多项式求逆的解法看

我们考虑用分治

假设现在已经求出了$[l,mid]$的答案，要计算他们对$[mid+1,r]$的答案的影响

那么对右边部分的点$f_x$的影响就是$f_x+=\sum_{i=l}^{mid}f[i]g[x-i]$

发现右边那个东西可以用卷积快速计算

那么只要一边分治一边跑FFT统计贡献就行了

说是分治FFT实际上代码里写的是NTT……

而且分治FFT跑得好慢多项式求逆的速度是它的10倍啊……

1 //minamoto 2 #include
     
       3 #include
      
        4 #include
       
         5 using namespace std; 6 #define swap(x,y) (x^=y,y^=x,x^=y) 7 #define mul(x,y) (1ll*x*y%P) 8 #define add(x,y) (x+y>=P?x+y-P:x+y) 9 #define dec(x,y) (x-y<0?x-y+P:x-y)10 using namespace std;11 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)12 char buf[1<<21],*p1=buf,*p2=buf;13 inline int read(){14     #define num ch-'0'15     char ch;bool flag=0;int res;16     while(!isdigit(ch=getc()))17     (ch=='-')&&(flag=true);18     for(res=num;isdigit(ch=getc());res=res*10+num);19     (flag)&&(res=-res);20     #undef num21     return res;22 }23 char sr[1<<21],z[20];int C=-1,Z;24 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}25 inline void print(int x){26     if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;27     while(z[++Z]=x%10+48,x/=10);28     while(sr[++C]=z[Z],--Z);sr[++C]=' ';29 }30 const int N=400005,P=998244353;31 inline int ksm(int a,int b){32     int res=1;33     while(b){34         if(b&1) res=mul(res,a);35         a=mul(a,a),b>>=1;36     }37     return res;38 }39 int n,r[N],g[N],f[N],A[N],B[N],O[N],limit,l;40 inline void init(int len){41     limit=1,l=0;42     while(limit
        
         >1]>>1)|((i&1)<<(l-1));45 }46 void NTT(int *A,int type){47     for(int i=0;i
         
          >1;CDQ(a,b,l,mid);68     init(r-l+1);69     for(int i=0;i