[UOJ 0034] 多项式乘法

题解

FFT&NTT的模板题, 应该不用多说啥了吧OwO

FFT的讲解Rush了一晚上也没Rush出来OwO先放一波代码水一篇博(逃)

参考代码

GitHub

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 const int MAXN=;

 const int DFT=;

 const int IDFT=-;

 const double PI=acos(-);

 struct Complex{

     double real;

     double imag;

     Complex(double r=,double i=){

         this->real=r;

         this->imag=i;

     }

 };

 Complex operator+(Complex a,Complex b){

     return Complex(a.real+b.real,a.imag+b.imag);

 }

 Complex operator-(Complex a,Complex b){

     return Complex(a.real-b.real,a.imag-b.imag);

 }

 Complex operator*(Complex a,Complex b){

     return Complex(a.real*b.real-a.imag*b.imag,a.real*b.imag+a.imag*b.real);

 }

 Complex a[MAXN],b[MAXN],c[MAXN];

 int n;             //Length of a

 int m;             //Length of b

 int bln=;         //Binary Length

 int bct;           //Bit Count

 int len;           //Length Sum

 int rev[MAXN];     //Binary Reverse Sort

 void Initialize();

 void FFT(Complex*,int,int);

 int main(){

     Initialize();

     FFT(a,bln,DFT);

     FFT(b,bln,DFT);

     for(int i=;i<=bln;i++){

         c[i]=a[i]*b[i];

     }

     FFT(c,bln,IDFT);

     for(int i=;i<=len;i++){

         printf("%d ",int(c[i].real/bln+0.5));

     }

     putchar('\n');

     return ;

 }

 void FFT(Complex* a,int len,int opt){

     for(int i=;i<len;i++)

         if(i<rev[i])

             std::swap(a[i],a[rev[i]]);

     for(int i=;i<len;i<<=){

         Complex wn=Complex(cos(PI/i),opt*sin(PI/i));

         int step=i<<;

         for(int j=;j<len;j+=step){

             Complex w=Complex(,);

             for(int k=;k<i;k++,w=w*wn){

                 Complex x=a[j+k];

                 Complex y=w*a[j+k+i];

                 a[j+k]=x+y;

                 a[j+k+i]=x-y;

             }

         }

     }

 }

 void Initialize(){

     scanf("%d%d",&n,&m);

     len=n+m;

     while(bln<=len){

         bct++;

         bln<<=;

     }

     for(int i=;i<bln;i++){

         rev[i]=(rev[i>>]>>)|((i&)<<(bct-));

     }

     for(int i=;i<=n;i++){

         scanf("%lf",&a[i].real);

     }

     for(int i=;i<=m;i++){

         scanf("%lf",&b[i].real);

     }

 }

Backup

以及日常图包OwO