UOJ 34 多项式乘法 FFT 模板
2024-08-28 22:34:37
这是一道模板题。
给你两个多项式,请输出乘起来后的多项式。
输入格式
第一行两个整数 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");
}
最新文章
- D3数据绑定
- SOAPUI使用教程-MockOperations和响应
- NYOJ题目839合并
- Ueditor配置及在项目中的使用
- Controller与View之间的数据传递
- ASP.NET实现IE下禁用浏览器后退按钮办法
- 用c++语言编写函数 int index(char *s,char * t),返回字符串t在字符串s中出现的最左边的位置,如果s中没有与t匹配的子串,则返回-1。类似于索引的功能。
- Spring Resources之介绍和资源接口
- 一个突发性的误解C# 引用类型
- 滚轮事件的防冒泡、阻止默认行为的代码(效果是:只让当前div滚动,连当前文档都不滚动的效果)
- Java9相关资料(JShell简易教程等)
- DS控件库 Win7链接列表框的仿Windows开始菜单样式
- Web Api Self-Host
- POJ 2533 - Longest Ordered Subsequence - [最长递增子序列长度][LIS问题]
- springMVC01,使用xml
- 如何让VB6代码编辑器垂直滚动条随鼠标滚轮滚动
- linux bash关闭标准输出1(exec 1<;&;-)后重新打开
- 【转】JavaScript 事件顺序:冒泡和捕获
- WINCRIS的使用
- [转]创建一个 Microsoft Outlook 扩展插件
热门文章
- 【Machine Learning&#183;机器学习】决策树之ID3算法(Iterative Dichotomiser 3)
- Maven从入门到放弃
- 前端笔记之微信小程序(三)GET请求案例&;文件上传和相册API&;配置https
- Shiro权限管理框架(三):Shiro中权限过滤器的初始化流程和实现原理
- 本地NTP服务器与客户端配置
- java-极光推送教程
- .NETCore C# 中级篇2-4 一文带你完全弄懂正则表达式
- 100天搞定机器学习|Day17-18 神奇的逻辑回归
- arukas 樱花免费docker容器获取IP和端口
- (十四)c#Winform自定义控件-键盘(一)