记录编号	242137	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] 帕秋莉的超级多项式	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	36.974 s
提交时间	2016-03-26 16:35:01	内存使用	32.64 MiB

#define maxn 530010ul

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>

#define ll long long

int G,P=119*(1<<23)+1;

namespace polynomial{
    int ksm(int p,int k,int mod){
        int ans=1;
        while(k){
            if(k&1) ans=1ll*ans*p%mod;
            k>>=1ll,p=1ll*p*p%mod;
        }
        return ans;
    }
    /*

        & fast number theory transform .

        -> obvious .

        -> T(n) = O(n) + 2 * T( n / 2 ) = O( n*log(n) )

    */
   void ntt(int *a,int n,int flag){
        for(int i=0,j=0;i<n;i++){
            if(i>j) std::swap(a[i],a[j]);
            for(int t=n>>1;(j^=t)<t;t>>=1);
        }
        int w,wn,u,t;
        for(int m=2;m<=n;m<<=1){
            wn=ksm(G,flag==1?(P-1)/m:(P-1-(P-1)/m),P),w=1ll;
            for(int i=0;i<n;i+=m,w=1ll) for(int k=0,p=m>>1;k<p;k++,w=1ll*w*wn%P)
                t=1ll*w*a[i+k+p]%P,u=a[i+k],a[i+k]=(u+t)%P,a[i+k+p]=(u-t)%P;
        }
        if(flag==-1){
            int inv=ksm(n,P-2,P);
            for(int i=0;i<n;i++) a[i]=1ll*a[i]*inv%P;
        }
        return;
    }
    /*

        &polynomial derivative

        -> obvious .

        -> T(n) = O(n)

    */
    void poly_derivative(int *poly,int *der,int n){
        poly[n]=0;
        for(int i=0;i<n;i++) der[i]=1ll*(i+1)*poly[i+1]%P;
        return;
    }
    /*

        &polynomial integrate

        -> obvious .

        -> T(n) = O(n)

    */
    void poly_integrate(int *poly,int n){
        static int tmp[maxn];tmp[0]=0;
        for(int i=0;i<n;i++) tmp[i+1]=1ll*poly[i]*ksm(i+1,P-2,P)%P;
        for(int i=0;i<n;i++) poly[i]=(tmp[i]%P+P)%P;
        return;
    }
    /*

        & polynomial inverse

        -> G(x) * F(x) = 1 ( mod x^n )
        -> H(x) * F(x) = 1 ( mod x^2n )

        -> we want to know -> H(x)

        -> G(x) * F(x) - 1 =0 ( mod x^n )
        -> [G(x) * F(x) - 1] ^ 2 = 0 ( mod x^2n )
        -> [G(x)F(x)] ^ 2 - 2 * G(x) * F(x) + 1 = 0 ( mod x^2n )
        -> G(x) ^ 2 * F(x) - 2 * G(x) + H(x) = 0 ( mod x^2n )
        -> H(x) = 2 * G(x) - G(x) ^ 2 * F(x)

        -> H(x) = G(x) * [ 2 - G(x) * F(x) ]

        -> T(n) = O( n*log(n) ) + T( n / 2 ) = O( n*log(n) )

    */
    void poly_inverse(int *f,int *g,int n){
        static int tmp[maxn];
        if(n==1){g[0]=ksm(f[0],P-2,P);return;}
        poly_inverse(f,g,n>>1);
        memcpy(tmp,f,sizeof(f[0])*n);
        memset(tmp+n,0,sizeof(f[0])*n);
        ntt(tmp,n<<1,1),ntt(g,n<<1,1);
        for(int i=0;i<(n<<1);i++) tmp[i]=1ll*g[i]*(2ll-1ll*g[i]*tmp[i]%P)%P;
        ntt(tmp,n<<1,-1);
        for(int i=0;i<n;i++) g[i]=tmp[i];
        memset(g+n,0,sizeof(g[0])*n);
        return;
    }
    /*

        & polynomial sqrt

        ->   G(x) ^ 2 = F(x) ( mod x^n )
        ->   H(x) ^ 2 = F(x) ( mod x^2n )

        ->   we want to know -> H(x)

        ->   G(x) ^ 2 - F(x) = 0 ( mod x^n )
        ->   [ G(x) ^ 2 - F(x) ] ^ 2 = 0 ( mod x^2n )
        ->   [ G(x) ^ 2 + F(x) ] ^ 2 = 4 * ( G(x) ^ 2 ) * F(x) ( mod x^2n )
        ->   [ (G(x) ^ 2 + F(x)) / ( 2 * G(x) ) ] ^ 2 = F(x) ( mod x^2n )

        ->   H(x) = (G(x) ^ 2 + F(x)) / ( 2 * G(x) )

        -> T(n) = O( n*log(n) ) + T( n / 2 ) = O( n*log(n) )

    */
    void poly_sqrt(int *f,int *g,int n){
        static int tmp[maxn],ginv[maxn];
        if(n==1){g[0]=(int)sqrt(f[0]);return;}
        int inv2=ksm(2,P-2,P);
        poly_sqrt(f,g,n>>1);
        memset(ginv,0,sizeof(ginv[0])*n);
        poly_inverse(g,ginv,n);
        memcpy(tmp,f,sizeof(f[0])*n);
        memset(tmp+n,0,sizeof(f[0])*n);
        ntt(tmp,n<<1,1),ntt(g,n<<1,1),ntt(ginv,n<<1,1);
        for(int i=0;i<(n<<1);i++) tmp[i]=1ll*inv2*(g[i]+1ll*tmp[i]*ginv[i]%P)%P;
        ntt(tmp,n<<1,-1);
        for(int i=0;i<n;i++) g[i]=tmp[i];
        memset(g+n,0,sizeof(g[0])*n);
        return;
    }
    /*

        & polynomial ln

        ->   F(x) = ln ( G(x) )
        ->   F'(x) = G'(x) / G(x)

        ->   F(x) = ∫( G'(x) / G(x) ) dx

        -> T(n) = O( n*log(n) ) + O(n) = O( n*log(n) )

    */
    void poly_ln(int *poly,int *ln,int n){
        static int der[maxn],inv[maxn];
        memset(inv,0,sizeof(inv[0])*(n<<1));
        memset(der,0,sizeof(der[0])*(n<<1));
        poly_inverse(poly,inv,n);
        poly_derivative(poly,der,n);
        ntt(der,n<<1,1),ntt(inv,n<<1,1);
        for(int i=0;i<(n<<1);i++)
            ln[i]=1ll*der[i]*inv[i]%P;
        ntt(ln,n<<1,-1);
        poly_integrate(ln,n);
        memset(ln+n,0,sizeof(ln[0])*n);
        memset(inv,0,sizeof(inv[0])*(n<<1));
        memset(der,0,sizeof(der[0])*(n<<1));
        return;
    }
    /*

        & polynomial exp

        -> F(x) = e ^ A(x)
        -> G( F(x) ) = ln( F(x) ) - A(x) = 0

        -> Newton Iteration.
        -> F0(x) under ( mod x ^ n )
        -> F(x) under ( mod x ^ (2n) )
        -> F(x) = F0(x) - ( ln( F0(x) ) - A(x) ) / ( 1 / F0(x) )

        -> F(x) = F0(x)( 1 - ln( F0(x) ) + A(x) ) ( mod x ^ (2n) )

        -> T(n) = O( n*log(n) ) + T( n / 2 ) = O( n*log(n) )

    */
    void poly_exp(int *poly,int *exp,int n){
        static int tmp[maxn];
        if(n==1){exp[0]=1;return;}
        poly_exp(poly,exp,n>>1);
        memset(tmp,0,sizeof(tmp[0])*n<<1);
        poly_ln(exp,tmp,n);
        for(int i=0;i<n;i++) tmp[i]=((i==0)+P-tmp[i]+poly[i])%P;
        ntt(tmp,n<<1,1),ntt(exp,n<<1,1);
        for(int i=0;i<(n<<1);i++) exp[i]=1ll*exp[i]*tmp[i]%P;
        ntt(exp,n<<1,-1);
        for(int i=0;i<n;i++) ((exp[i]%=P)+=P)%=P;
        memset(exp+n,0,sizeof(exp[0])*n);
        return;
    }
    /*

        & polynomial power

        -> F(x) ^ k ( mod x ^ n ) = exp ( k * ln( F(x) ) )

        -> T(n) = O( n*log(n) )

    */
    void poly_pow(int *poly,int n,int k){
        static int ln[maxn],exp[maxn];
        poly_ln(poly,ln,n);
        for(int i=0;i<n;i++) poly[i]=1ll*k*ln[i]%P;
        poly_exp(poly,exp,n);
        for(int i=0;i<n;i++) poly[i]=exp[i];
        return;
    }
    /*

        &primitive_root

        -> ord(m,a) = phi(m)
        -> a is the primitive root of m
            * if not :
                exist-> a ^ i = a ^ j ( mod p )
                -> a ^ ( i - j ) = 1 ( mod p )
                -> i - j < ord(m,a)
                -> it contradicts the assumption .

        -> judge x is the primitive_root of m
            phi(m) = PI( pi ^ ai )
            * if exist x ^ ( phi(m) / pi ) = 1 ( mod m )
                x is not a primitive_root of m
                *if is -> x ^ ( phi(m) / pi ) = 1 ( mod p )
                    -> ord(m,x) = n , n | phi(m)
                        * if n < phi(m)
                            exist pi ->  n | ( phi(m) / pi )
                            -> x ^ ( phi(m) / pi ) = 1
                            -> x ^ n = 1
                            -> x ^ ( n - phi(m) / pi ) = 1
                            -> n - phi(m) / pi < n
                            -> it contradicts the assumption .

    */
    bool primitive_root_judge(int x,int p){
        for(int i=2;i*i<=p;i++) if((p-1)%i==0&&ksm(x,(p-1)/i,p)==1)
            return false;
        return true;
    }
    int primitive_root(int p){
        if(p==2) return 1;
        int ans=2;
        for(;!primitive_root_judge(ans,p);++ans);
        return ans;
    }
}

void read(int &x){
    x=0;int c=getchar();
    while(c<'0'||c>'9') c=getchar();
    for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    return;
}

int n,k,len,F[maxn],sqrtF[maxn],lnv_sqrt[maxn],exp_[maxn],inv2[maxn],ln2[maxn],G_[maxn];

int main(){
	freopen("polynomial.in","r",stdin);
	freopen("polynomial.out","w",stdout);
	G=polynomial::primitive_root(P);
	read(n),read(k);
	for(int i=0;i<n;i++) read(F[i]);
	for(len=1;len<=n;len<<=1);
	polynomial::poly_sqrt(F,sqrtF,len);
	polynomial::poly_inverse(sqrtF,lnv_sqrt,len);
	polynomial::poly_integrate(lnv_sqrt,len);
	polynomial::poly_exp(lnv_sqrt,exp_,len);
	polynomial::poly_inverse(exp_,inv2,len);
	(inv2[0]+=1)%=P;
	polynomial::poly_ln(inv2,ln2,len);
	(ln2[0]+=1)%=P;
	polynomial::poly_pow(ln2,len,k);
	polynomial::poly_derivative(ln2,G_,n);
	for(int i=0;i<n;i++) printf("%d ",(G_[i]%P+P)%P);
    return 0;
}