[POJ] 3233. Matrix Power Series

題目連結:http://poj.org/problem?id=3233

---

其實看到的時候以為是要用等比級數的公式，可是馬上就發現兩個會慘的點1.不保證有反矩陣, 2.不保證有些東西模m有反元素。後來被提示了才知道原來其實是用DP的想法找的轉移矩陣，然後對他快速冪。稍微列一下式就會得到$ \begin{bmatrix} S_i \\ A_i \end{bmatrix} = \begin{bmatrix} I \cdot S_{i-1}+A \cdot A_{i-1} \\ 0 \cdot S_{i-1}+A \cdot A_{i-1} \end{bmatrix} = \begin{bmatrix} I & A \\ 0 & A \end{bmatrix} \cdot \begin{bmatrix} S_{i-1} \\ A_{i-1} \end{bmatrix} $，所以就照著這個跑就好了。

#include <iostream>
using namespace std;

const int N = 60 + 2;

int (*A)[N] = new int[N][N];
int (*Mtx)[N] = new int[N][N];
int (*Temp)[N] = new int[N][N];
int (*Ans)[N] = new int[N][N];
int (*Res)[N] = new int[N][N];

int n, m, n2;

inline void mTimes(int[N][N],int[N][N],int[N][N],int,int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int k; cin>>n>>k>>m;
	n2 = n<<1;
	for(int i=0;i<n;i++) for(int j=0;j<n;j++)
		cin>>A[i][j];
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			Mtx[i][j]=(i==j);
			Mtx[i][j+n] = A[i][j];
			Mtx[i+n][j] = 0;
			Mtx[i+n][j+n]= A[i][j];
			Ans[i][j] = (i==j);
			Ans[i+n][j+n] = (i==j);
			Ans[i][j+n] = 0;
			Ans[i+n][j] = 0;
			Res[i][j] = A[i][j];
			Res[i+n][j] = A[i][j];
		}
	}
	k--;
	while(k){
		if(k&1){
			mTimes(Ans, Mtx, Temp, n2, n2, n2);
			swap(Ans, Temp);
		}
		k>>=1;
		mTimes(Mtx, Mtx, Temp, n2, n2, n2);
		swap(Temp, Mtx);
	}
	mTimes(Ans, Res, Temp, n2, n, n2);
	swap(Res, Temp);
	for(int i=0;i<n;i++) for(int j=0;j<n;j++)
		cout<<Res[i][j]<<" \n"[j==n-1];
	return 0;
}

inline void mTimes(int a[N][N],int b[N][N],int c[N][N],int I, int J, int K){
	for(int i=0;i<I;i++){
		for(int j=0;j<J;j++){
			c[i][j]=0;
			for(int k=0;k<K;k++)
				c[i][j] = (c[i][j] + (a[i][k]*b[k][j])%m)%m;
		}
	}
}