loj #108. 多项式乘法
2024-10-20 13:47:23
#108. 多项式乘法
题目描述
这是一道模板题。
输入两个多项式,输出这两个多项式的乘积。
输入格式
第一行两个整数 n nn 和 m mm,分别表示两个多项式的次数。
第二行 n+1 n + 1n+1 个整数,分别表示第一个多项式的 0 00 到 n nn 次项前的系数。
第三行 m+1 m + 1m+1 个整数,分别表示第二个多项式的 0 00 到 m mm 次项前的系数。
输出格式
一行 n+m+1 n + m + 1n+m+1 个整数,分别表示乘起来后的多项式的 0 00 到 n+m n + mn+m 次项前的系数。
样例
样例输入
1 2
1 2
1 2 1
样例输出
1 4 5 2
数据范围与提示
0≤n,m≤105 0 \leq n, m \leq 10 ^ 50≤n,m≤105,保证输入中的系数大于等于 0 00 且小于等于 9 99。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define maxn 400010
#define PI (acos(-1.0))
using namespace std;
int rd[maxn];
struct node{
double x,y;
node(double a=,double b=):x(a),y(b){}
node operator + (const node &c)
{return node(x+c.x,y+c.y);}
node operator - (const node &c)
{return node(x-c.x,y-c.y);}
node operator * (const node &c)
{return node(x*c.x-y*c.y,x*c.y+y*c.x);}
node operator / (const double &c)
{return node(x/c,y/c);}
}a[maxn],b[maxn];
void fft(node *a,int n,int f){
node wn,w;int i;
for(int i=;i<=n;i++)
if(rd[i]>i)swap(a[i],a[rd[i]]);
for(int k=;k<n;k<<=){
wn=node(cos(PI/k),f*sin(PI/k));
for(int j=;j<n;j+=(k<<)){
for(w=node(,),i=;i<k;i++,w=w*wn){
node x=a[i+j];
node y=a[i+j+k]*w;
a[i+j]=x+y;
a[i+j+k]=x-y;
}
}
}
if(f==-)
for(int i=;i<=n;i++)a[i]=a[i]/n;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%lf",&a[i].x);
for(int i=;i<=m;i++)scanf("%lf",&b[i].x);
m=n+m,n=;int l=;
while(n<=m){n<<=,l++;}
for(int i=;i<=n;i++)rd[i]=(rd[i>>]>>)|((i&)<<(l-));
fft(a,n,);fft(b,n,);
for(int i=;i<=n;i++)a[i]=a[i]*b[i];
fft(a,n,-);
for(int i=;i<=m;i++)printf("%d ",(int)(a[i].x+0.5));
return ;
}
最新文章
- bitset用法总结
- 获取WIFI密码
- java中采用dom4j解析xml文件
- mysql group by后 拼接某一字段
- Pyhton 单行、多行注释符号使用方法及规范
- c++学习笔记——聚合类
- php数据访问:pdo用法、事物回滚功能和放sql注入功能
- jenkins:应用篇(Gatling plugin的使用)
- DBHelper数据库操作类(二)
- PHP类中的__get()和__set函数到底有什么用?
- [时间操作] C#DateFormat时间帮助类 (转载)
- Javascript 设计模式笔记
- Silverlight 中MatrixTransform和其他Transform的数值转换
- FindPkgConfig----CMake的pkg-config模块
- ECMAscript6新特性之解构赋值
- eclipse 精确查询
- java面试之常见编程题
- OpenCV 求外接矩形以及旋转角度
- Consecutive Sum LightOJ - 1269(区间异或和)
- ICPC China Nanchang National Invitational -- D. Match Stick Game(dp)