Typical DP Contest : T - フィボナッチ

yukicoderをちゃんとやっていれば余裕。
http://tdpc.contest.atcoder.jp/tasks/tdpc_fibonacci

問題

以下の条件のもとで、A[N]を求めよ。

• A[i]=1 (i≦K)
• A[i] = A[i−1] + ... + A[i−K] (i>K)

解法

yukicoder214,215を解いていれば余裕。
高速きたまさ法は不要で、通常のきたまさ法で通ります。
yukicoder : No.214 素数サイコロと合成数サイコロ (3-Medium) - kmjp's blog
yukicoder : No.215 素数サイコロと合成数サイコロ (3-Hard) - kmjp's blog

ll mo=1000000007;
ll N,K;

vector<ll> mult(vector<ll>& v,vector<ll>& v2) {
	int i,j;
	vector<ll> t(2*K,0);
	FOR(i,K) FOR(j,K) t[i+j] += v[i]*v2[j]%mo;
	for(i=2*K-2;i>=K;i--) {
		ll ti=t[i]%mo;
		for(j=1;j<=K;j++) t[i-j] += ti;
	}
	FOR(j,K) ((t[j]%=mo)+=mo)%=mo;
	t.resize(K);
	return t;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K>>N;
	if(N<=K) return _P("1\n");
	
	
	vector<ll> R(K,0),V(K,0);
	R[0]=V[1]=1;
	N--;
	while(N) {
		if(N%2) R=mult(R,V);
		V=mult(V,V);
		N/=2;
	}
	
	ll ret=0;
	FOR(i,K) ret+=R[i];
	cout << ((ret % mo)+mo)%mo << endl;
}

まとめ

yukicoderをやっていたら、TDPCの最終問題があっさり解けるようになっていた。