Coloring Game

一道签到题…卡在快速幂取模，最后改对了，花费时间太长了，记录一下…

题目链接: https://nanti.jisuanke.com/t/38227

David has a white board with 2 \times N2×N grids.He decides to paint some grids black with his brush.He always starts at the top left corner and ends at the bottom right corner, where grids should be black ultimately.
Each time he can move his brush up(↑), down(↓), left(←), right(→), left up(↖), left down(↙), right up(↗), right down (↘) to the next grid.
For a grid visited before,the color is still black. Otherwise it changes from white to black.
David wants you to compute the number of different color schemes for a given board. Two color schemes are considered different if and only if the color of at least one corresponding position is different.

Input
One line including an integer n $(0< n ≤ 10^9)$

Output
One line including an integer, which represent the answer mod 1000000007
样例输入1
2
样例输出1
4

样例输入1
3
样例输出1
12

题意：从左上角到后下角的路径数，没经过一个格子，黑的不变，白的变黑
思路: 从输入样例可以看出，对于每一列来讲除了第一列和最后一列，每一列都有三种情况，第一列和最后一列只有两种情况，所以路径数为$3^{n-2}*2*2$

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull  n;
ull poww(ull a, ull b) {
    ull ans = 1, base = a;
    while (b != 0) {
        if (b & 1 != 0)
            {
                ans =ans* base%1000000007;
            }
            base = base*base%1000000007;
            b >>= 1;
    }
    return ans;
}
int main()
{
	while(scanf("%lld", &n)!=EOF){
	if(n==1){
        printf("1\n");
	}
	else{
	ull ans = poww(3, n - 2);
	printf("%lld\n", ans*4%1000000007);
	}
	}
	return 0;
}

总结：快速幂且取模

// 位运算
typedef long long ll;
ll mod_pow(ll x,ll n,ll mod){
	ll res=1;
	while(n>0){
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}

// 递归
typedef long long ll;
ll mod_pow(ll x,ll n,ll mod){
	if(n==0) return 1;
	ll res=mod_pow(x*x%mod,n/2,mod);
	if(n&1) res=res*x%mod;
	return res;
}