UOJ #34 多项式乘法-白红宇

UOJ #34 多项式乘法

阅读量：4625 次

发布时间：2019-06-09

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

题目链接：

　　保存一发FFT与NTT板子。

　　学习链接：

　　注意差值回来的时候不取反也是可以的，只不过需要把数组\(reverse\)一下(根据单位复数根的性质应该不难理解)

　　代码(FFT):

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)#define C complex
           
            #define maxn 300010#define pi (acos(-1))using namespace std;typedef long long llg;int n,m,L,R[maxn];C a[maxn],b[maxn];int getint(){ int w=0;bool q=0; char c=getchar(); while((c>'9'||c<'0')&&c!='-') c=getchar(); if(c=='-') c=getchar(),q=1; while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;}void fft(C *a){ for(int i=0;i
            
             >1]>>1)|((i&1)<<(L-1)); fft(a); fft(b); for(int i=0;i

　　代码(NTT):

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)#define maxn 300010#define mod 998244353using namespace std;typedef long long llg;const int g=3;int n,m,L,R[maxn],N;int a[maxn],b[maxn];int getint(){ int w=0;bool q=0; char c=getchar(); while((c>'9'||c<'0')&&c!='-') c=getchar(); if(c=='-') c=getchar(),q=1; while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;}int qpow(int x,int y){ int s=1; while(y){ if(y&1) s=1ll*s*x%mod; x=1ll*x*x%mod; y>>=1; } return s;}void ntt(int *a){ for(int i=0;i
           
            =mod) a[j+k]-=mod; a[j+i+k]=x-y; if(x
            
             >1]>>1)|((i&1)<<(L-1)); ntt(a); ntt(b); N=qpow(n,mod-2); for(int i=0;i