Typical DP Contest T - フィボナッチ

問題

数列aiをai = 1(i ≦ K)
ai = ai-1 + ai-2 + ... + ai-K (i > K)
と定義するとき、aNをmod 10^9 + 7で求めよ。

制約条件

K≦1000
N≦10^9

方針

漸化式を行列の累乗で計算するとO(K^3logN)かかって無理なので、
漸化式のの高速計算法を使うと解ける。
（wataさんがきたまさ法と呼んでいた奴http://d.hatena.ne.jp/wata_orz/20090922/1253615708）

この問題では漸化式に定数項がないので、定数項なしで解説する。
定数項がある場合は項が一個くっついて面倒なだけで、本質的には変わらない。

amをa0からaK-1の線形結合で表していくのが基本方針。
amが表せてるとき、a2mはa0からa2K-2で表せる。

何故なら、
am = Σkiaiと書けるとき
a2m = Σkiai+m （漸化式をm項ずらす）
= Σki(Σkjai+j)　（上の漸化式をi項ずらす）
と書けるため。

で、aK〜a2K-2は、愚直に一番最初の漸化式を使ってa0〜aK-1で表してやればよい。

こうすれば、amからa2mを求められるので、
繰り返し二乗法的なことをすればaNがO(K^2 logN)で求められる。

ソースコード

typedef deque<int> di;

const int mod = inf + 7;
int K, N;

inline void advance(di &co){ //amをa0〜aK-1で表しているとき、am+1の表現を求める
	int n = co.size();
	co.push_front(0);
	rep(i, n) (co[i] += co[n]) %= mod;
	co.pop_back();
}

inline void dbl(di &v){ //amをa0〜aK-1で表しているとき、a2mの表現を求める
	
	int n = v.size();
	di prev = v;
	v.clear();
	v.resize(n * 2);
	
	rep(i, n) rep(j, n) (v[i + j] += (ll)prev[i] * prev[j] % mod) %= mod;
	
	di co(K, 1);
	for(int i = n; i < 2 * n; i++){
		
		rep(j, n) (v[j] += (ll)v[i] * co[j] % mod) %= mod;
		advance(co);
	}
	rep(i, n) v.pop_back();
}


int main(){
	cin >> K >> N;
	N--;
	
	di v(K, 0);
	v[1] = 1;
	
	int p;
	for(p = 31; !(N >> p & 1); p--);
	p--;
	for(; p >= 0; p--){
		dbl(v);
		if(N >> p & 1) advance(v);
	}
	
	ll ans = 0;
	rep(i, K) ans += v[i];
	cout << ans % mod << endl;
	
	return 0;
}

これでtypical DP全部解いた。
後は解説記事書いてないのがG, H, I, J, K, L, M, N, R, S