UOJ 34 多项式乘法 FFT 模板

我不是女神ヾ 2021-12-20 23:55 186阅读 0赞

这是一道模板题。

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

### 输入格式 ###

第一行两个整数 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

AC代码：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #define N 2300003
    #define pi acos(-1)
    using namespace std;
    struct data{
    	double x,y;
    	data (double X=0,double Y=0) {
    		x=X,y=Y;
    	}
    }a[N],b[N],c[N];
    data operator +(data a,data b){  return data(a.x+b.x,a.y+b.y); }
    data operator -(data a,data b){  return data(a.x-b.x,a.y-b.y); }
    data operator *(data a,data b){  return data(a.x*b.x-a.y*b.y,a.y*b.x+b.y*a.x); }
    int n,m,L,R[N];
    char s[N];
    void fft(data a[N],int opt)
    {
    	for (int i=0;i<n;i++)
    	 if (i<R[i]) swap(a[i],a[R[i]]);
    	for(int i=1;i<n;i<<=1){
    		data wn=data(cos(pi/i),opt*sin(pi/i));
    		for (int p=i<<1,j=0;j<n;j+=p) {
    			data w=data(1,0);
    			for (int k=0;k<i;k++,w=w*wn){
    				data x=a[j+k],y=w*a[j+k+i];
    				a[j+k]=x+y; a[j+k+i]=x-y;
    			}
    		}
    	}
    }
    int main()
    {
    	//freopen("a.in","r",stdin);
    	scanf("%d%d",&n,&m);
    	for (int i=0;i<=n;i++) scanf("%lf",&a[i].x);
    	for (int i=0;i<=m;i++) scanf("%lf",&b[i].x);
    	m=n+m;
    	for (n=1;n<=m;n<<=1) L++;
        for (int i=0;i<n;i++)
    	 R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));//位逆序置换
    	fft(a,1); fft(b,1);
    	for (int i=0;i<=n;i++) a[i]=a[i]*b[i];
    	fft(a,-1);
    	for (int i=0;i<=m;i++)
    	 printf("%d ",(int)(a[i].x/n+0.5));
    	printf("\n");
    }

转载于:https://www.cnblogs.com/l609929321/p/9549225.html