ACM思維題訓(xùn)練集合

You've got an array a, consisting of n integers. The array elements are indexed from 1 to n. Let's determine a two step operation like that:First we build by the array a an array s of partial sums, consisting of n elements. Element number i (1?≤?i?≤?n) of array s equals . The operation x mod y means that we take the remainder of the division of number x by number y. Then we write the contents of the array s to the array a. Element number i (1?≤?i?≤?n) of the array s becomes the i-th element of the array a (ai?=?si). You task is to find array a after exactly k described operations are applied.

Input

The first line contains two space-separated integers n and k (1?≤?n?≤?2000, 0?≤?k?≤?109). The next line contains n space-separated integers a1,?a2,?...,?an — elements of the array a (0?≤?ai?≤?109).

Output

Print n integers — elements of the array a after the operations are applied to it. Print the elements in the order of increasing of their indexes in the array a. Separate the printed numbers by spaces.

Examples

Input 3 1 1 2 3 Output 1 3 6 Input 5 0 3 14 15 92 6 Output 3 14 15 92 6

$$\begin{gathered} 如果把a1,a2,a3....an的系數(shù)取出，會(huì)有如下規(guī)律 \\ 1,11,111,1111C_0^0{C}_1^0{C}_2^0{C}_3^0 \\ 1,21,321,4321,54321C_1^1{C}_2^1{C}_3^1{C}_4^1 \\ 1,31,631,10631C_2^2{C}_3^2{C}_4^2{C}_5^2 \end{gathered}$$
這個(gè)題用lucas過(guò)不了，卡時(shí)間，然后寫遞推，感謝SHDL寫的遞推板子

#include <bits/stdc++.h> using namespace std; template <typename t> void read(t &x) {char ch = getchar();x = 0;int f = 1;while (ch < '0' || ch > '9')f = (ch == '-' ? -1 : f), ch = getchar();while (ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();x *f; } #define wi(n) printf("%d ", n) #define wl(n) printf("%lld ", n) typedef long long ll; //---------------https://lunatic.blog.csdn.net/-------------------// #define MOD 1000000007 // LL quickPower(LL a, LL b) // { // LL ans = 1; // a %= MOD; // while (b) // { // if (b & 1) // { // ans = ans * a % MOD; // } // b >>= 1; // a = a * a % MOD; // } // return ans; // }// LL c(LL n, LL m) // { // if (m > n) // { // return 0; // } // LL ans = 1; // for (int i = 1; i <= m; i++) // { // LL a = (n + i - m) % MOD; // LL b = i % MOD; // ans = ans * (a * quickPower(b, MOD - 2) % MOD) % MOD; // } // return ans; // }// LL lucas(LL n, LL m) // { // if (m == 0) // { // return 1; // } // return c(n % MOD, m % MOD) * lucas(n / MOD, m / MOD) % MOD; // } ll power(ll a, ll b, ll p) {ll ans = 1 % p;for (; b; b >>= 1){if (b & 1)ans = ans * a % p;a = a * a % p;}return ans; } long long b[20005], ans[20005], mm[500000]; void init(ll n, ll k) {mm[1] = 1;for (ll i =2; i <= n; i++){mm[i] = ((mm[i - 1] * (k + i - 2)) % MOD * power(i - 1, MOD - 2, MOD)) % MOD;//cout<<mm[i]<<endl;} }int main() {int n, k;read(n), read(k);init(n,k);for (int i = 1; i <= n; i++){read(b[i]);for (int j = i; j >= 1; j--){ans[i] += (mm[i-j+1] * b[j]) % MOD;ans[i] %= MOD;}}for (int i = 1; i <= n; i++)// k == 0 ? wl(b[i]) :wl(ans[i]);puts(""); }

總結(jié)

以上是生活随笔為你收集整理的CF思维联系–CodeForces - 223 C Partial Sums（组合数学的先线性递推）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。