[TIOJ] 1331. 索拉數列

題目連結:http://tioj.infor.org/problems/1331

---

看一眼大概就可以發現這就是一個經典的矩陣優化DP的題目，稍微算一下後得到轉移矩陣$ \begin{bmatrix} 0 & x \\ 1 & y \\ \end{bmatrix} $，所以要求$a_n$其實就是算$ \begin{bmatrix} a_0 & a_1 \\ \end{bmatrix} \times \begin{bmatrix} 0 & x \\ 1 & y \\ \end{bmatrix}^n = \begin{bmatrix} a_n & a_{n+1} \\ \end{bmatrix}$ ，然後冪次的部分用快速冪解決。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef unsigned long long llu;

const llu mod = 1LL<<32;
auto A = new llu[2][2];
auto B = new llu[2][2];
auto C = new llu[2][2];
auto F = new llu[2][2];

void mTimes(llu[2][2],llu[2][2],llu[2][2],int,int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	lld n, a, b, x, y;
	while(cin>>n, n>=0){
		cin>>a>>b>>x>>y;
		F[0][0]=a;
		F[0][1]=b;
		A[0][0]=0;
		A[0][1]=x;
		A[1][0]=1;
		A[1][1]=y;
		B[0][0]=1;
		B[0][1]=0;
		B[1][0]=0;
		B[1][1]=1;
		while(n>0){
			if(n&1){
				mTimes(A,B,C,2,2,2);
				swap(C,B);
			}
			n>>=1;
			mTimes(A,A,C,2,2,2);
			swap(A, C);
		}
		C[0][0]=(((F[0][0]*B[0][0])%mod)+((F[0][1]*B[1][0])%mod))%mod;
		cout<<(lld)C[0][0]<<'\n';
	}
	return 0;
}

void mTimes(llu a[2][2], llu b[2][2], llu c[2][2], int x, int y, int z){
	for(int i=0;i<x;i++){
		for(int j=0;j<z;j++){
			c[i][j]=0;
			for(int k=0;k<y;k++)
				c[i][j] += (a[i][k]*b[k][j])%mod;
			c[i][j]%=mod;
		}
	}
}