yukicoder : No.891 隣接3項間の漸化式

890より簡単な気はする。
https://yukicoder.me/problems/no/891

問題

整数A,B,Nが与えられる。
数列Xは、X[0]=0, X[1]=1, X[i] = (A*X[i-1] + B*X[i-2]) mod (10^9+7)であるとき、X[N]を求めよ。

解法

漸化式を２次正方行列で表現して行列累乗といういつものパターン。

const int MAT=2;
struct Mat { ll v[MAT][MAT]; Mat(){ZERO(v);};};
ll mo=1000000007;
Mat mulmat(Mat& a,Mat& b,int n=MAT) {
	ll mo2=4*mo*mo;
	int x,y,z; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(x,n) FOR(z,n) FOR(y,n) {
		r.v[x][y] += a.v[x][z]*b.v[z][y];
		if(r.v[x][y]>mo2) r.v[x][y] -= mo2;
	}
	FOR(x,n) FOR(y,n) r.v[x][y]%=mo;
	return r;
}

Mat powmat(ll p,Mat a,int n=MAT) {
	int i,x,y; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(i,n) r.v[i][i]=1;
	while(p) {
		if(p%2) r=mulmat(r,a,n);
		a=mulmat(a,a,n);
		p>>=1;
	}
	return r;
}

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}
int A,B,N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>N;
	Mat V;
	V.v[1][0]=1;
	V.v[0][0]=A;
	V.v[0][1]=B;
	Mat W=powmat(N,V);
	cout<<W.v[1][0]<<endl;
}

まとめ

890と順番入れ替えてもよかったかもね。