#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=5e6+5;
//复数类型
const double Pi=acos(-1.0); //π的值
struct complex { //复数类型
double x,y; //x为常数,y为sqrt(-1)的系数
complex (double xx=0,double yy=0) { x=xx,y=yy; }
} A[N],B[N];
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); } //复数乘法
int len,n,m,r[N],l;
//FFT 点值表示法与系数表示法的互换
void FFT(complex *A,int P) { //A为系数,P的解释见下面
for (int i=0; i<len; i++)
if (i<r[i]) swap(A[i],A[r[i]]); //求出迭代的序列
for (int mid=1; mid<len; mid<<=1) { //这次要合并的区间的长度的一半
complex Wn(cos(Pi/mid),P*sin(Pi/mid)); //用欧拉定理求单位根
for (int j=0; j<len; j+=(mid<<1)) { //(mid<<1)为区间长度,j为当前位置
complex w(1,0); //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() {
scanf("%d%d",&n,&m);
for (int i=0; i<=n; i++) scanf("%lf",&A[i].x); //代表A中x^0,x^1,x^2……的系数
for (int i=0; i<=m; i++) scanf("%lf",&B[i].x); //和A意义相似
len=1; while (len<=n+m) len<<=1,l++; //len为单位w的最大幂次方
for (int i=0; i<len; i++)
r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
//蝴蝶定理
// 在原序列中 i 与 i/2 的关系是 : i可以看做是i/2的二进制上的每一位左移一位得来
// 那么在反转后的数组中就需要右移一位,同时特殊处理一下奇数
FFT(A,1); FFT(B,1); //1表示从系数->点值,-1表示从点值->系数
for (int i=0; i<=len; i++) A[i]=A[i]*B[i]; //向量乘法
FFT(A,-1);
for (int i=0; i<=n+m; i++)
printf("%d ",(int)(A[i].x/len+0.5)); //四舍五入,这里除以len是因为公式(见附本)
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 17.096 ms | 152 MB + 648 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 81.823 ms | 155 MB + 52 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 47.545 ms | 153 MB + 416 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 46.801 ms | 153 MB + 404 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 18 ms | 152 MB + 648 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 17.091 ms | 152 MB + 648 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 18 ms | 152 MB + 648 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 76.128 ms | 154 MB + 808 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 75.792 ms | 154 MB + 808 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 69.686 ms | 154 MB + 540 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 82.019 ms | 155 MB + 132 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 82.232 ms | 154 MB + 12 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 17.136 ms | 152 MB + 648 KB | Accepted | Score: 0 | 显示更多 |