吴玉相简介,狂凤驭兽全文免费阅读,赵红霞列传
这是一道模板题。
输入两个多项式,输出这两个多项式的乘积。
第一行两个整数 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。
洛谷上过不了。
只好到这里交咯
用递归实现的
关于FFT可以看这里http://www.cnblogs.com/zwfymqz/p/8244902.html
#include<iostream> #include<cstdio> #include<cmath> using namespace std; const int MAXN=2*1e6+10; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } const double Pi=acos(-1.0); struct complex { double x,y; complex (double xx=0,double yy=0){x=xx,y=yy;} }a[MAXN],b[MAXN]; 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);}//不懂的看复数的运算那部分 void fast_fast_tle(int limit,complex *a,int type) { if(limit==1) return ;//只有一个常数项 complex a1[limit>>1],a2[limit>>1]; for(int i=0;i<=limit;i+=2)//根据下标的奇偶性分类 a1[i>>1]=a[i],a2[i>>1]=a[i+1]; fast_fast_tle(limit>>1,a1,type); fast_fast_tle(limit>>1,a2,type); complex Wn=complex(cos(2.0*Pi/limit) , type*sin(2.0*Pi/limit)),w=complex(1,0); //Wn为单位根,w表示幂 for(int i=0;i<(limit>>1);i++,w=w*Wn) a[i]=a1[i]+w*a2[i], a[i+(limit>>1)]=a1[i]-w*a2[i];//利用单位根的性质,O(1)得到另一部分 } int main() { int N=read(),M=read(); for(int i=0;i<=N;i++) a[i].x=read(); for(int i=0;i<=M;i++) b[i].x=read(); int limit=1;while(limit<=N+M) limit<<=1; fast_fast_tle(limit,a,1); fast_fast_tle(limit,b,1); //后面的1表示要进行的变换是什么类型 //1表示从系数变为点值 //-1表示从点值变为系数 //至于为什么这样是对的,可以参考一下c向量的推导过程 for(int i=0;i<=limit;i++) a[i]=a[i]*b[i]; fast_fast_tle(limit,a,-1); for(int i=0;i<=N+M;i++) printf("%d ",(int)(a[i].x/limit+0.5)); return 0; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论