square869120Contest #3 : G - フィボナッチ数の総和 / Sum of Fibonacci Sequence

これは解けるべきだった…のか？
http://s8pc-3.contest.atcoder.jp/tasks/s8pc_3_g

問題

Aをフィボナッチ数列(A(1)=A(2)=1, A(i)=A(i-1)+A(i-2))とする。
以下の関数DにおけるD(N,M) mod 1000000007を求めよ。

• 
• 

解法

i＞1の時、であることがわかる。

よってD(1,j+(i-1)*2)=A(j+(i-1)*2)を行列累乗で求め、そこからCombinationの値を順次引いていこう。
このCombinationの値はそれぞれ個別に計算すると間に合わないが、実際は分子分母が少しずつ変化するのでその差分だけ掛け割りしていけばよい。

ll N,M;
ll mo=998244353;

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

ll fib(ll k,ll a1=1,ll a2=1) {
	ll R[2][2]={{1,0},{0,1}};
	ll A[2][2]={{1,1},{1,0}};
	k--;
	
	while(k) {
		ll S[2][2], T[2][2];
		if(k%2) {
			S[0][0]=(A[0][0]*R[0][0]+A[0][1]*R[1][0])%mo;
			S[0][1]=(A[0][0]*R[0][1]+A[0][1]*R[1][1])%mo;
			S[1][0]=(A[1][0]*R[0][0]+A[1][1]*R[1][0])%mo;
			S[1][1]=(A[1][0]*R[0][1]+A[1][1]*R[1][1])%mo;
			swap(S,R);
		}
		T[0][0]=(A[0][0]*A[0][0]+A[0][1]*A[1][0])%mo;
		T[0][1]=(A[0][0]*A[0][1]+A[0][1]*A[1][1])%mo;
		T[1][0]=(A[1][0]*A[0][0]+A[1][1]*A[1][0])%mo;
		T[1][1]=(A[1][0]*A[0][1]+A[1][1]*A[1][1])%mo;
		swap(T,A);
		k>>=1;
	}
	return (R[1][0]+R[1][1])%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	M+=2*(N-1);
	ll F=fib(M);
	
	ll a=1,b=1,c=1;
	ll M1=M-1,M2=M1;
	for(i=1;i<N;i++) {
		F=(F+mo-b*modpow(a*c%mo)%mo)%mo;
		
		(a*=M1)%=mo;
		M1=(M1+mo-1)%mo;
		(b*=M2)%=mo;
		M2=(M2+mo-1)%mo;
		(b*=M2)%=mo;
		M2=(M2+mo-1)%mo;
		(c*=i)%=mo;
	}
	cout<<F<<endl;
}

まとめ

D(i,j)がD(i-1,j+1)ではなくD(i-1,j+2)と関係するのがわからなかった。