ACM思维题训练集合
代码语言：javascript复制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
代码语言：javascript复制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
代码语言：javascript复制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
代码语言：javascript复制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,11,111,1111C00C10C20C30
1,21,321,4321,54321C11C21C31C41
1,31,631,10631C22C32C42C52
这个题用lucas过不了，卡时间，然后写递推，感谢SHDL写的递推板子
代码语言：javascript复制#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("");
}
