题解 P4239 【【模板】多项式求逆（加强版）】
xzyxzy
2018-07-05 14:36:04
~~作为全站最短代码写个题解~~
首先多项式求逆，不会请见4938题解
然后这题模数不是NTT模数，MTT请见4245题解
所以两个多项式乘起来用MTT合并
但是我调试了两个小时，原因在于：**FFT由于不能取模，而double的位数有限，所以多项式算$AB^2$的时候，不能像NTT那样三个点值直接乘起来，会爆double，要乘完AB之后再乘B！**
另外我的MTT长得和大家的不一样，常数是他们的$\frac{8}{7}$，就是用时间长一点换代码短一点嘛
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<complex>
using namespace std;
const double Pi=acos(-1);
const int N=800100;
const int M=30000;
const int mod=1e9+7;
int n,F[N],G[N],l,r[N],tt,P1[N],P2[N];
complex<double> A1[N],A2[N],B1[N],B2[N],w[N],U[N];
int ksm(int x,int k)
{
int s=1;for(;k;k>>=1,x=1ll*x*x%mod)
if(k&1) s=1ll*s*x%mod; return s;
}
void FFT(complex<double> *P,int op)
{
for(int i=0;i<l;i++) if(i<r[i]) swap(P[i],P[r[i]]);
for(int i=1;i<l;i<<=1)
for(int j=0,p=i<<1;j<l;j+=p)
for(int k=0;k<i;k++)
{
complex<double> W=w[l/i*k];W.imag()*=op;
complex<double> X=P[j+k],Y=P[j+k+i]*W;
P[j+k]=X+Y;P[j+k+i]=X-Y;
}
}
void Work(complex<double> *A,complex<double> *B,int b)
{
for(int i=0;i<l;i++) U[i]=A[i]*B[i]; FFT(U,-1);
for(int i=0;i<l;i++) (P1[i]+=((long long)(U[i].real()/l+0.5)%mod*b%mod+mod)%mod)%=mod;
}
void MTT()
{
for(int i=0;i<l;i++) A1[i].real()=P1[i]/M,B1[i].real()=P1[i]%M,A1[i].imag()=B1[i].imag()=0;
for(int i=0;i<l;i++) A2[i].real()=P2[i]/M,B2[i].real()=P2[i]%M,A2[i].imag()=B2[i].imag()=0;
for(int i=0;i<l;i++) P1[i]=0; FFT(A1,1);FFT(A2,1);FFT(B1,1);FFT(B2,1);
Work(A1,A2,M*M);Work(A1,B2,M);Work(B1,A2,M);Work(B1,B2,1);
}
void GetInv(int *f,int *g,int n)
{
if(n==1) {g[0]=ksm(f[0],mod-2);return;}
GetInv(f,g,n>>1);
for(tt=0,l=1;l<n*2;l<<=1) tt++;tt--;
for(int i=0;i<l;i++) r[i]=(r[i>>1]>>1)|((i&1)<<tt),P1[i]=P2[i]=0;
for(int i=0;i<l;i++) w[i].real()=cos(Pi/l*i),w[i].imag()=sin(Pi/l*i);
for(int i=0;i<n;i++) P1[i]=f[i],P2[i]=g[i]; MTT(); MTT();
for(int i=0;i<n;i++) g[i]=((2ll*g[i]%mod-P1[i])%mod+mod)%mod;
}
int main()
{
scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&F[i]);
int m; for(m=1;m<n;m<<=1); GetInv(F,G,m);
for(int i=0;i<n;i++) printf("%d ",G[i]);
}
```
~~[打个广告：博主将会出一个多项式/NTT的总结以及题单](https://www.cnblogs.com/xzyxzy/)~~