题解 P4721 【【模板】分治 FFT】

a2956331800

2019-01-05 21:49:15

Solution

生成函数 $$f[i]=\sum_{j=1}^if[i-j]*g[j],i>0$$ 设$f(x)=\sum\limits_{i=0}^\infty f[i]x^i,g(x)=\sum\limits_{i=0}^\infty g[i]x^i$(设$g[0]=0$) 发现把$f$和$g$卷积后$f$**常数项**没有了: $$f(x)*g(x)=\sum_{i=0}^\infty\sum_{j=0}^\infty f[i]\times g[j]x^{i+j}$$ 令$k=i+j$ $$f(x)*g(x)=\sum_{k=0}^\infty(\sum_{j=0}^kf[k-j]g[j])x^k$$ $k>0$时$\sum_{j=0}^kf[k-j]g[j]=f[k]$ $k=0$时$\sum_{j=0}^kf[k-j]g[j]=0$($g[0]=0$) 所以$f(x)*g(x)=\sum\limits_{k=1}^\infty f[k]x^k$,和$f(x)$对比一下发现就差了一个常数项 即$f(x)*g(x)+f[0]=f(x)$ 然后用初中数学知识(就是把未知数换成了多项式)就能算出来 $$f(x)=\frac{f[0]}{1-g(x)}$$ 多项式求逆就完了 ~~生成函数真是人类智慧做法~~ 代码(是个~~正在完善的~~多项式板子,什么$\ln \exp$都有可以拿去看) ```cpp #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #define md 998244353LL #define inv(x) power(x,md-2) #define max_n 1000000 using namespace std; int n,N,i; long long num[max_n],ans[max_n]; //const double pi=acos(-1); // //struct complex //{ // double x,y; // complex operator +(complex a) // { // return (complex){x+a.x,y+a.y}; // } // complex operator -(complex a) // { // return (complex){x-a.x,y-a.y}; // } // complex operator *(complex a) // { // return (complex){x*a.x-y*a.y,x*a.y+y*a.x}; // } // complex operator /(double a) // { // return (complex){x/a,y/a}; // } //}; long long power(long long a,long long n) { long long ans=1; while(n) { if(n&1) ans=ans*a%md; a=a*a%md; n>>=1; } return ans; } int re[max_n]; void build_re(int N) { int x,now=N>>1,len=0; while(now) len++,now>>=1; for(int i=0;i<N;i++) { x=i;now=0; for(int j=0;j<len;j++) now=(now<<1)|(x&1),x>>=1; re[i]=now; } } //void FFT(complex a[],int len,int opt) //{ // for(int i=0;i<len;i++) // if(i<re[i]) // swap(a[i],a[re[i]]); // complex wn,w,x; // for(int i=2;i<=len;i<<=1) // for(int j=(wn=(complex){cos(pi*2/i),opt*sin(pi*2/i)},0);j<len;j+=i) // for(int k=(w=(complex){1,0},0);k<i>>1;k++,w=w*wn) // x=w*a[j+k+(i>>1)],a[j+k+(i>>1)]=a[j+k]-x,a[j+k]=a[j+k]+x; // if(opt==-1) // for(int i=0;i<len;i++) // a[i]=a[i]/len; //} void NTT(long long a[],int len,int opt) { for(int i=0;i<len;i++) if(i<re[i]) swap(a[i],a[re[i]]); long long wn,w,x; for(int i=2;i<=len;i<<=1) for(int j=(wn=power(3,(md-1)/i),(opt==-1?wn=power(wn,md-2):0),0);j<len;j+=i) for(int k=(w=1,0);k<i>>1;k++,w=w*wn%md) x=a[j+k+(i>>1)]*w%md,a[j+k+(i>>1)]=(a[j+k]-x+md)%md,a[j+k]=(a[j+k]+x)%md; if(opt==-1) { long long inv=power(len,md-2); for(int i=0;i<len;i++) a[i]=a[i]*inv%md; } } //void poly_mul(long long a[],long long b[],long long tar[],int len) //{ // static long long A[4*max_n],B[4*max_n]; // memcpy(A,a,sizeof(long long)*len);memcpy(B,b,sizeof(long long)*len); // build_re(len); // NTT(A,len,1);NTT(B,len,1); // for(int i=0;i<len;i++) // tar[i]=A[i]*B[i]%md; // NTT(tar,len,-1); //} void poly_inv(long long a[],long long tar[],int len) { static long long now[4*max_n],ret[4*max_n]; memset(now,0,sizeof(long long)*len);memset(ret,0,sizeof(long long)*len); ret[0]=inv(a[0]); for(int i=2;i<=len;i<<=1) { build_re(i<<1); memcpy(now,a,sizeof(long long)*i); NTT(ret,i<<1,1);NTT(now,i<<1,1); for(int j=0;j<i<<1;j++) ret[j]=ret[j]*(2LL-now[j]*ret[j]%md+md)%md; NTT(ret,i<<1,-1); memset(ret+i,0,sizeof(long long)*i); } memcpy(tar,ret,sizeof(long long)*len); } //void poly_dir(long long a[],long long tar[],int len) //{ // for(int i=0;i<len-1;i++) // tar[i]=a[i+1]*(i+1)%md; //} //void poly_int(long long a[],long long tar[],int len) //{ // for(int i=len;i>=1;i--) // tar[i]=a[i-1]*inv(i)%md; // tar[0]=0; //} //void poly_ln(long long a[],long long tar[],int len) //{ // static long long now[4*max_n],ret[4*max_n]; // memset(now,0,sizeof(long long)*len);memset(ret,0,sizeof(long long)*len); // poly_inv(a,ret,len); // poly_dir(a,now,len); // poly_mul(now,ret,ret,len<<1); // poly_int(ret,ret,len); // memcpy(tar,ret,sizeof(long long)*len); //} //void poly_exp(long long a[],long long tar[],int len) //{ // static long long now[4*max_n],ret[4*max_n],ln[4*max_n]; // memset(now,0,sizeof(long long)*len);memset(ret,0,sizeof(long long)*len);memset(ln,0,sizeof(long long)*len); // ret[0]=1; // for(int i=2;i<=len;i<<=1) // { // poly_ln(ret,now,i); // for(int j=0;j<i;j++) // now[j]=(a[j]-now[j]+(j==0)+md)%md; // poly_mul(now,ret,ret,i<<1); // } // memcpy(tar,ret,sizeof(long long)*len); //} char Getchar() { return getchar(); static char buff[1000000],*p,*end=p; if(p==end) end=buff+fread(p=buff,1,1000000,stdin); return *(p++); } template<typename T>void read(T &x) { static char rc; x=0;rc=Getchar(); while(!isdigit(rc)) rc=Getchar(); while(isdigit(rc)) x=x*10+rc-'0',rc=Getchar(); } int main() { read(n);num[0]=1; for(i=1;i<n;i++) read(num[i]),num[i]=-num[i]; N=1; while(N<n) N<<=1; poly_inv(num,ans,N); for(i=0;i<n;i++) cout<<ans[i]<<' '; return 0; } ```