yukicoder : No.3228 Very Large Fibonacci Sum

これは典型かな。
https://yukicoder.me/problems/no/3228

問題

整数a,b,c,d,e,Nが与えられる。

• F(0)=a
• F(1)=b
• F(n)= c*F(n-1) + d *F(n-2) + e

としたとき、F(0)+F(1)+...+F(N)を求めよ。

解法

F(n)のprefix sumをS(n)とする。
(S(n),F(n),F(n-1),1)の線形和で(S(n+1),F(n+1),F(n),1)を計算できるので、後は行列累乗しよう。

ll A,B,C,D,E,N;
const ll mo=1000000007;
// S(n),F(n),F(n-1),1
const int MAT=4;
struct Mat { ll v[MAT][MAT]; Mat(){ZERO(v);};};


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;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>C>>D>>E>>N;
	
	if(N==0) {
		cout<<(A%mo+mo)%mo<<endl;
	}
	else {
		Mat P;
		P.v[0][0]=1;
		P.v[0][1]=C;
		P.v[0][2]=D;
		P.v[0][3]=E;
		P.v[1][1]=C;
		P.v[1][2]=D;
		P.v[1][3]=E;
		P.v[2][1]=1;
		P.v[3][3]=1;
		P=powmat(N-1,P);
		ll ret=P.v[0][0]*(A+B)+P.v[0][1]*(B)+P.v[0][2]*(A)+P.v[0][3]*(1);
		ret=(ret%mo+mo)%mo;
		cout<<ret<<endl;
	}
}

まとめ

すんなりだった。