首页 > 其他 > 详细

【UOJ 34】多项式乘法

时间:2016-01-23 21:39:52      阅读:409      评论:0      收藏:0      [点我收藏+]

FFT模板

 

迭代的还没会 先写了个递归的

define的PI 我也是神了!!  少上一位就会WA

模板看的hzwer的

 

因为 PI较短【...】所以递归的跑的和迭代的一样快 23333333

 

 还差的几点:

1. acos要用

2.complex要自己写(yts1999大爷说会被卡)

3. 要改成迭代的

 

 

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <complex>
 4 #include <iostream>
 5 using namespace std;
 6 #define PI 3.14159265
 7 //const double PI =acos(-1);
 8 int n,m;
 9 complex<double> a[300000+1],b[300000+1];
10 
11 void FFT(complex<double> x[],int lenth,int type)
12 {
13     if(lenth==1return ;
14     complex<double> p[lenth/2],q[lenth/2];
15     for(int i=0;i<lenth;i++)
16     if(i&1) p[i/2]=x[i];
17     else q[i/2]=x[i];
18     FFT(q,lenth/2,type);
19     FFT(p,lenth/2,type);
20     complex <double> wn(cos(2*PI/lenth),sin(type*2*PI/lenth)),t,w(1,0);
21     for(int i=0;i<lenth/2;i++)
22     {
23         t=w*p[i];
24         x[i]=q[i]+t;
25         x[i+lenth/2]=q[i]-t;
26         w*=wn;
27     }
28 }
29 int main()
30 {
31     scanf("%d %d",&n,&m);int tmp;    
32 
33     for(int i=0;i<=n;i++) scanf("%d",&tmp),a[i]=tmp;
34     for(int i=0;i<=m;i++) scanf("%d",&tmp),b[i]=tmp;
35     m+=n;m++;
36     n=1;
37     for(;n<m;n*=2);
38     FFT(a,n,1);
39     FFT(b,n,1);
40     for(int i=0;i<n;i++) a[i]*=b[i];
41     FFT(a,n,-1);
42     for(int i=0;i<m;i++) printf("%d ",(int)(a[i].real()/n+0.5));
43     return 0;
44 }

 

【UOJ 34】多项式乘法

原文:http://www.cnblogs.com/ofsxb/p/5154038.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!