多项式求逆/分治FFT 学习笔记-白红宇

多项式求逆/分治FFT 学习笔记

阅读量：7093 次

发布时间：2019-06-28

本文共 3098 字，大约阅读时间需要 10 分钟。

一、多项式求逆

给定一个多项式 $F(x)$，请求出一个多项式 $G(x)$，满足 $F(x) * G(x) \equiv 1 ( \mathrm{mod\:} x^n )$。系数对 $998244353$取模。

考虑递归求解，当$F$的最高次为$0$时，$G_0=F_0^{-1}$

假设我们知道了$F(x)$在模$x^{\left \lceil \frac{n}{2}\right \rceil}$意义下的逆元$G'$

那么$F∗G′≡1(\mathrm{mod\:} x^{\left \lceil \frac{n}{2}\right \rceil})$且$F∗G≡1(\mathrm{mod\:} x^{\left \lceil \frac{n}{2}\right \rceil})$

因此 $G-G'\equiv 0(\mathrm{mod\:} x^{\left \lceil \frac{n}{2}\right \rceil})$

然后两边平方：$(G-G')^2\equiv 0(\mathrm{mod\:} x^n)$

所以$G^2-2GG'+G'^2\equiv0(\mathrm{mod\:} x^n)$

通乘$F$后，由于$F*G \equiv0(\mathrm{mod\:} x^n)$,所以$G-2G'+FG'^2\equiv0(\mathrm{mod\:} x^n)$

最后得到$G\equiv2G'-FG'^2(\mathrm{mod\:} x^n)$

总复杂度$O(n \log n)$

二、分治FFT

在求卷积的时候，如果后面的数字基于前面的数字，朴素的$FFT$就会退化至$O(n^2 \log n)$

考虑$cdq$分治

我们先求出$l \rightarrow mid$的答案，然后考虑它对$mid+1 \rightarrow r $的贡献。

显然，对于$mid+1 \rightarrow r$中$x$贡献是:

\[ \sum_{i=l}^{mid}f[i]g[x-i] \]

贡献可以用$FFT$计算

总复杂度$O(n \log n)$

Description

给定长度为 $n-1$的数组$ g[1],g[2],..,g[n-1]g[1],g[2],..,g[n−1]$，求 $f[0],f[1],..,f[n-1]f[0],f[1],..,f[n−1]$，其中

\[f[i]=\sum_{j=1}^if[i-j]g[j]\]

边界为 $f[0]=1$ 。答案模 $998244353$ 。

Code-多项式求逆版

由题可知：
\[ f*g=f-1 \]
所以：
\[ f\equiv(1-g)^{-1}(\mathrm{mod\:} x^n) \]
直接多项式求逆就可以啦

复杂度$O(n\log n)$

#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define swap(a,b) (a^=b^=a^=b)inline ll read(){    ll x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define mod 998244353#define g 3#define invg 332748118#define MN 2097152ll a[MN],b[MN],c[MN],N,di,invN;int pos[MN];bool now;inline ll fpow(ll x,int m){ll res=1;for(;m;m>>=1,x=x*x%mod) if(m&1)res=res*x%mod;return res;}inline void NTT(ll *a,int type){    register int i,j,p,k;    for(i=0;i
     
      
       0?g:invg,(mod-1)/(i<<1));        for(p=i<<1,j=0;j
       
        >1,a,b);    for(N=1,di=0;N<(n<<1);N<<=1,++di);    register int i;invN=fpow(N,mod-2);    for(i=0;i
        
         >1]>>1)|((i&1)<<(di-1));    for(i=0;i

Code-分治FFT版

复杂度$O(n\log^2 n)$

#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define mod 998244353#define g 3#define invg 332748118#define MN 262144ll G[MN],F[MN],N,di,pos[MN],A[MN],B[MN],invN;inline ll fpow(ll x,int m){ll res=1;for(;m;m>>=1,x=x*x%mod) if(m&1)res=res*x%mod;return res;}inline void NTT(ll *a,int type){    register int i,j,p,k;    for(i=0;i
     
      
       0?g:invg,(mod-1)/(i<<1));        for(p=i<<1,j=0;j
       
        >1,i,len=r-l+1;    cdqNTT(a,b,l,mid);        for(N=1,di=0;N
        
         <<1;N<<=1,++di);    for(i=0;i
         
          >1]>>1)|((i&1)<<(di-1)); invN=fpow(N,mod-2); for(i=0;i