CodeForces 223C Partial Sums 多次前缀和

Partial Sums

题解：

一个数列多次前缀和之后， 对于第i个数来说他的答案就是

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

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

                b[i] = (b[i] + 1ll * a[j] * C(k-+j-i,j-i)) % mod;

            }

        }

唯一注意的就是这个k会到1e9。

观察可能，其实我们最多也就用了n个组合数， 并且这个C(n, m) 的 m 足够小。

所以我们可以根据定义先把这几个组合数先预处理出来。

代码：

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const int _inf = 0xc0c0c0c0;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL _INF = 0xc0c0c0c0c0c0c0c0;

const LL mod =  (int)1e9+;

const int N = 2e3 + ;

int n, k;

int a[N], b[N];

int inv[N];

int c[N];

void init(){

    int MOD = mod;

    inv[] = ;

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

        inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;

    }

    c[] = ;

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

        c[i] = ;

        int now = k + i - ;

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

            c[i] = 1ll * c[i] * now % mod * inv[j] % mod;

            --now;

        }

    }

}

int main(){

    scanf("%d%d", &n, &k);

    for(int i = ; i <= n; ++i) scanf("%d", &a[i]);

    init();

    if(k){

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

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

                b[i] = (b[i] + 1ll * a[j] * c[i-j]) % mod;

            }

        }

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

            a[i] = b[i];

    }

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

        printf("%d%c", a[i], " \n"[i==n]);

    }

    return ;

}