设S[k] = A + A^2 +````+A^k.

设矩阵T =

A[1]	0
E	E

 

这里的E为n*n单位方阵，0为n*n方阵

令A[k] = A ^ k

矩阵B[k] =

A[k+1]

S[k]

则有递推式B[K] = T*B[k-1],即有B[k] = T^k*B[0],令S[0] 为n*n的0矩阵。

矩阵快速幂求出即可·····

还可以使用两次分治的方法····自行百度····

贴代码：

1 #include
      
        2 #include
       
         3 int n,k,p,d;//d = 2*n 4 struct matrix 5 { 6     int m[70][70]; 7 } A; 8 matrix mul(int a[70][70],int b[70][70]) 9 {10     matrix ans;11     memset(ans.m,0,sizeof(ans.m));12     for(int i=1; i<=d; ++i)13         for(int j=1; j<=d; ++j)14             for(int k=1; k<=d; ++k)15                 ans.m[i][j] = (ans.m[i][j] + a[i][k]*b[k][j]%p)%p;16     return ans;17 }18 matrix qPow()19 {20     matrix ans;21     memset(ans.m,0,sizeof(ans.m));22     for(int i=1; i<=d; ++i)23         ans.m[i][i] = 1;24     while(k)25     {26         if(k&1) ans = mul(ans.m,A.m);27         A = mul(A.m,A.m);28         k >>= 1;29     }30     return ans;31 }32 int main()33 {34 //    freopen("in.txt","r",stdin);35     while(~scanf("%d%d%d",&n,&k,&p))36     {37         memset(A.m,0,sizeof(A.m));38         int t[35][35];39         for(int i=1; i<=n; ++i)40         {41             for(int j=1; j<=n; ++j)42             {43                 scanf("%d",&A.m[i][j]);44                 t[i][j] = A.m[i][j];45             }46         }47         for(int i=n+1; i<=2*n; ++i)48             A.m[i][i-n] = 1,A.m[i][i] = 1;49         d = n<<1;50         matrix ans = qPow();51         for(int i=n+1; i<=d; ++i)52         {53             for(int j=1; j<=n; ++j)54             {55                 int res =0;56                 for(int k=1; k<=n; ++k)57                     res = (res + ans.m[i][k]*t[k][j]%p)%p;58                 if(j != 1) printf(" ");59                 printf("%d",res);60             }61             puts("");62         }63     }64     return 0;65 }