Codeforces 138C (226C) Partial Sums

問題

n項からなる数列a[i]が与えられる。
これに対して、次のような操作を考える。
s[i] = Σ[j = 0 to i] a[j]
として、a[i] := s[i]と置き換える。


この操作をk回行った後のa[i]をmod 10^9 + 7で出力せよ。

制約条件

n≦2000
a[i]≦10^9
k≦10^9

方針

k回操作を終えたあとのa[i]が、一番最初のa[i - j]を何回足しているかを考える。
ちょっと考えるとC(k - 1 + j, j)回足していることがわかる。


二項係数をあらかじめ計算しておけば、
答えの各項がO(n)で求まり、全体でO(n^2)の計算量で答えが求まる。

ソースコード

const int mod = (int)1e9 + 7;

inline ll pw(ll n, ll m){
	ll res = 1;
	for(; m; m /= 2){
		if(m & 1) res = res * n % mod;
		n = n * n % mod;
	}
	return res;
}
inline ll inv(ll n){
	return pw(n, mod - 2);
}

int n, k, a[2000];
ll C[2010];

int main(){
	cin >> n >> k;
	
	//C(k - 1 + i, i)を前計算しておく。
	C[0] = 1;
	rep(i, 2000) C[i + 1] = C[i] * (k + i) % mod * inv(i + 1) % mod;
	
	rep(i, n){
		cin >> a[i];
		ll s = 0;
		rep(j, i + 1) (s += a[i - j] * C[j]) %= mod;
		cout << s << (i == n - 1 ? "\n" : " ");
	}
	return 0;
}