題目鏈接：[點擊打開鏈接](http://poj.org/problem?id=3233) 題意：求S[k] = A + A^2 + ..... + A^k 利用矩陣快速冪可以很快的求出A矩陣的k次方， 但是該題是求和， 如果還按照原來的方法， 將要計算k次， 復雜度無法承受。 我們可以構造一個矩陣 ? （A ?0） ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（E ?E） 此時令S[k] = E + A + A^2 + ..... + A^(k-1) 那么 ?( A^k ) ? ? ( A ? 0)(A^(k-1)) ? ? ? ?(A ? 0 )^k (E) ? ? ? ??? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?= ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? (S[k] ) ? ? ?(E ? E)(S[k-1] ) ? ? ? ? ?(E ? E ) ? ? (0) 那么， 我們只要計算出S[k+1] = E + A + .... + A^k 然后將對角線元素-1就行了。 細節參見代碼： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int mod = 10007; const int maxn = 100; int T,n,m,k; typedef vector<int> vec; typedef vector<vec> mat; mat mul(mat &a, mat &b) { mat c(a.size(), vec(a[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]) % m; } } } return c; } mat pow(mat a, ll n) { mat b(a.size(), vec(a[0].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; } int main() { scanf("%d%d%d",&n,&k,&m); mat a(2*n, vec(2*n)); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { scanf("%d",&a[i][j]); } } for(int i=n;i<2*n;i++) { for(int j=0;j<2*n;j++) if(i - n == j || i == j) a[i][j] = 1; } a = pow(a, k+1); for(int i=n;i<2*n;i++) { for(int j=0;j<n;j++) { if(i - n == j) a[i][j] = (a[i][j] - 1 + m) % m; printf("%d%c",a[i][j], j == n-1 ? '\n' : ' '); } } return 0; } ~~~