David has a white board with 2×N2 \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.
One line including an integer n(0<n≤109)n(0<n \le 10^9)n(0<n≤109)
One line including an integer, which represent the answer mod 1000000007\bmod 1000000007mod1000000007
思路：这题是纯数学题（我当时傻fufu的画了很多图，而且还没画够情况。佛了，知道真相的我眼泪掉下来。）第一列和最后一列有两种选择，剩下的格子要不要，每一列有3中选择，要哪个和都要，结果就是4*3^(n-2) #include <cstdio> #include <iostream> #include <vector> #include <string> #include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; #define ll long long const int inf = 0x3f3f3f3f; const ll linf =1LL<<50; const int maxn = 1e5+8; const ll mod = 1000000007; ll qsm(ll a, ll b) { ll sum = 1; a = a%mod; while(b) { if(b&1) { sum = (sum*a)%mod; } b /= 2; a = (a*a)%mod; } return sum; } int main() { ll n; scanf("%lld", &n); ll sum = 4*qsm(3, n-2); printf("%lld\n", sum); return 0; }
转载于:https://www.cnblogs.com/RootVount/p/10752643.html
相关资源：JAVA上百实例源码以及开源项目