yukicoder : No.720 行列のできるフィボナッチ数列道場 (2)

適当な解法なので参考にしないように。
https://yukicoder.me/problems/no/720

問題

F[0]=0, F[1]=1から生成されるフィボナッチ数列Fを考える。
２整数N,Mが与えられたとき、F[M]+F[2M]+...+F[NM]を求めよ。

解法

実験したりOEISを見たりすると(Mに依存した)定数Aを用いて、以下の形を成すことがわかる。

• Mが奇数のとき、F[kM] =A*F[(k-1)M] - F[(k-2)M]
• Mが偶数のとき、F[kM] =A*F[(k-1)M] + F[(k-2)M]

幸いMは小さいのでF[2M]とF[M]を愚直に求めればF[0]=0からA=F[2M]/F[M]となる。
あとはいつもの行列累乗の要領でF[kM]およびF[M]+...+F[kM]を求められる。
(総和の方がわからない場合、自分が過去に出題しているのでそちらを参考)

yukicoder : No.194 フィボナッチ数列の理解(1) - kmjp's blog

ll N,M;
ll F[101010];
ll mo=1000000007;
ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

const int MAT=3;
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>>N>>M;
	F[0]=0;
	F[1]=1;
	for(i=2;i<=101000;i++) F[i]=(F[i-1]+F[i-2])%mo;
	
	Mat G;
	G.v[0][0]=G.v[2][1]=1;
	G.v[0][1]=G.v[1][1]=F[2*M]*modpow(F[M])%mo;
	G.v[0][2]=G.v[1][2]=(M%2==1)?1:mo-1;
	G=powmat(N-1,G);
	
	cout<<(G.v[0][0]+G.v[0][1])*F[M]%mo<<endl;
	
	
}

まとめ

718も埋め込みで解いたし、今回色々雑である。