『算法-ACM 竞赛-思维题』–CodeForces - 223 C Partial Sums（组合数学的先线性递推）

ACM 思维题训练集合

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

$如果把a1,a2,a3….an的系数取出，会有如下规律\
1 , 1 1,111,1111 \ C^0_0C^0_1C^0_2C^0_3\
1,21,321,4321,54321\ C^1_1C^1_2C^1_3C^1_4\
1,31,631,10\ 631\ C^2_2C^2_3 C^2_4C^2_5$
这个题用 lucas 过不了，卡时间，然后写递推，感谢 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("");
}