题解 P4726 【【模板】多项式指数函数】

多项式$Exp$模板题。 想做这道题先要知道[多项式Ln](https://www.luogu.org/problemnew/show/P4725)怎么写。 你可以看看[这个](https://www.luogu.org/blog/user7035/duo-xiang-shi-zong-jie)。 设$G(x)\equiv e^{F(x)}\pmod{x^n}$，$G_1(x)\equiv e^{F(x)}\pmod{x^{\lceil\frac{n}{2}\rceil}}$ 利用牛顿迭代公式可得 $$G=G_1(1-LnG_1+F)$$ 倍增求即可。注意倍增用的变量不能重复。 代码: ```cpp #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/priority_queue.hpp> #define For(i,a,b) for(i=(a);i<=(b);++i) #define Forward(i,a,b) for(i=(a);i>=(b);--i) #define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i) #define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i) using namespace std; inline void read(int &x) { static const int BUFSIZE = 1048576; static char buf[BUFSIZE]; static char *bufnow = buf; static char *bufmax = buf; if (bufnow == bufmax) { bufmax = buf + fread(buf, 1, BUFSIZE, stdin); bufnow = buf; } static int c; c = *bufnow++; for (;!isdigit(c);c = *bufnow++) { if (bufnow == bufmax) { bufmax = buf + fread(buf, 1, BUFSIZE, stdin); bufnow = buf; } } x = 0; for (;isdigit(c);c = *bufnow++) { x = (x << 1) + (x << 3) + c - 48; if (bufnow == bufmax) { bufmax = buf + fread(buf, 1, BUFSIZE, stdin); bufnow = buf; } } } inline void write(int a,char ed='\n') { static short s[13],tp; if(!a){putchar('0'),putchar(ed);return;} for(tp=0;a;a/=10)s[++tp]=a%10; for(;tp;putchar(s[tp--]^48)); putchar(ed); } void file(void){ freopen("polynomial.in","r",stdin); freopen("polynomial.out","w",stdout); } const int MAXN=1<<22; typedef long long ll; namespace polynomial { static int mod=998244353,gen=3,g[21],rev[MAXN],Len; inline int ad(int a,int b){return (a+=b)>=mod?a-mod:a;} inline int power(int a,int b) { static int sum; for(sum=1;b;b>>=1,a=(ll)a*a%mod)if(b&1) sum=(ll)sum*a%mod; return sum; } inline void predone() { static int i,j; for(i=1,j=2;i<=20;++i,j<<=1)g[i]=power(gen,(mod-1)/j); } inline void calrev(int Len) { static int Logl;Logl=(int)floor(log(Len)/log(2)+0.3)-1; Rep(i,1,Len-1)rev[i]=(rev[i>>1]>>1)|((i&1)<<Logl); } inline void NTT(int X[],int typ) { Rep(i,1,Len-1)if(i<rev[i])swap(X[i],X[rev[i]]); static int i,j,k,kk,w,t,wn,r; for(k=2,kk=1,r=1;k<=Len;k<<=1,kk<<=1,++r) { wn=g[r]; for(i=0;i<Len;i+=k)for(j=0,w=1;j<kk;++j,w=(ll)w*wn%mod) { t=(ll)w*X[i+j+kk]%mod; X[i+j+kk]=ad(X[i+j],mod-t); X[i+j]=ad(X[i+j],t); } } if(typ==-1) { reverse(X+1,X+Len); static int invn;invn=power(Len,mod-2); Rep(i,0,Len-1)X[i]=(ll)X[i]*invn%mod; } } static int x[MAXN],y[MAXN]; inline void mul(int a[],int b[]) { memset(x,0,sizeof x);memset(y,0,sizeof y); Rep(i,0,(Len>>1)-1)x[i]=a[i],y[i]=b[i]; NTT(x,1);NTT(y,1); Rep(i,0,Len-1)x[i]=(ll)x[i]*y[i]%mod; NTT(x,-1); Rep(i,0,Len-1)a[i]=x[i]; } static int c[2][MAXN]; static int A[MAXN],B[MAXN]; void Inv(int *a,int *b,int n) { if(n==1){b[0]=power(a[0],mod-2);return;} Inv(a,b,n>>1); Len=n<<1; calrev(Len); Rep(i,0,(Len>>1)-1)A[i]=a[i],B[i]=b[i]; NTT(A,1);NTT(B,1); Rep(i,0,Len-1)B[i]=(ll)B[i]*B[i]%mod*A[i]%mod; NTT(B,-1); Rep(i,0,(Len>>1)-1)b[i]=ad(b[i],ad(b[i],mod-B[i])); Rep(i,0,Len)A[i]=B[i]=0; } inline void Direv(int *a,int n) {Rep(i,1,n)a[i-1]=(ll)a[i]*i%mod;a[n]=0;} inline void Inter(int *a,int n) {Repe(i,n,1)a[i]=(ll)a[i-1]*power(i,mod-2)%mod;a[0]=0;} static int X[MAXN]; inline void Ln(int *a,int n) { Len=2; memset(X,0,sizeof X); while(Len<=n)Len<<=1; Inv(a,X,Len); Direv(a,n); while(Len<=(n<<2))Len<<=1; calrev(Len); mul(a,X); Inter(a,n); Rep(i,n+1,Len)a[i]=0; } static int T[MAXN],K[MAXN]; inline void Exp(int *a,int n) { static int t,z;t=0; memset(K,0,sizeof K);K[0]=1; Len=z=2; while(z<=(n<<1)) { z<<=1;t^=1; Rep(i,0,(z>>1)-1)T[i]=K[i]; Ln(T,(z>>1)-1); Rep(i,0,(z>>1)-1)T[i]=ad(a[i]+(i==0),mod-T[i]); calrev(Len=z); mul(K,T); Rep(i,z,z<<1)K[i]=T[i]=0; } Rep(i,0,n)a[i]=K[i]; } } using namespace polynomial; static int n,F[MAXN]; int main(void){ // file(); predone(); read(n); Rep(i,0,n-1)read(F[i]); Exp(F,n); Rep(i,0,n-1)write(F[i],' '); // cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl; return 0; } ``` ~~(因为常数问题卡了下常，顺便一说递归式比非递归式要快)~~