{矩阵相关}

题集：

http://www.cppblog.com/notonlysuccess/archive/2009/03/03/75405.aspx

http://acm.hdu.edu.cn/forum/read.php?tid=15908

待补题。。。

Matrix Power Series

POJ - 3233

题意：求矩阵和S = A + A² + A³ + … + A^k.

构造矩阵

A A

0 1

然后这个矩阵自乘K次即可

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 #define CLR(m,a) memset(m,a,sizeof(m))
 6 const int maxn=65;
 7 int n,k,mod;
 8 struct Matrix
 9 {
10     int n,m[maxn][maxn];
11     void init(int sz)
12     {
13         CLR(m,0);
14         n=sz;
15     }
16     Matrix(int sz=0){init(sz);}
17     void setE()
18     {
19         for(int i=0;i<n;i++) m[i][i]=1;
20     }
21     Matrix operator* (const Matrix &a)
22     {
23         Matrix ans(n);
24         for(int k=0;k<n;k++)
25             for(int i=0;i<n;i++)
26                 for(int j=0;j<n;j++)
27                     ans.m[i][j]=(ans.m[i][j]+(m[i][k]*a.m[k][j])%mod)%mod;
28         return ans;
29     }
30 };
31 int main()
32 {
33     while(scanf("%d%d%d",&n,&k,&mod)!=EOF){
34         int tot=n*2;
35         Matrix a(tot),b(tot);
36         for(int i=0;i<n;i++)
37             for(int j=0;j<n;j++)
38                 scanf("%d",&a.m[i][j]);
39         for(int i=0;i<n;i++)
40             for(int j=n;j<tot;j++)
41                 a.m[i][j]=a.m[i][j-n];
42         for(int i=n;i<tot;i++) a.m[i][i]=1;
43         b.setE();
44         while(k){
45             if(k&1) b=b*a;
46             k>>=1;
47             a=a*a;
48         }
49         for(int i=0;i<n;i++)
50             for(int j=n;j<tot;j++)
51                 printf("%d%c",b.m[i][j],j==tot-1?'
':' ');
52     }
53 }

View Code