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

时间：2022-07-11 20:04:10

什么都别说了，咱心态已经炸了...

question

题目戳这里的说...

其实就是叫你求下面这个式子的导函数：

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

noteskey

其实是道板子题呢~

刚好给我们弄个多项式合集的说...

各种板子粘贴的不亦乐乎结果一交发现自己 T 掉了，心态爆炸

斗胆把 YYB 大仙的代码交上去发现 A 掉了...（会不会被棕掉丫）

然后调了半天代码甚至还加了更多的优化结果发现跑得还是巨慢无比...

然后继续查 bug ，发现各种函数里面都没有区别，函数运行速度也差不了多少

于是只剩 NTT 里面的锅了，于是两份代码各跑 30 遍 NTT 看了看，发现自己的代码比 YYB 大仙的慢三倍！ 然后各种心态爆炸...

于是终于怀疑起了最基本的函数： mul、inc、dec...

最后发现居然是 inc 和 dec 函数跑慢了！ 心态怎能不炸！多年的信仰丫~

本以为取模速度超级慢三目速度超级快，结果...啪啪打脸（好吧其实是取模相对加减乘除慢，三目相对 if 语句快）

于是...就把三目改成取模瞬间 A 了此题 TAT

长教训了（但是感觉 inc 和 dec 的写法都改不了了怎么办...在线等）

code

总之和那位大佬说的一样，这种题拿来练手 （抄板子） 还行，比赛里面出来就准备好锤子把出题人胖揍一顿吧...

//by Judge

#include<bits/stdc++.h>

#define Rg register

#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i)

#define ll long long

using namespace std;

const int mod=998244353;

const int iG=332748118;

const int M=3e5+3;

typedef int arr[M];

#ifndef Judge

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

#endif

char buf[1<<21],*p1=buf,*p2=buf;

inline int inc(int x,int y){return (x+y)%mod;}

inline int dec(int x,int y){return (x-y+mod)%mod;}

inline int Dec(int x,int y){return x<y?x-y+mod:x-y;}

inline int Inc(int x,int y){return x+y>=mod?x+y-mod:x+y;}

inline int mul(int x,int y){return 1ll*x*y%mod;}

inline int read(){ int x=0,f=1; char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;

} char sr[1<<21],z[20];int CCF=-1,Z;

inline void Ot(){fwrite(sr,1,CCF+1,stdout),CCF=-1;}

inline void print(int x,char chr=' '){

    if(CCF>1<<20)Ot();if(x<0)sr[++CCF]=45,x=-x;

    while(z[++Z]=x%10+48,x/=10);

    while(sr[++CCF]=z[Z],--Z);sr[++CCF]=chr;

} int n,k,d,limit; arr a,b,r[21],lg,inv,G[2];

inline int qpow(Rg int x,Rg int p=mod-2,Rg int s=1){

	for(;p;p>>=1,x=mul(x,x)) if(p&1) s=mul(s,x); return s;

}

inline void prep(int n){

	inv[1]=1; for(limit=1;limit<=n;limit<<=1);

	fp(i,2,limit) inv[i]=mul(mod-mod/i,inv[mod%i]);

	fp(d,1,19){ lg[1<<d]=d; fp(i,0,(1<<d)-1)

		r[d][i]=(r[d][i>>1]>>1)|((i&1)<<(d-1));

	}

	for(Rg int t=(mod-1)>>1,i=1,x,y;i<262144;i<<=1,t>>=1){

		x=qpow(3,t),y=qpow(iG,t),G[0][i]=G[1][i]=1;

		fp(k,1,i-1) G[1][i+k]=mul(G[1][i+k-1],x),G[0][i+k]=mul(G[0][i+k-1],y);

	}

}

inline void NTT(int* a,int tp){

	fp(i,0,limit-1) if(i<r[d][i]) swap(a[i],a[r[d][i]]);

	for(Rg int mid=1;mid<limit;mid<<=1){ int I=mid<<1;

		for(Rg int j=0,x,y;j<limit;j+=I) fp(k,0,mid-1)

			x=a[j+k],y=mul(G[tp][mid+k],a[j+k+mid]),

			a[j+k]=(x+y)%mod,a[j+k+mid]=(x-y+mod)%mod;

	}

	if(tp) return ; fp(i,0,limit-1) a[i]=mul(a[i],inv[limit]);

}

