矩阵快速幂

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1113

这个题因为m比较大,所以不能递归求解,需要换成循环的形式.

 1 #include <cstdio>
 2 typedef long long ll;
 3 const int mod = 1e9+7;
 4 struct Mat
 5 {
 6     ll matrix[100][100];
 7 };
 8 
 9 int n,m;
10 
11 Mat mul(Mat a,Mat b)
12 {
13     Mat c;
14     for(int i=0;i<n;i++)
15         for(int j=0;j<n;j++)
16         {
17             c.matrix[i][j]=0;
18             for(int k=0;k<n;k++)
19             {
20                 c.matrix[i][j]+=(a.matrix[i][k]*b.matrix[k][j])%mod;
21             }
22             c.matrix[i][j]%=mod;
23         }
24     return c;
25 }
26 Mat mat;
27 Mat solve(int m)
28 {
29     Mat mt=mat;
30     m--;
31     while(m)
32     {
33         if(m&1)
34         {
35             mt=mul(mat,mt);
36             m--;
37         }
38         mat=mul(mat,mat);
39         m/=2;
40     }
41     return mt;
42 }
43 int main()
44 {
45     //freopen("a.txt","r",stdin);
46     int x;
47     Mat a,b,c;
48     scanf("%d%d",&n,&m);
49     for(int i=0;i<n;i++)
50         for(int j=0;j<n;j++)
51         {
52             scanf("%d",&x);
53             a.matrix[i][j]=x;
54         }
55     mat=a;
56     /*for(int i=0;i<n;i++)
57     {
58         for(int j=0;j<n;j++)
59             printf("%d ",mt.matrix[i][j]);
60         printf("
");
61     }*/
62     c=solve(m);
63     for(int i=0;i<n;i++)
64     {
65         for(int j=0;j<n-1;j++) printf("%lld ",c.matrix[i][j]);
66         printf("%lld
",c.matrix[i][n-1]);
67     }
68     return 0;
69 }