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; }