POJ 3233 Matrix Power Series（矩阵优化）
最后更新于：2022-04-01 15:53:27
题目链接：[点击打开链接](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;
}
~~~