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 nelements. 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
题意：
有一个长度为N的数组，每次用它的前缀和数组代替它，求执行K次操作后的数组。
分析：
组合数做法：
比如当N=4，K=4的时候
（建议缩小一下看）
k=0 : a[1] a[2] a[3] a[4]
k=1: a[1] a[1]+a[2] a[1]+a[2]+a[3] a[1]+a[2]+a[3]+a[4]
k=2: a[1] 2*a[1]+a[2] 3*a[1]+2*a[2]+ a[3] 4*a[1]+3*a[2]+2*a[3]+a[4]
k=3: a[1] 3*a[1]+a[2] 6*a[1]+3*a[2]+ a[3] 10*a[1]+6*a[2]+3*a[3]+a[4]
k=4: a[1] 4*a[1]+a[2] 10*a[1]+4*a[2]+a[3] 20*a[1]+10*a[2]+4*a[3]+a[4]
1
4 1
10 4 1
20 10 4 1
只需要得到这个矩阵就可以了，可以发现是一个组合数C(i+k-1,i)(数组下标从0开始）
比如20=C(6,3) 10=C(5,2) 4=C(4,1) 1=C(3,0)
矩阵快速幂做法：
1 1 1 1
0 1 1 1
0 0 1 1
0 0 0 1
对其矩阵四次方可以得到
1 4 10 20
0 1 4 10
0 0 1 4
0 0 0 1我们发现第一行就是上面的结论，
所以对于整个矩阵真正有意义的值只是最上面一行。所以我们就可以考虑把矩阵压缩成一个1＊N的矩阵。所以我们要解决的核心问题就是实现压缩后矩阵的乘法运算。 利用每条与主对角线平行的斜线上的值是相等这一性质，我们就可以按照普通矩阵乘法的计算方式找到在压缩后矩阵对应值的位置写乘法(具体见代码）。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MOD 1000000007
#define N 500005
LL inv[N],c[N],a[N];
//预处理逆元 i (i<N)关于MOD的逆元
void getinv()
{inv[0]=inv[1]=1;for(int i=2; i<N; i++)inv[i]=((-MOD/i*inv[MOD%i])%MOD+MOD)%MOD;
}
//计算C(n,m)
LL slove(int n,int m)
{LL ans=1;for(int i=1; i<=m; i++)ans=((ans*inv[i])%MOD*(n-i+1))%MOD;return ans;
}
int main()
{int n,k;while(scanf("%d%d",&n,&k)!=EOF){for(int i=0; i<n; i++)scanf("%I64d",&a[i]);if(k==0){for(int i=0; i<n; i++)printf("%I64d ",a[i]);printf("\n");continue;}getinv();for(int i=0; i<n; i++)c[i]=slove(i+k-1,i);for(int i=0; i<n; i++){LL ans=0;for(int j=0; j<=i; j++)ans=(ans+a[j]*c[i-j])%MOD;printf("%I64d ",ans);}}return 0;
}#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define N 20005
ll a[N];
//上三角矩阵的压缩 乘法
/*1 1 1 10 1 1 10 0 1 10 0 0 1*/
ll temp[N];
void mul(ll *A,ll *B,int len)//矩阵A乘矩阵B，结果储存在A中
{memset(temp,0,sizeof(temp));for(int i=1;i<=len;++i)for(int j=1;j<=i;++j)temp[i]=(temp[i]+A[j]*B[i-j+1])%MOD;for(int i=1;i<=N;++i)A[i]=temp[i];
}
ll h[N];void pow(ll *A,ll b,int len)//矩阵快速幂，结果储存在A中
{for(int i=1;i<=len;++i)//初始矩阵赋值（需要计算的矩阵，注意为上三角矩阵h[i]=1;memset(temp,0,sizeof(temp));A[1]=1;//单位矩阵第一行，不要动while(b>0){if(b&1)mul(A,h,len);mul(h,h,len);b>>=1;}}
ll A[N];
int main()
{int n,k;while(scanf("%d%d",&n,&k)!=EOF){for(int i=1; i<=n; i++)scanf("%I64d",&a[i]);pow(A,k,n);for(int i=1; i<=n; i++){ll ans=0;for(int j=1; j<=i; j++)ans=(ans+a[i-j+1]*A[j])%MOD;printf("%I64d ",ans);}}return 0;
}