示例题目： POJ3233
Time Limit: 3000MS Memory Limit: 131072K Total Submissions: 24251 Accepted: 10081 Description
Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.
Input
The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 109) and m (m < 104). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.
Output
Output the elements of S modulo m in the same way as A is given.
Sample Input
2 2 4 0 1 1 1 Sample Output
1 2 2 3
#include <iostream> #include <vector> #include <algorithm> #include <cstdio> using namespace std; typedef long long LL; const int MAXN=1e4+5; typedef vector<int> vec; typedef vector<vec> mat; int n,k,MOD; mat A; mat mul(mat &A,mat &B) { mat C(A.size(),vec(B[0].size())); for(int i=0;i<A.size();i++){ for(int k=0;k<B.size();k++){ for(int j=0;j<B[0].size();j++){ C[i][j]=(C[i][j]+A[i][k]*B[k][j])%MOD; } } } return C; } mat pow(mat A,LL n) { mat B(A.size(),vec(A.size())); for(int i=0;i<A.size();i++) B[i][i]=1; while(n>0) { if(n&1) B=mul(B,A); A=mul(A,A); n>>=1; } return B; } void solve() { mat B(n*2,vec(n*2)); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ B[i][j]=A[i][j]; } B[n+i][i]=B[n+i][n+i]=1; } B=pow(B,k+1);//I+A+A^2+...+A^k for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ int a=B[n+i][j]%MOD; //减去I if(i==j) a=(a+MOD-1)%MOD; printf("%d%c",a,j+1==n?'\n':' '); } } } int main() { while(scanf("%d%d%d",&n,&k,&MOD)!=EOF) { A=mat(n,vec(n)); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { scanf("%d",&A[i][j]); } } solve(); } return 0; }