bzoj2194 快速傅立葉之二

NO IMAGE

Description


請計算C[k]=∑a[i]∗b[i−k]” role=”presentation”>C[k]=∑a[i]∗b[i−k]C[k]=∑a[i]∗b[i−k]C[k]=\sum{a[i]*b[i-k]} 其中 k < = i < n ,並且有 n < = 10 ^ 5。 a,b中的元素均為小於等於100的非負整數。

Solution


把a或b陣列倒過來裝,這樣下標和就是定值了,FFT套一波

Code


#include <stdio.h>
#include <string.h>
#include <complex>
#include <math.h>
#define rep(i,st,ed) for (int i=st;i<=ed;  i)
typedef std:: complex <double> com;
const double pi=3.1415926535897932;
const int N=262145;
com a[N],b[N];
void FFT(com *c,int len,int f) {
if (len==1) return ;
com wn(cos(2.0*pi/len),sin(2.0*f*pi/len)),w(1,0);
com c1[len/2],c2[len/2];
rep(i,0,len/2-1) {
c1[i]=c[i*2 0];
c2[i]=c[i*2 1];
}
FFT(c1,len/2,f); FFT(c2,len/2,f);
for (int i=0;i<len/2;  i,w*=wn) {
com tmp=c2[i]*w;
c[i]=c1[i] tmp;
c[i len/2]=c1[i]-tmp;
}
}
int main(void) {
int n; scanf("%d",&n);
rep(i,0,n-1) {
scanf("%lf%lf",&a[i],&b[n-i 1]);
}
int m=n*2; n=1;
while (n<=m) n*=2;
FFT(a,n,1); FFT(b,n,1);
rep(i,0,n) a[i]*=b[i];
FFT(a,n,-1);
rep(i,m/2 1,m) {
printf("%d\n", (int)(a[i].real()/n 0.5));
}
return 0;
}