P3803 【模板】多项式乘法[FFT]

2018-02-26

题目背景

这是一道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
3

1 2
1 2
1 2 1

输出样例#1：

1 4 5 2

说明

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

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

数据有一定梯度。

空间限制：256MB

模板

http://blog.miskcoo.com/2015/04/polynomial-multiplication-and-fast-fourier-transform

#include<bits/stdc++.h>
#define ll long long
using namespace std;
void qmax(int &x,int y) {if (x<y) x=y;}
void qmin(int &x,int y) {if (x>y) x=y;}
inline int read()
{
    char s;
    int k=0,base=1;
    while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
    if(s==EOF)exit(0);
    if(s=='-')base=-1,s=getchar();
    while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
    return k*base;
}
inline void write(int x)
{
    static char cnt,num[15];cnt=0;
    if (!x)
    {
        putchar('0');
        return;
    }
    for (;x;x/=10) num[++cnt]=x%10;
    for (;cnt;putchar(num[cnt--]+48));
}
const int maxn=1e7+100;
int n,m;
struct Complex
{
    double x,y;
    Complex() {x=0,y=0;}
    friend Complex operator + (const Complex &a,const Complex &b)
    {
        Complex c;
        c.x=a.x+b.x;
        c.y=a.y+b.y;
        return c;
    }
    friend Complex operator - (const Complex &a,const Complex &b)
    {
        Complex c;
        c.x=a.x-b.x;
        c.y=a.y-b.y;
        return c;
    }
    friend Complex operator * (const Complex &a,const Complex &b)
    {
        Complex c;
        c.x=a.x*b.x-a.y*b.y;
        c.y=a.x*b.y+a.y*b.x;
        return c;
    }
} a[maxn],b[maxn];
const double pi=acos(-1.0);
int limit,l,r[maxn<<1];
void FFT(Complex *A,int type)
{
    for (int i=0;i<limit;i++) if (i<r[i]) swap(A[i],A[r[i]]);
    for (int mid=1;mid<limit;mid<<=1)
    {
        Complex Wn;
        Wn.x=cos(pi/mid);
        Wn.y=type*sin(pi/mid);
        for (int R=mid<<1,j=0;j<limit;j+=R)
        {
            Complex w;
            w.x=1;w.y=0;
            for (int k=0;k<mid;k++,w=w*Wn)
            {
                Complex x=A[j+k],y=w*A[j+mid+k];
                A[j+k]=x+y;
                A[j+mid+k]=x-y;
            }
        }
    }
}
int main()
{
#ifdef ylx
    freopen("p3803.in","r",stdin);
    freopen("p3803.out","w",stdout);
#endif
    n=read();m=read();
    for (int i=0;i<=n;i++) a[i].x=read();
    for (int i=0;i<=m;i++) b[i].x=read();
    limit=1;l=0;
    while (limit<=n+m) limit<<=1,l++;
    for (int i=0;i<limit;i++) 
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    FFT(a,1);
    FFT(b,1);
    for (int i=0;i<=limit;i++) a[i]=a[i]*b[i];
    FFT(a,-1);
    for (int i=0;i<=n+m;i++)
        printf("%d ",(int)(a[i].x/limit+0.5));
    return 0;
}