UOJ 34 多项式乘法（FFT 快速傅里叶变换模板）

UOJ 34 多项式乘法

这是一道模板题。

给你两个多项式，请输出乘起来后的多项式。

输入格式

第一行两个整数 nn 和 mm ，分别表示两个多项式的次数。

第二行 n+1n+1 个整数，表示第一个多项式的 00 到 nn 次项系数。

第三行 m+1m+1 个整数，表示第二个多项式的 00 到 mm 次项系数。

输出格式

一行 n+m+1n+m+1 个整数，表示乘起来后的多项式的 00 到 n+mn+m 次项系数。

样例一

input

1 2
1 2
1 2 1

output

1 4 5 2

explanation

(1+2x)⋅(1+2x+x2)=1+4x+5x2+2x3(1+2x)⋅(1+2x+x2)=1+4x+5x2+2x3 。

限制与约定

0≤n,m≤1050≤n,m≤105 ，保证输入中的系数大于等于 00 且小于等于 99 。

时间限制：1s1s

空间限制：256MB

最最最最最最最原始的板子

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <complex>
#include <iostream>
using namespace std;

typedef complex<double> cd;     ///复数类的定义
const int maxx = 2094153;       ///nlongn的最大长度
const double pi = acos(-1.0);   ///圆周率

cd ar[maxx], br[maxx];          ///存储中间转换结果
int rev[maxx];                  ///存储二进制反转结果

///二进制转换位置，bit为最长的长度，必定是2的幂
void getrev (int bit)
{
    for (int i = 0; i < (1<<bit); i++)
    {
        rev[i] = (rev[i>>1]>>1)|((i&1)<<(bit-1));
    }
}

///a为转换后的数组，n是数组长度，dft是控制dft和idft
void fft (cd *a, int n, int dft)
{
    ///按照二进制翻转
    for (int i = 0; i < n; i++)
    {
        if (i < rev[i])
        {
            swap(a[i], a[rev[i]]);
        }
    }
    ///蝴蝶操作模拟合并过程
    for (int step = 1; step < n; step <<= 1)        ///模拟合并的次数
    {
        cd wn = exp(cd(0, dft*pi/step));            ///计算单位复根
        for (int j = 0; j < n; j += (step<<1))      ///模拟合并一次的组数
        {
            cd wnk(1, 0);                           ///每个独立序列都是从0开始的
            for (int k = j; k < j+step; k++)        ///模拟合并的每一组
            {
                cd x = a[k];
                cd y = wnk*a[k+step];
                a[k] = x+y;
                a[k+step] = x-y;
                wnk *= wn;                          ///计算下一次复根
            }
        }
    }
    ///idft的情况
    if (dft == -1)
    {
        for (int i = 0; i < n; i++)
        {
            a[i] /= 1.0*n;
        }
    }
}

int output[maxx];           ///输出
int l1,l2;

int main ()
{
    while(scanf("%d%d", &l1, &l2)!=EOF)///两个多项式的次数
    {
        memset(ar,0,sizeof(ar));
        memset(br,0,sizeof(br));
        memset(rev,0,sizeof(rev));
        memset(output,0,sizeof(output));
        l1++;
        l2++;
        for(int i=0; i<l1; i++)///从0到最高项
        {
            scanf("%lf",&ar[i]);
        }
        for(int i=0; i<l2; i++)///从0到最高项
        {
            scanf("%lf",&br[i]);
        }
        int bit = 1, s = 2;     ///bit表示数组的二进制位数，s表示分割的长度
        for (bit = 1; (1<<bit) < l1+l2-1; bit++)
        {
            s <<= 1;            ///找到一个2的整数次幂可以容纳这两个串的乘积
        }
        ///转换数组模拟
        getrev(bit);
        ///分别DFT
        fft(ar, s, 1);
        fft(br, s, 1);
        ///对应相乘
        for (int i = 0; i < s; i++)
        {
            ar[i] *= br[i];
        }
        ///进行IDFT
        fft(ar, s, -1);
        ///存入输出数组
        for (int i = 0; i < s; i++)
        {
            output[i] += (int)(ar[i].real()+0.5);
        }
        for (int i=0; i < l1+l2-1; i++)///从0到最高项的系数
        {
            if(i)
                cout<<' ';
            printf("%d", output[i]);
        }
        cout<<'\n';
    }
    return 0;
}