1122 机器人走方格 V4

基准时间限制：1 秒 空间限制：131072 KB 

四个机器人a b c d，在2 * 2的方格里，一开始四个机器人分别站在4个格子上，每一步机器人可以往临近的一个格子移动或留在原地（同一个格子可以有多个机器人停留），经过n步后有多少种不同的走法，使得每个毯子上都有1机器人停留。由于方法数量巨大，输出 Mod 10^9 + 7的结果。

Input

输入1个数N（0 <= N <= 10^9)

Output

输出走法的数量 Mod 10^9 + 7

Input示例

1

Output示例

9
思路：矩阵快速幂。
这道题和hdu2232是一样的只不过hud的那到题数据比较小，用dp能过，但这道题必须要矩阵快速幂。这道题的思路可以参考http://blog.csdn.net/womendeaiwoming/article/details/5806700
给出递推：

其中f下标表示第i个机器人在第j的方格的方案；

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 using namespace std;
8 typedef long long LL;
9 typedef struct node {
10 LL m[4][4];
11 node() {
12 memset(m,0,sizeof(m));
13 }
14 } maxtr;
15 void Init(maxtr *p);
16 maxtr quick(maxtr ans,LL m);
17 const LL mod = 1e9 + 7;
18 LL dp[4][4];
19 LL dpx[4][4];
20 int main(void) {
21 LL n;
22 scanf("%lld",&n);
23 if(n == 0) {
24 printf("1\n");
25 } else {
26 maxtr ac;
27 Init(&ac);
28 int i,j,z;
29 maxtr ak = quick(ac,n);
30 memset(dpx,0,sizeof(dpx));
31 for(i = 0; i < 4; i++) { 32 for(j = 0; j < 4; j++) { 33 for(z = 0; z < 4; z++) { 34 dpx[i][j] = dpx[i][j] + ak.m[i][z]*dp[z][j]%mod; 35 dpx[i][j]%=mod; 36 } 37 } 38 } 39 int x,y; 40 LL sum = 0; 41 for(i = 0; i < 4; i++) { 42 for(j = 0; j < 4; j++) { 43 for(x = 0; x < 4; x++) { 44 for(y = 0; y < 4; y++) { 45 if(i==j||i==x||i==y||j==x||j==y||x==y) 46 continue; 47 else { 48 sum = sum + (((dpx[0][i]*dpx[1][j]%mod)*dpx[2][x]%mod)*dpx[3][y])%mod; 49 sum %= mod; 50 } 51 } 52 } 53 } 54 } 55 printf("%lld\n",sum); 56 } 57 return 0; 58 } 59 maxtr E() { 60 int i,j; 61 maxtr ans; 62 for(i = 0 ; i < 4 ; i++) { 63 for(j = 0 ; j < 4 ; j++) { 64 if(i == j) { 65 ans.m[i][j] = 1; 66 } 67 } 68 } 69 return ans; 70 } 71 void Init(maxtr *p) { 72 int i,j; 73 for(i = 0; i < 4; i++) { 74 fill(p->m[i],p->m[i]+4,1);
75 }
76 p->m[0][2] = 0;
77 p->m[1][3] = 0;
78 p->m[2][0] = 0;
79 p->m[3][1] = 0;
80 memset(dp,0,sizeof(dp));
81 for(i = 0; i < 4; i++) { 82 for(j = 0; j < 4; j++) { 83 if(i == j) 84 dp[i][j] = 1; 85 } 86 } 87 } 88 maxtr quick(maxtr ans,LL m) { 89 int i,j,z; 90 maxtr ask = E(); 91 while(m) { 92 if(m&1) { 93 maxtr C; 94 for(i = 0; i < 4; i++) { 95 for(j = 0 ; j < 4; j++) { 96 for(z = 0; z < 4; z++) { 97 C.m[i][j] = C.m[i][j] + ans.m[i][z]*ask.m[z][j]%mod; 98 C.m[i][j]%=mod; 99 } 100 } 101 } 102 ask = C; 103 } 104 maxtr ak; 105 for(i = 0 ; i < 4; i++) { 106 for(j = 0; j < 4; j++) { 107 for(z = 0 ; z < 4; z++) { 108 ak.m[i][j] = ak.m[i][j] + ans.m[i][z]*ans.m[z][j]%mod; 109 ak.m[i][j]%=mod; 110 } 111 } 112 } 113 ans = ak; 114 m>>=1;
115 }
116 return ask;
117 }