inline void init(Rg int n){ d=0;

	for(limit=1;limit<=n;limit<<=1)++d;

}

void Inv(int* a,int* b,int n){

	static arr C,D; if(n==1) return b[0]=qpow(a[0]),void();

	Inv(a,b,n>>1),init(n); fp(i,0,n-1) C[i]=a[i],D[i]=b[i];

	fp(i,n,limit-1) C[i]=D[i]=0; NTT(C,1),NTT(D,1);

	fp(i,0,limit-1) C[i]=mul(C[i],mul(D[i],D[i])); NTT(C,0);

	fp(i,0,n-1) b[i]=dec(inc(b[i],b[i]),C[i]); fp(i,n,limit-1) b[i]=0;

}

void Sqrt(int* a,int* b,int n){

	static arr D,F; if(n==1) return b[0]=sqrt(a[0]),void();

	Sqrt(a,b,n>>1); fp(i,0,n<<1) F[i]=0;

	Inv(b,F,n),init(n); fp(i,0,n-1) D[i]=a[i];

	fp(i,n,limit-1) D[i]=0; NTT(D,1),NTT(b,1),NTT(F,1);

	fp(i,0,limit-1) b[i]=mul(inc(b[i],mul(D[i],F[i])),inv[2]);

	NTT(b,0); fp(i,n,limit-1) b[i]=0;

	memset(D,0,limit<<2),memset(F,0,limit<<2);

}

inline void Direv(int* a,int* b,int n){

	fp(i,1,n-1) b[i-1]=mul(a[i],i); b[n-1]=b[n]=0;

}

inline void Inter(int* a,int* b,int n){

	fp(i,1,n-1) b[i]=mul(a[i-1],inv[i]); b[0]=0;

}

inline void Ln(int* a,int* b,int n){

	static arr A,B; Direv(a,A,n),Inv(a,B,n);

	init(n),NTT(A,1),NTT(B,1);

	fp(i,0,limit-1) A[i]=mul(A[i],B[i]);

	NTT(A,0),Inter(A,b,limit);

	memset(A,0,limit<<2),memset(B,0,limit<<2);

}

inline void Exp(int* a,int* b,int n){

	static arr F; if(n==1) return b[0]=1,void();

	Exp(a,b,n>>1),Ln(b,F,n),init(n);

	F[0]=dec(a[0]+1,F[0]); fp(i,1,n-1) F[i]=dec(a[i],F[i]);

	NTT(F,1),NTT(b,1); fp(i,0,limit-1) b[i]=mul(b[i],F[i]);

	NTT(b,0); fp(i,n,limit-1) b[i]=0; memset(F,0,limit<<2);

}

inline void Pow(int* a,int* b,int n,int k){

	static arr F; memset(F,0,n<<2),Ln(a,F,n);

	fp(i,0,n-1) F[i]=mul(F[i],k); Exp(F,b,n);

}

int main(){

#ifndef Judge

	freopen("polynomial.in","r",stdin);

	freopen("polynomial.out","w",stdout);

#else

	freopen("1.in","r",stdin);

	freopen("1.out","w",stdout);

#endif

	n=read(),k=read(),prep(n<<1);

	fp(i,0,n-1) a[i]=read(); int len;

	for(len=1;len<=n;len<<=1);

	Sqrt(a,b,len),memset(a,0,len<<2);

	Inv(b,a,len),memset(b,0,len<<2);

	Inter(a,b,n),memset(a,0,len<<2);

	Exp(b,a,len),memset(b,0,len<<2);

	Inv(a,b,len),memset(a,0,len<<2);

	b[0]=inc(b[0],1);

	Ln(b,a,len),memset(b,0,len<<2);

	a[0]=inc(a[0],1);

	Pow(a,b,len,k),memset(a,0,len<<2);

	Direv(b,a,n);

	fp(i,0,n-1) print(a[i]); return Ot(),0;

}

相关文章