Warning: session_start(): open(/tmp/sess_816dcca2f352590a07f27b136da30a36, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== FFT ======
补充板子
#include
#include
#include
#include
using namespace std;
const int MAXN=4000100;
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); //不懂的看复数的运算那部分
}
long long l,r[MAXN];
long long limit=1;
void fast_fast_tle(complex *A,int type) {
for(int i=0; i>n>>m;
for(int i=0; i<=n; i++) cin>>a[i].x;
for(int i=0; i<=m; i++) cin>>b[i].x;
while(limit<=n+m) limit<<=1,l++;
for(int i=0; i>1]>>1 )| ( (i&1)<<(l-1) ) ;
fast_fast_tle(a,1);
fast_fast_tle(b,1);
for(int i=0; i<=limit; i++) a[i]=a[i]*b[i];
fast_fast_tle(a,-1);
for(int i=0; i<=n+m; i++) c[i]=(long long)(a[i].x/limit+0.5);
for(int i=0; i<=n+m; i++) printf("%lld ",c[i]);
return 0;
}