首页 > 代码库 > 1122 机器人走方格 V4

1122 机器人走方格 V4

2024-08-11 04:08:24   221人阅读

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<stdio.h>  2 #include<algorithm>  3 #include<iostream>  4 #include<stdlib.h>  5 #include<queue>  6 #include<string.h>  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 }

 

1122 机器人走方格 V4






























        

            
                
                  
                
                

                    联系

                    我们