【BZOJ】2194:高速フーリエの二

http://www.lydsy.com/JudgeOnline/problem.php?id=2194
求$c[k]=\sum_｛k<=i＜n｝a[i]b[i-k]n<=10^5$

#include <bits/stdc++.h>

using namespace std;

struct cp {

	double x, y;

	cp(double _x=0, double _y=0):x(_x),y(_y) {}

	cp operator+(const cp &a) { return cp(x+a.x, y+a.y); }

	cp operator-(const cp &a) { return cp(x-a.x, y-a.y); }

	cp operator*(const cp &a) { return cp(x*a.x-y*a.y, x*a.y+y*a.x); }

};

const int N=400005;

const double pi=acos(-1);

int rev[N];

void dft(cp *a, int n, int flag) {

	static cp A[N], u, v;

	static int i, j, m, mid;

	for(i=0; i<n; ++i) A[rev[i]]=a[i];

	for(i=0; i<n; ++i) a[i]=A[i];

	for(m=2; m<=n; m<<=1) {

		cp wn(cos(pi*2/m), sin(pi*2/m)*flag);

		for(i=0; i<n; i+=m) {

			mid=m>>1; cp w(1);

			for(j=0; j<mid; ++j) {

				u=a[i+j], v=a[i+j+mid]*w;

				a[i+j]=u+v;

				a[i+j+mid]=u-v;

				w=w*wn;

			}

		}

	}

	if(flag==-1) for(i=0; i<n; ++i) a[i].x/=n;

}

inline void init(int &len) {

	static int k, t, j, r; k=1; t=0;

	while(k<len) k<<=1, ++t;

	len=k;

	for(int i=0; i<len; ++i) {

		k=i; j=t; r=0;

		while(j--) r<<=1, r|=k&1, k>>=1;

		rev[i]=r;

	}

}

void fft(int *a, int *b, int *c, int la, int lb) {

	static cp x[N], y[N];

	int len=la+lb-1;

	init(len);

	for(int i=0; i<len; ++i) x[i].x=a[i], x[i].y=0;

	for(int i=0; i<len; ++i) y[i].x=b[i], y[i].y=0;

	dft(x, len, 1); dft(y, len, 1);

	for(int i=0; i<len; ++i) x[i]=x[i]*y[i];

	dft(x, len, -1);

	for(int i=0; i<len; ++i) c[i]=x[i].x+0.5;

}

int x[N], y[N], a[N], n;

int main() {

	scanf("%d", &n);

	for(int i=0; i<n; ++i) scanf("%d%d", &x[i], &y[i]);

	for(int i=0; i<n; ++i) a[i]=x[n-1-i];

	fft(y, a, x, n, n);

	for(int i=0; i<n; ++i) a[i]=x[n-1-i];

	for(int i=0; i<n; ++i) printf("%d
", a[i]);

	return 0;

}

　　
 
復習しました。・・・サイズが出てきて本当に素晴らしいです。しかし、なぜ私のfftは辛いですか？遅いですか？
まず複雑な置換==
$begin{align}c[k]=& \sum_｛k<=ij=i-kであれば、i=j+kです。
$c[k]= \sum_｛0==j<=n-k-1｝a[j+k]b[j]$
c'[n-k-1]=c[k]，T=n-k-1\Rightarrow k=n-1-Tを設定します。
$c'[T]=\sum_｛0==j==T｝a[n-1-(T-j)]b[j]$
最後に$a'[T-j]=a[n-1-(T-j)\Rightarrow a'[x]=a[n-1-x]を設定します。
そして、裸の畳み込み辛み＝