RT，爆零了/kk

屑代码

#include<bits/stdc++.h>
#define eps 1e-10
#define re register
#define N 501001
#define MAX 2001
#define inf 1e18
using namespace std;
typedef long long ll;
typedef double db;
const ll mod=1004535809,g=3;
inline void read(re ll &ret)
{
    ret=0;re ll pd=0;re char c=getchar();
    while(!isdigit(c)){pd|=c=='-';c=getchar();}
    while(isdigit(c)){ret=(ret<<1)+(ret<<3)+(c^48);c=getchar();}
    ret=pd?-ret:ret;
    return;
}
inline void readd(re ll &ret)
{
    ret=0;re ll pd=0;re char c=getchar();
    while(!isdigit(c)){pd|=c=='-';c=getchar();}
    while(isdigit(c)){ret=(ret<<1)%mod+(ret<<3)%mod+(c^48),ret%=mod;c=getchar();}
    ret=pd?mod-ret:ret;
    return;
}
ll n,k,t,a[N],inv[N],b[N],rev[N];
inline ll qpow(re ll a,re ll b)
{
    re ll ret=1;
    while(b)
    {
        if(b&1)
            ret*=a,ret%=mod;
        b>>=1;
        a*=a;
        a%=mod;
    }
    return ret;
}
inline ll getinv(re ll x)
{
    return qpow(x,mod-2);
}
inline void ntt(re ll a[],re ll len,re ll typ)
{
    re ll bit=0,num=1;
    while(num<len)
    {
        num<<=1;
        bit++;
    }
    for(re int i=0;i<len;i++)
    {
        rev[i]=(rev[i>>1]>>1)|((i&1)?(1<<(bit-1)):0);
        if(i<rev[i])
            swap(a[i],a[rev[i]]);
    }
    for(re int mid=1;mid<len;mid<<=1)
    {
        re ll wn=qpow((typ==1)?g:inv[g],(mod-1)/(mid<<1));
        for(re int i=0;i<len;i+=mid<<1)
        {
            re ll w=1;
            for(re int j=0;j<mid;j++,w=w*wn%mod)
            {
                re ll x=a[i+j],y=w*a[i+j+mid]%mod;
                a[i+j]=(x+y)%mod,a[i+j+mid]=(x-y+mod)%mod;
            }
        }
    }
    return;
}
signed main()
{
    read(n);
    readd(k);
    read(t);
    inv[1]=inv[0]=1;
    for(re ll i=1;i<=n;i++)
    {
        if(i>1)
            inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        read(a[i]);
    }
    inv[g]=getinv(g);
    b[0]=1;
    if(!t)
        for(re ll i=1;i<=n;i++)
            b[i]=b[i-1]*(k+i-1)%mod*inv[i]%mod;
    else
        for(re ll i=1;i<=n;i++)
            b[i]=-b[i-1]*(k-i+1)%mod*inv[i]%mod,b[i]=(b[i]+mod)%mod;
    re ll num=1;
    while(num<=n)
        num<<=1;
    ntt(a,num,1);
    ntt(b,num,1);
    for(re ll i=0;i<num;i++)
        a[i]=a[i]*b[i]%mod;
    ntt(a,num,-1);
    inv[num]=getinv(num);
    for(re ll i=1;i<=n;i++)
    {
        if(i>1)
            putchar(' ');
        printf("%lld",a[i]*inv[num]%mod);
    }
    putchar('\n');
    exit(0);
}