2014 ICPC模擬地区予選 G - Cookie Counter

問題

n枚のクッキーをd日間かけて食べる。
一日に食べてよい枚数はx枚未満。このとき、クッキーの食べ方は何通りあるか。

二つの食べ方が異なるとは、どこかの日で、二つの食べ方で食べたクッキーの枚数が異なることを言う。

制約条件

n≦2000
d≦10^20

方針

行列の累乗をしたくなる。
けど愚直にやるとO(n^3logd).

この問題の行列は斜めの線上に同じ数が並んでいる行列。
（テプリッツ行列, Toeplitz Matrixと言うらしい）

テプリッツ行列同士の和、積はまたテプリッツ行列になるので、
（しかも上三角行列なので）行列の１行目だけを持っていれば行列全体が復元できる。
つまり積の計算量がO(n^2)になるので間に合う。

ソースコード

inline vi operator*(const vi &a, const vi &b){
	int n = a.size();
	vi c(n);
	rep(i, 1) rep(j, n){
		ll s = 0;
		rep(k, n) s += (ll)(i > k ? 0 : a[k - i]) * (k > j ? 0 : b[j - k]) % mod;
		c[j] = s % mod;
	}
	return c;
}
inline vi pow(vi a, ll m){
	vi res(a.size());
	res[0] = 1;
	for(; m; m /= 2){
		if(m & 1) res = res * a;
		a = a * a;
	}
	return res;
}
 
 
int main(){
	ll n, d, x;
	while(cin >> n >> d >> x, n){
		n++;
		x = min(x, n);
		vi m(n);
		rep(i, x) m[i] = 1;
		m = pow(m, d);
		cout << m[n - 1] << endl;
	}
	
	return 0;
}