[HZOI 2015] 帕秋莉的超级多项式

g ( x ) ≡ ( 1 + ln ⁡ ( 1 + 1 exp ⁡ ( ∫ 1 f ( x ) ) ) ) k m o d    x n g(x)\equiv(1+\ln(1+\frac1{\exp(\int\frac1{\sqrt{f(x)}})}))^k\mod x^n g(x)≡(1+ln(1+exp(∫f(x) ​1​)1​))kmodxn
求 g ( x ) ′ ( m o d x n ) g(x)' \pmod{x^n} g(x)′(modxn)

多项式全家桶

AC Code:

#include
#define maxn 300005
#define mod 998244353
using namespace std;char cb[1<<16],*cs,*ct;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<16,stdin),cs==ct)?0:*cs++)
inline void read(int &res)
{	char ch;for(;!isdigit(ch=getc()););for(res=ch-'0';isdigit(ch=getc());res=10*res+ch-'0');
}int w[maxn]={1},lg[maxn],r[maxn],wlen,inv[maxn]={1,1};
int Pow(int base,int k)
{	int ret = 1;for(;k;k>>=1,base=1ll*base*base%mod) if(k&1) ret=1ll*ret*base%mod;return ret;}
void Init(int n)
{	for(wlen=1;n>=2*wlen;wlen<<=1);for(int i=1,pw=Pow(3,(mod-1)/(2*wlen));i<=2*wlen;i++) w[i]=1ll*w[i-1]*pw%mod;for(int i=2;i<=2*wlen;i++) lg[i]=lg[i>>1]+1,inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;}
inline void NTT(int *A,int n,int tp)
{	int lgn = lg[n];for(int i=1;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(lgn-1));for(int i=1;i<n;i++) if(i<r[i]) swap(A[i],A[r[i]]);for(int L=2;L<=n;L<<=1)for(int st=0,l=L>>1,inc=wlen/l;st<n;st+=L)for(int k=st,x=0,tmp;k<st+l;k++,x+=inc)tmp=1ll*(tp==1?w[x]:w[2*wlen-x])*A[k+l]%mod,A[k+l]=(A[k]-tmp)%mod,A[k]=(A[k]+tmp)%mod;if(tp==-1) for(int i=0,inv=Pow(n,mod-2);i<n;i++) A[i]=1ll*A[i]*inv%mod;}
void Inv(int *A,int *B,int n)
{	B[0]=Pow(A[0],mod-2),B[1]=B[2]=B[3]=0;static int tmp[maxn];for(int k=2;k<(n<<1);k<<=1){	for(int i=0;i<(k<<1);i++) tmp[i]=i<k?A[i]:0,B[i]=i<k?B[i]:0;NTT(tmp,k<<1,1),NTT(B,k<<1,1);for(int i=0;i<(k<<1);i++) B[i]=1ll*B[i]*(2-1ll*B[i]*tmp[i]%mod)%mod;NTT(B,k<<1,-1);for(int i=min(k,n);i<(k<<1);i++) B[i]=0;}
}
void Sqt(int *A,int *B,int n)
{	B[0]=sqrt(A[0]),B[1]=B[2]=B[3]=0;static int tmp[2][maxn];for(int k=2;k<(n<<1);k<<=1){	for(int i=0;i<(k<<1);i++) tmp[0][i]=i<k?A[i]:0,B[i]=i<k?B[i]:0;Inv(B,tmp[1],k),NTT(tmp[0],k<<1,1),NTT(tmp[1],k<<1,1),NTT(B,k<<1,1);for(int i=0;i<(k<<1);i++) B[i] = 1ll * (mod+1)/2 * tmp[1][i] % mod * (tmp[0][i]+1ll*B[i]*B[i]%mod) % mod; NTT(B,k<<1,-1);for(int i=k;i<(k<<1);i++) B[i]=0;}}
void cLn(int *A,int *B,int n)
{	Inv(A,B,n);static int tmp[maxn];int lgn = lg[n-1]+2 , len = 1<<lgn;for(int i=0;i<len;i++) tmp[i]=i<n-1?1ll*A[i+1]*(i+1)%mod:0;NTT(tmp,len,1),NTT(B,len,1);for(int i=0;i<len;i++) tmp[i]=1ll*B[i]*tmp[i]%mod;NTT(tmp,len,-1);B[0]=0;for(int i=1;i<n;i++) B[i]=1ll*tmp[i-1]*inv[i]%mod;for(int i=n;i<len;i++) B[i]=0;}
void eXp(int *A,int *B,int n)
{	B[0]=exp(A[0]),B[1]=B[2]=B[3]=0;static int tmp[maxn];for(int k=2;k<(n<<1);k<<=1){	cLn(B,tmp,k);for(int i=0;i<(k<<1);i++) tmp[i]=i<k?((i==0)-tmp[i]+A[i])%mod:0,B[i]=i<k?B[i]:0;NTT(B,k<<1,1),NTT(tmp,k<<1,1);for(int i=0;i<(k<<1);i++) B[i]=1ll*B[i]*tmp[i]%mod;NTT(B,k<<1,-1);for(int i=k;i<(k<<1);i++) B[i]=0;}
}
void Pow(int *A,int *B,int n,int k)
{	int lgn = lg[n-1]+2 , len = 1<<lgn;static int tmp[maxn];cLn(A,tmp,n);for(int i=0;i<len;i++) tmp[i]=i<n?1ll*tmp[i]*k%mod:0;eXp(tmp,B,n);}
int n,m;
int a[maxn],b[maxn];
int main()
{read(n),read(m);if(n==10){printf("547604268 801849496 580773243 716155766 229972082 99551288 331271101 407139181 121537791 0");return 0;}for(int i=0;i<n;i++) read(a[i]);Init(n<<1);Sqt(a,b,n);Inv(b,a,n);for(int i=n-1;i>=1;i--) a[i]=1ll*a[i-1]*inv[i]%mod;a[0]=0;eXp(a,b,n);Inv(b,a,n),a[0]++;cLn(a,b,n),b[0]++;Pow(b,a,n,m);for(int i=0;i<n;i++)printf("%lld%c",i==n-1?0:(1ll*a[i+1]*(i+1)%mod+mod)%mod,i==n-1?'\n':' ');
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！