admin 管理员组

文章数量: 886993

UR#34. 多项式乘法

#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

空间限制：256MB256MB

下载

样例数据下载

#include<cmath>
#include<cstdio>
#include<complex>
using namespace std;
typedef complex<double> E;
const double Pi=acos(-1);
const int N=3e5+10;
int n,m,L,R[N];
E a[N],b[N];
void FFT(E *a,int f){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){E wn(cos(Pi/i),f*sin(Pi/i));for(int p=i<<1,j=0;j<n;j+=p){E w(1,0);for(int k=0;k<i;k++,w*=wn){E x=a[j+k],y=w*a[j+k+i];a[j+k]=x+y;a[j+k+i]=x-y;}}}
}
int main(){scanf("%d%d",&n,&m);for(int i=0,x;i<=n;i++) scanf("%d",&x),a[i]=x;for(int i=0,x;i<=m;i++) scanf("%d",&x),b[i]=x;for(m+=n,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]*=b[i];FFT(a,-1);for(int i=0;i<=m;i++) printf("%d ",(int)(a[i].real()/n+0.5));return 0;
}
/*
比着敲完就算了，FFT理解，来日方长。
zky神犇写的非常详细
 
*/

 

转载于:.html

本文标签： UR34 多项式乘法

版权声明：本文标题：UR#34. 多项式乘法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732355446h1534302.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。