読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

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を求めよ。

  •  D_{1, j} = A(j)
  •  D_{i, j} = \sum_{k = 1}^j D_{i - 1, k} \ (i \ge 2)

解法

i>1の時、 D_{i,j}=D_{i-1,j+2} - {}_{i+j-1} C_{i-2}であることがわかる。

よって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)と関係するのがわからなかった。

広告を非表示にする