51nod 1161 Partial Sums

给出一个数组A，经过一次处理，生成一个数组S，数组S中的每个值相当于数组A的累加，比如：A = {1 3 5 6} => S = {1 4 9 15}。如果对生成的数组S再进行一次累加操作，{1 4 9 15} => {1 5 14 29}，现在给出数组A，问进行K次操作后的结果。(每次累加后的结果 mod 10^9 + 7)

Input

第1行，2个数N和K，中间用空格分隔，N表示数组的长度，K表示处理的次数（2 <= n <= 5000, 0 <= k <= 10^9, 0 <= a[i] <= 10^9)

Output

共N行，每行一个数，对应经过K次处理后的结果。每次累加后mod 10^9 + 7。

Input示例

Output示例

1

5

14

29
————————————————————————
这题我们单独考虑矩阵乘法 我们发现 这个矩阵大概是长这样的
1 1 1 .... 1
0 1 1 ..... 1
0 0 1 ..... 1
0 0 0 ..... 1
然后观察发现 我们可以通过第一行直接推出下面的所有行
我们再考虑发现第一行每一位满足一定的条件
第i个=C（k+i-1,i-1)然后就可以nlogn+n^2直接推出最后的矩阵
然后在n^2矩阵乘法直接推出答案辣

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

const int M=5e3+,mod=1e9+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,k;

int s[M],ans[M];

int b[M][M];

LL inv(LL a,LL b){

    LL ans=;

    while(b){

        if(b&) ans=ans*a%mod;

        b>>=; a=a*a%mod;

    }return ans;

}

int main(){

    n=read(); k=read()-;

    for(int i=;i<=n;i++) s[i]=read()%mod;

    b[][]=; for(int i=;i<n;i++) b[][i+]=1LL*b[][i]*(k+i)%mod*inv(i,mod-)%mod;

    //for(int i=1;i<=n;i++) printf("[%d] ",b[1][i]); puts("");

    for(int i=;i<=n;i++){

        int cnt=;

        for(int j=i;j<=n;j++) b[i][j]=b[][++cnt];

    }

//    for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=n;j++) printf("[%d] ",b[i][j]);

    for(int i=;i<=n;i++)for(int j=;j<=n;j++) ans[i]=(ans[i]+1LL*s[j]*b[j][i]%mod)%mod;

    for(int i=;i<=n;i++) printf("%d\n",ans[i]);

    return ;

}

巴特西

51nod 1161 Partial Sums

最新文章

热门文章