[COGS2189]帕秋莉的超级多项式(多项式全家桶)

原题传送门

Code

  直接上模板全套就好辣！（跑得还挺快，17.33s，现在在rk10）

#pragma GCC optimize(3,"Ofast","inline")
#include
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int mod=998244353,inv2=(mod+1)>>1;
namespace {inline int Add(const int &x,const int &y) {int res=x+y;if(res>=mod)res-=mod;return res;}inline int Sub(const int &x,const int &y) {int res=x-y;if(res<0)res+=mod;return res;}inline int Mul(const int &x,const int &y) {return 1ll*x*y%mod;}inline int Pow(int x,int y=mod-2) {int res=1;while(y) {if(y&1)res=1ll*res*x%mod;x=1ll*x*x%mod;y>>=1;}return res;}
}
const int fmaxn=18,Fmaxn=(1<5,G=3;
int nxtl[Fmaxn],nxtlim[Fmaxn],inv[Fmaxn];
namespace Poly {static int root[fmaxn][Fmaxn],mx,rev[Fmaxn];inline void Rev(int l) {rev[0]=0;for(int i=1;i<(1<>1]>>1)|((i&1)<<(l-1));}inline void DFT(vector<int>&a,int bit) {if(mxfor(int i=mx;iint len=1<1)/(len<<1)),w=1;for(int j=0;jfor(int i=1;i<1<if(ifor(int i=0,len=1;i1)for(int j=0;j<(1<1))for(int k=0;kint x=a[j+k],y=Mul(a[j+k+len],root[i][k]);a[j+k]=Add(x,y),a[j+k+len]=Sub(x,y);}}inline void IDFT(vector<int>&a,int bit) {int len=(1<1,a.end());DFT(a,bit);for(int i=0;iinline void FFT(vector<int>a,vector<int>b,vector<int>&c) {int la=a.size(),lb=b.size(),lc=la+lb-1,l=nxtl[lc],lim=nxtlim[lc];a.resize(lim),b.resize(lim),c.resize(lim);Rev(l),DFT(a,l),DFT(b,l);for(int i=0;iinline void Inv(vector<int>f,vector<int>&g,int len) {int lim=nxtlim[len];f.resize(lim),g.resize(lim);g[0]=Pow(f[0]);for(int i=2,p=1;i<=lim;i<<=1,++p) {vector<int>h(i<<1),l(i<<1),o(i<<1);for(int j=0;jfor(int j=0;j>1;++j)l[j]=g[j];Rev(p+1),DFT(h,p+1),DFT(l,p+1);for(int j=0;j1;++j)o[j]=Mul(h[j],Mul(l[j],l[j]));IDFT(o,p+1);for(int j=0;j2,g[j]),o[j]);}g.resize(len);}inline void Ln(vector<int>f,vector<int>&g,int len) {vector<int>h(len,0);for(int i=1;i1]=Mul(f[i],i);h[len-1]=0;Inv(f,g,len);FFT(g,h,g);for(int i=len-1;i;--i)g[i]=Mul(g[i-1],::inv[i]);g[0]=0;g.resize(len);}inline void Exp(vector<int>f,vector<int>&g,int len,int init) {int lim=nxtlim[len];f.resize(lim),g.resize(lim);if(init)g[0]=1;for(int i=2,p=1;i<=lim;i<<=1,++p) {vector<int>h(i<<1),l,o(i<<1,0);for(int j=0;j>1;++j)h[j]=g[j];Ln(h,l,i);for(int j=0;j0);Rev(p+1),DFT(h,p+1),DFT(l,p+1);for(int j=0;j1;++j)o[j]=Mul(h[j],l[j]);IDFT(o,p+1);for(int j=0;jinline void Pow(vector<int>f,vector<int>&g,int len,ll k) {vector<int>h;Ln(f,h,len);int o=k%mod;for(int i=0;i0],(int)(k%(mod-1))));Exp(h,g,len,0);}inline void Sqrt(vector<int>f,vector<int>&g,int len) {g.push_back((int)sqrt(f[0]));int lim=nxtlim[len];for(int i=2,p=1;i<=lim;i<<=1,++p) {vector<int>h(i),l,o(i<<1,0);g.resize(i<<1);for(int j=0;j1);for(int j=0;jint)f.size());++j)o[j]=f[j];Rev(p+1),DFT(g,p+1),DFT(l,p+1),DFT(o,p+1);for(int j=0;j1;++j)o[j]=Mul(Add(g[j],Mul(l[j],o[j])),inv2);IDFT(o,p+1);for(int j=0;jvector<int>a,b,c;
int n,m;
inline void Getmul() {a.clear(),b.clear();read(n),read(m);for(int i=0,x;i<=n;++i)read(x),a.push_back(x);for(int i=0,x;i<=m;++i)read(x),b.push_back(x);Poly::FFT(a,b,c);for(int i=0;i<(int)c.size();++i)printf("%d ",c[i]);
}
inline void Getinv() {a.clear();read(n);for(int i=0,x;ifor(int i=0;iprintf("%d ",b[i]);
}
inline void Getln() {a.clear();read(n);for(int i=0,x;ifor(int i=0;iprintf("%d ",b[i]);
}
inline void Getexp() {a.clear();read(n);for(int i=0,x;i1);for(int i=0;iprintf("%d ",b[i]);
}
inline void Getpow() {a.clear();ll p;read(n),read(p);for(int i=0,x;ifor(int i=0;iprintf("%d ",b[i]);
}
inline void Getsqrt() {a.clear();read(n);for(int i=0,x;ifor(int i=0;iprintf("%d ",b[i]);
}
int main() {freopen("polynomial.in","r",stdin);freopen("polynomial.out","w",stdout);nxtl[1]=0,nxtlim[1]=1,inv[1]=1;for(int i=1;i1;++i) {nxtl[i+1]=nxtl[i],nxtlim[i+1]=nxtlim[i];if(i==(i&-i))++nxtl[i+1],nxtlim[i+1]<<=1;}for(int i=2;i// Getmul();// Getinv();// Getln();// Getexp();// Getpow();// Getsqrt();read(n);ll p;read(p);for(int i=0,x;ifor(int i=n-1;i;--i)c[i]=Mul(c[i-1],inv[i]);c[0]=0;b.clear();Poly::Exp(c,b,n,1);c.clear();Poly::Inv(b,c,n);++c[0];b.clear();Poly::Ln(c,b,n);++b[0];c.clear();Poly::Pow(b,c,n,p);for(int i=1;i1]=Mul(c[i],i);c[n-1]=0;for(int i=0;iprintf("%d ",c[i]);puts("");return 0;
}

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