模拟考某题一开始由于校内OJ太慢直接拆系数FFT跑不过

后来被神仙婊了一顿之后发现复杂度写炸了改了改随便过

模版题：

---

三模数NTT

常数巨大，跑的极慢

---

拆系数FFT

原理是对于两个多项式$ P=\sum\limits_{i=0}^{n-1}P_ix^i \ \ Q=\sum\limits_{i=0}^{m-1}Q_ix^i$

直接$ FFT$计算会发现值域达到$ 10^{23}$会炸精度

设

$ A=\sum\limits_{i=0}^{n-1}(P_i>>15)x^i \ \ B=\sum\limits_{i=0}^{n-1}(P_i\&32767)x^i$

$ C=\sum\limits_{i=0}^{m-1}(Q_i>>15)x^i \ \ D=\sum\limits_{i=0}^{m-1}(Q_i\&32767)x^i$

我们只要求$ (A*C)<<30,(B*C+A*D)<<15,B*D$这三项的和即可

设一次$ DFT/IDFT$为一次操作

暴力实现需要进行$ 8$次操作

---

精度问题 

如果用$ k$次乘法计算$ w_n^k$会损失大量精度

需要利用三角函数预处理单位根，这样可以用$ double$代替$ long \ double$

---

优化

参考myy的2016年集训队论文

合并$DFT$

设我们要计算$ DFT_A$和$DFT_B$

令$$ P(x)=A(x)+iB(x) \\ Q(x)=A(x)-iB(x)$$

我们只要计算一次$ DFT_P$就可以推出$ DFT_Q$

推导请参考

有

$DFT_A[i]=\frac{DFT_P[i]+DFT_Q[i]}{2}$

$DFT_B[i]=\frac{DFT_P[i]-DFT_Q[i]}{2i}$

合并$IDFT$

同理

但这里甚至不需要求$ IDFT_Q$

事实上$IDFT_P$的实部和虚部分别对应$ IDFT_A$和$IDFT_B$

这样就把$ 8$次操作减少到$4$次了

---

代码 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define l putchar('\n')#define file(x)freopen(x".in","r",stdin);freopen(x".out","w",stdout)#define block 32768#define rt register int#define ll long longusing namespace std;inline ll read(){ ll x=0;char zf=1;char ch=getchar(); while(ch!='-'&&!isdigit(ch))ch=getchar(); if(ch=='-')zf=-1,ch=getchar(); while(isdigit(ch))x=x*10+ch-'0',ch=getchar();return x*zf;}void write(ll y){ if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);}void writeln(const ll y){write(y);putchar('\n');}int k,m,n,x,y,z,cnt,ans,p;namespace any_module_NTT{ vector
             
              R; const double PI=acos(-1.0); struct cp{ double x,y; cp operator +(const cp s)const{ return {x+s.x,y+s.y};} cp operator -(const cp s)const{ return {x-s.x,y-s.y};} cp operator *(const cp s)const{ return {x*s.x-y*s.y,x*s.y+y*s.x};} }w[18][1<<17]; void FFT(const int n,vector
              
               &A){ A.resize(n); for(rt i=0;i
               
                R[i])swap(A[i],A[R[i]]); for(rt i=1,s=0;i
                
                 <<=1,s++){ for(rt j=0;j
                 
                  <<1){ for(rt k=0;k
                  

Mul(vector

&x,vector

&y){ int sz=x.size()+y.size()-1,lim=1; while(lim<=sz)lim<<=1;R.resize(lim); for(rt i=0;(1<

AB(lim),CD(lim),AC(lim),BC(lim); for(rt i=1;i

>1]>>1)|(i&1)*(lim>>1); for(rt i=0;i

>15; for(rt i=0;i

>15; FFT(lim,AB);FFT(lim,CD); for(rt i=0;i