P3803 【模板】多项式乘法（FFT）

注意：虽然本题开到3s，但是建议程序在1s内可以跑完，本题需要一定程度的常数优化。

题目描述

给定一个n次多项式F(x)，和一个m次多项式G(x)。

请求出F(x)和G(x)的卷积。

输入输出格式

输入格式：

第一行2个正整数n,m。

接下来一行n+1个数字，从低到高表示F(x)的系数。

接下来一行m+1个数字，从低到高表示G(x))的系数。

输出格式：

一行n+m+1个数字，从低到高表示F(x)∗G(x)的系数。

输入输出样例

输入样例#1： 复制

1 2
1 2
1 2 1

输出样例#1： 复制

1 4 5 2

说明

保证输入中的系数大于等于 0 且小于等于9。

对于100%的数据： $ n, m \leq {10}^6 $, 共计20个数据点，2s。

数据有一定梯度。

空间限制：256MB

快速傅里叶变换 Fast Fourier Transform(FFT)

各种资料都写得非常清楚，没有什么好说的。

然后总结了一下精度高，常数小（部分）的代码，体现在蝴蝶操作以及二进制翻转。

这里我封装了一下代码，然后TLE……开O2反复交卡进3s。

#8
AC
2923ms/78800KB


#9
AC
2949ms/81944KB

然后又是输出-0的问题。时间复杂度\(O(n\log n)\)

#include<bits/stdc++.h>
#define il inline
#define co const
template<class T>T read(){
    T data=0,w=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w;
    for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0';
    return data*w;
}
template<class T>il T read(T&x) {return x=read<T>();}
typedef long long LL;
using namespace std;
typedef vector<complex<double> > polynomial;

co double PI=acos(-1);
void Fourier_Transform(polynomial&a,int inverse){
    int limit=a.size(),len=log2(limit);
     // bit reserval
    vector<int> bit_rev(limit);
    for(int i=0;i<limit;++i) bit_rev[i]=bit_rev[i>>1]>>1|(i&1)<<len-1;
    for(int i=0;i<limit;++i)if(i<bit_rev[i]) swap(a[i],a[bit_rev[i]]);
    // Butterfly diagram
    for(int step=1;step<limit;step<<=1){
        double alpha=inverse*PI/step;
        for(int k=0;k<step;++k){
            complex<double> omega_k=exp(complex<double>(0,alpha*k));
            for(int even_k=k;even_k<limit;even_k+=step<<1){
                int odd_k=even_k+step;
                complex<double> t=omega_k*a[odd_k];
                a[odd_k]=a[even_k]-t,a[even_k]+=t;
            }
        }
    }
    if(inverse==-1)for(int i=0;i<limit;++i) a[i]/=limit;
}

int main(){
//  freopen("LG3803.in","r",stdin),freopen("LG3803.out","w",stdout);
    int n=read<int>(),m=read<int>();
    polynomial a(n+1),b(m+1);
    for(int i=0;i<=n;++i) read(a[i].real());
    for(int i=0;i<=m;++i) read(b[i].real());
    int limit=1;
    while(limit<n+m+1) limit<<=1;
    a.resize(limit),b.resize(limit);
    Fourier_Transform(a,1),Fourier_Transform(b,1);
    for(int i=0;i<limit;++i) a[i]*=b[i];
    Fourier_Transform(a,-1);
    for(int i=0;i<=n+m;++i) printf("%.0lf ",a[i].real()+1e-9); // edit 1:-0
    return 0;
}