Luogu

Karry is God !!!

分析

考虑 $a_i$ 对 $sum_{k,1,r}$ 的贡献。显然左右独立，因此只考虑计算左边的方案数，即在 $i$ 个位置中放 $k-1$ 个左端点，因而左边的方案数为 $i+k-2\choose k-1$。类似地可以得到右边的方案数为 $r-i+k-1\choose k-1$。从而得到

$$ sum_{k,1,r}=\sum_{i=1}^ra_i\times{i+k-2\choose k-1}\times {r-i+k-1\choose k-1} $$

考虑构造卷积。简单推一推式子得到

$$ sum_{k,1,r}=\sum_{i=0}^{r-1}a_i{i+k-1\choose i}\times {r-i+k-2\choose r-i-1} $$

令

$$ F_i=a_i{i+k-1\choose i},G_i={i+k-1\choose i} $$

这样子就可以直接 NTT 了。

需要注意的是这个组合数是不太能直接算的，可以从 $i=0$ 开始递推出需要的部分。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int x=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*w;
}

const int N=300000+10;
const int mod=998244353;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,k,a[N],F[N],G[N];

int r[N];
void NTT(int* A,int n,int op) {
    for (int i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]);
    for (int i=1;i<n;i<<=1) {
        int rot=qpow(op==1?3:(mod+1)/3,(mod-1)/(i<<1));
        for (int j=0;j<n;j+=i<<1)
            for (int k=0,w=1;k<i;++k,w=1ll*w*rot%mod) {
                int x=A[j+k],y=1ll*w*A[j+k+i]%mod;
                A[j+k]=(x+y)%mod,A[j+k+i]=(x-y+mod)%mod;
            }
    }
    if (op==-1) { int inv=qpow(n,mod-2);
        for (int i=0;i<n;++i) A[i]=1ll*A[i]*inv%mod;
    }
}

int main() {
    n=read(),k=read();
    for (int i=0;i<n;++i) a[i]=read();
    G[0]=1;
    for (int i=1;i<n;++i) G[i]=1ll*G[i-1]*(i+k-1)%mod*qpow(i,mod-2)%mod;
    for (int i=0;i<n;++i) F[i]=1ll*a[i]*G[i]%mod;
    int lim=1,l=0;
    for (;lim<=n<<1;lim<<=1,++l);
    for (int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    NTT(F,lim,1),NTT(G,lim,1);
    for (int i=0;i<lim;++i) F[i]=1ll*F[i]*G[i]%mod;
    NTT(F,lim,-1);
    for (int i=0;i<n;++i) printf("%d%c",F[i]," \n"[i==n-1]);
    return 0;
}