LOJ #108. 多項式乘法

題目描述

這是一道模板題。

輸入兩個多項式，輸出這兩個多項式的乘積。

輸入格式

第一行兩個整數 n nn 和 m mm，分別表示兩個多項式的次數。

第二行 n+1 n + 1n+1 個整數，分別表示第一個多項式的 0 00 到 n nn 次項前的繫數。

第三行 m+1 m + 1m+1 個整數，分別表示第二個多項式的 0 00 到 m mm 次項前的繫數。

輸出格式

一行 n+m+1 n + m + 1n+m+1 個整數，分別表示乘起來後的多項式的 0 00 到 n+m n + mn+m 次項前的繫數。

樣例

樣例輸入

1 2
1 2
1 2 1

樣例輸出

1 4 5 2

數據範圍與提示

0≤n,m≤105 0 \leq n, m \leq 10 ^ 50≤n,m≤10​5​​，保證輸入中的繫數大於等於 0 00 且小於等於 9 99。

顯示分類標簽

洛谷上過不了。

只好到這裡交咯

用遞歸實現的

關於FFT可以看這裡http://www.cnblogs.com/zwfymqz/p/8244902.html

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN=2*1e6+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const double Pi=acos(-1.0);
struct complex
{
    double x,y;
    complex (double xx=0,double yy=0){x=xx,y=yy;}
}a[MAXN],b[MAXN];
complex operator + (complex a,complex b){ return complex(a.x+b.x , a.y+b.y);}
complex operator - (complex a,complex b){ return complex(a.x-b.x , a.y-b.y);}
complex operator * (complex a,complex b){ return complex(a.x*b.x-a.y*b.y , a.x*b.y+a.y*b.x);}//不懂的看複數的運算那部分 
void fast_fast_tle(int limit,complex *a,int type)
{
    if(limit==1) return ;//只有一個常數項
    complex a1[limit>>1],a2[limit>>1];
    for(int i=0;i<=limit;i+=2)//根據下標的奇偶性分類
        a1[i>>1]=a[i],a2[i>>1]=a[i+1];
    fast_fast_tle(limit>>1,a1,type);
    fast_fast_tle(limit>>1,a2,type);
    complex Wn=complex(cos(2.0*Pi/limit) , type*sin(2.0*Pi/limit)),w=complex(1,0);
    //Wn為單位根，w表示冪
    for(int i=0;i<(limit>>1);i++,w=w*Wn)
        a[i]=a1[i]+w*a2[i],
        a[i+(limit>>1)]=a1[i]-w*a2[i];//利用單位根的性質，O(1)得到另一部分 
}
int main()
{
    int 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();
    int limit=1;while(limit<=N+M) limit<<=1;
    fast_fast_tle(limit,a,1);
    fast_fast_tle(limit,b,1);
    //後面的1表示要進行的變換是什麼類型
    //1表示從繫數變為點值
    //-1表示從點值變為繫數
    //至於為什麼這樣是對的，可以參考一下c向量的推導過程
    for(int i=0;i<=limit;i++)
        a[i]=a[i]*b[i];
    fast_fast_tle(limit,a,-1);
    for(int i=0;i<=N+M;i++) printf("%d ",(int)(a[i].x/limit+0.5)); 
    return 0;
}