1449: 【快速傅里叶变换(模版题)】多项式乘法

时间限制: 1 Sec 内存限制: 256 MB
提交: 44 解决: 14
[提交][状态][讨论版]
题目描述

【题意】
给你两个多项式，请输出乘起来后的多项式。
【输入】
第一行两个整数 n 和 m，分别表示两个多项式的次数。1<=n,m<=10^5
第二行 n+1 个整数，分别表示第一个多项式的 0 到 n次项前的系数。
第三行 m+1 个整数，分别表示第一个多项式的 0 到 m 次项前的系数。
【输出】
一行 n+m+1 个整数，分别表示乘起来后的多项式的 0 到 n+m 次项前的系数。
【样例输入】
1 2
1 2
1 2 1

【样例输出】
1 4 5 2
本篇博客介绍的是迭代的方法，自己建立的Complex,较为重要的地方带有注释。

#include<iostream>
#include<cstdio>
using namespace std;
#include <cmath>
double PI =acos(-1);
const int MAXN =4*1e5+10;
int r[MAXN];
struct Complex
{
    double r,i;
    Complex(){}
    Complex(double _r,double _i){ r=_r,i=_i;}
    Complex operator +(const Complex &y){ return Complex(r+y.r,i+y.i);}
    Complex operator -(const Complex &y){return Complex(r-y.r,i-y.i);}
    Complex operator *(const Complex &y){return Complex(r*y.r-i*y.i,r*y.i+i*y.r);}
    Complex operator *=(const Complex &y){double t=r;r=r*y.r-i*y.i,i=t*y.i+i*y.r;}
 } a[MAXN],b[MAXN];
 void fft(Complex *a,int len,int op)
 {
    Complex tt;
    for(int i=0;i<len;i++)if(i<r[i])
     tt=a[i],a[i]=a[r[i]],a[r[i]]=tt;
     for(int i=1;i<len;i<<=1)//枚举需要合并的长度 合并后的长度就变成i*2了，所以无需枚举至len 
     {
        Complex wn(cos(PI/i),sin(PI*op/i));//无需乘2，因为合并后的长度i*2,用到的单位复数根只有i 
        for(int k=0,t=(i<<1);k<len;k+=t)//被分成了l/(i<<1)段序列 
        {
            Complex w(1,0);//注意一点，w是for循环执行完毕之后才累乘，因为我们还有我们还有w^0 
            for(int j=0;j<i;j++,w*=wn)//枚举前半部分，后半部分加上一个i就可以了 
            {
                Complex t=w*a[k+j+i];//k+j+i是后半部分 
                Complex u=a[k+j];//k+j是前半部分 
                a[k+j]=u+t;
                a[k+j+i]=u-t;
              }
          }
      }
      if(op==-1) for(int i=0;i<len;i++) a[i].r/=len,a[i].i/=len;//IFFT 每个数都要/len 
 }
 int main()
 {
    int n,m,L,i,x;
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)scanf("%lf",&a[i]);
    for(int i=0;i<=m;i++) scanf("%lf",&b[i]);
    m+=n;
    for(n=1,L=0;n<=m;n<<=1) L++; //把串变为2的幂次方 
     for(i=0,x=L-1;i<n;i++) r[i]=(r[i>>1]>>1) |((i&1)<<x);
     fft(a,n,1),fft(b,n,1);
     for(int i=0;i<n;i++) a[i]*=b[i];
     fft(a,n,-1);
     for(int i=0;i<=m;i++) printf("%d ",int(a[i].r+0.5));
     return 0;
 }