题目背景
这是一道 FFT 模板题
题目描述
给定一个 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) 的系数.
- #include<cmath>
- #include<cstdio>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- using namespace std;
- const double Pi=acos(-1);
- #define db double
- #define maxn 1350000
- inline int read(){
- register char ch=0;
- while(ch<48||ch>57)ch=getchar();
- return ch-'0';
- }
- int n,m;
- struct CP{
- CP (db xx=0,db yy=0){x=xx;y=yy;}
- db x,y;
- CP operator + (CP const &B)const
- {return CP(x+B.x,y+B.y);}
- CP operator - (CP const &B)const
- {return CP(x-B.x,y-B.y);}
- CP operator * (CP const &B)const
- {return CP(x*B.x-y*B.y,x*B.y+y*B.x);}
- }f[maxn<<1];
- int tr[maxn<<1];
- inline void fft(CP *f,bool flag){
- for(int i=0;i<n;i++)if(i<tr[i])swap(f[i],f[tr[i]]);
- for(int p=2;p<=n;p<<=1){
- int len=p>>1;
- CP tG(cos(2*Pi/p),sin(2*Pi/p));
- if(!flag)tG.y*=-1;
- for(int k=0;k<n;k+=p){
- CP buf(1,0);
- for(int l=k;l<k+len;l++){
- CP tt=buf*f[len+l];
- f[len+l]=f[l]-tt;
- f[l]=f[l]+tt;
- buf=buf*tG;
- }
- }
- }
- }
- signed main(){
- scanf("%d%d",&n,&m);
- for(int i=0;i<=n;i++)f[i].x=read();
- for(int i=0;i<=m;i++)f[i].y=read();
- for(m+=n,n=1;n<=m;n<<=1);
- for(int i=0;i<n;i++)
- tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
- fft(f,1);
- for(int i=0;i<n;i++)f[i]=f[i]*f[i];
- fft(f,0);
- for(int i=0;i<=m;i++)
- printf("%d",(int)(f[i].y/n/2+0.49));
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3348196.html