记录编号	251996	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] 帕秋莉的超级多项式	最终得分	100
用户昵称	葳棠殇	是否通过	通过
代码语言	C++	运行时间	32.172 s
提交时间	2016-04-19 07:45:41	内存使用	17.30 MiB

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define Mod 998244353
#define G 3
#define maxn 262300
int n,k,d;
int rev[maxn],inv[maxn];
char ch;
bool flag;
template<class T>void Read(T &x){
	flag=false;
	while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=true;x=ch^48;
	while(ch=getchar(),isdigit(ch))x=(x<<3)+(x<<1)+(ch^48);
}
namespace Polynomial{
    inline int Revbit(int x,int bit){int r=0;for(int i=0;i<bit;++i)if((x>>i)&1)r+=1<<(bit-1-i);return r;}
    int Qpow(int x,int y){int re=1;for(;y;y>>=1,x=1LL*x*x%Mod)if(y&1)re=1LL*re*x%Mod;return re;}
    void NTT(int *a,int n,int flag){
        int i,j,k,W,Wn,t,bit=0;
        for(int tmp=n;tmp^1;tmp>>=1)++bit;
        static int b[262300];
        for(i=0;i<n;i++)b[Revbit(i,bit)]=a[i];
        memcpy(a,b,sizeof(a[0])*n);
        for(k=2;k<=n;k<<=1)for(Wn=Qpow(G,1LL*(Mod-1)/k*flag%(Mod-1)),i=0;i<n;i+=k)for(W=1,j=0;j<k/2;j++,W=1LL*W*Wn%Mod)t=1LL*W*a[i+j+k/2]%Mod,a[i+j+k/2]=(a[i+j]+Mod-t)%Mod,a[i+j]=(a[i+j]+t)%Mod;
    }
	void Inv(int *a,int *b,int n){
        static int tmp[maxn];
        if(n==1){b[0]=Qpow(a[0],Mod-2);return;}
        Inv(a,b,n>>1),memcpy(tmp,a,sizeof(a[0])*n),memset(tmp+n,0,sizeof(a[0])*n);
        NTT(tmp,n<<1,1),NTT(b,n<<1,1);
        for(int i=0;i<(n<<1);i++)tmp[i]=1LL*b[i]*(2LL-1LL*tmp[i]*b[i]%Mod+Mod)%Mod;
        NTT(tmp,n<<1,Mod-2);
        for(int i=0;i<n;i++)b[i]=1LL*tmp[i]*inv[n<<1]%Mod;
        memset(b+n,0,sizeof(b[0])*n);
    }
	void Sqrt(int*a,int *b,int n){
        static int tmp[maxn],invb[maxn];
        if(n==1){b[0]=sqrt(a[0]);return;}
        Sqrt(a,b,n>>1),memset(invb,0,sizeof(a[0])*n),Inv(b,invb,n);
        memcpy(tmp,a,sizeof(a[0])*n),memset(tmp+n,0,sizeof(a[0])*n);
        NTT(tmp,n<<1,1),NTT(b,n<<1,1),NTT(invb,n<<1,1);
        for(int i=0;i<n<<1;i++)b[i]=1LL*inv[2]*(b[i]+1LL*invb[i]*tmp[i]%Mod)%Mod*inv[n<<1]%Mod;
		NTT(b,n<<1,Mod-2),memset(b+n,0,sizeof(b[0])*n);
    }
	void Derivative(int *a,int *b,int n){for(int i=0;i<n-1;i++)b[i]=1LL*a[i+1]*(i+1)%Mod;b[n-1]=0;}
	void Formula(int *a,int n){for(int i=n-1;i;i--)a[i]=1LL*a[i-1]*inv[i]%Mod;a[0]=0;}
	void ln(int *a,int *b,int n){
		static int a_[262300],a_inv[262300];
		Inv(a,a_inv,n),Derivative(a,a_,n),NTT(a_,n<<1,1),NTT(a_inv,n<<1,1);
		for(int i=0;i<n<<1;i++)b[i]=1LL*a_[i]*a_inv[i]%Mod*inv[n<<1]%Mod;
		NTT(b,n<<1,Mod-2),Formula(b,n);
		memset(b+n,0,sizeof(b[0])*n),memset(a_,0,sizeof(a_[0])*n<<1),memset(a_inv,0,sizeof(a_inv[0])*n<<1);
	}
	void Exp(int *a,int *b,int n){
        static int tmp[262300];
        if(n==1){b[0]=1;return;}
        Exp(a,b,n>>1),memset(tmp,0,sizeof(tmp[0])*n<<1),ln(b,tmp,n);
        for(int i=0;i<n;i++)tmp[i]=((i==0)+Mod-tmp[i]+a[i])%Mod;
        NTT(tmp,n<<1,1),NTT(b,n<<1,1);
        for(int i=0;i<n<<1;i++)b[i]=1LL*b[i]*tmp[i]%Mod;
        NTT(b,n<<1,Mod-2);
        for(int i=0;i<n;i++)b[i]=1LL*inv[n<<1]*b[i]%Mod;
        memset(b+n,0,sizeof(b[0])*n);
    }
	void Pow(int *a,int *b,int n,int k){
		static int tmpp[maxn];
		memset(tmpp,0,sizeof(tmpp)),ln(a,tmpp,n);
		for(int i=0;i<n;i++)tmpp[i]=1LL*tmpp[i]*k%Mod;
		Exp(tmpp,b,n),Derivative(b,b,n);
	}
};
int main(){
	using namespace Polynomial;
	freopen("polynomial.in","r",stdin);freopen("polynomial.out","w",stdout);
	static int A[maxn],As[maxn],AsI[maxn],AsID[maxn],AsIDE[maxn],AsIDEI[maxn],AsIDEIl[maxn],AsIDEIlP[maxn];
	Read(n),Read(k);
	for(d=1;d<=n;d<<=1);
	int i,x;
	for(inv[1]=1,i=2;i<=d<<1;i++)inv[i]=1LL*(Mod-Mod/i)*inv[Mod%i]%Mod;
	for(i=0;i<n;i++)Read(A[i]);
	Sqrt(A,As,d),Inv(As,AsI,d),Formula(AsI,d),Exp(AsI,AsIDE,d),Inv(AsIDE,AsIDEI,d);
	AsIDEI[0]++,AsIDEI[0]%=Mod,ln(AsIDEI,AsIDEIl,d),AsIDEIl[0]++,AsIDEIl[0]%=Mod,Pow(AsIDEIl,AsIDEIlP,d,k);
	for(int i=0;i<n-1;i++)printf("%d ",AsIDEIlP[i]);puts("0");
}