Artifact 893844b7e5ed0726e2e8aec1bc99558deed882c4

• File lib/doc/fft.txt
  • 2011-09-28 15:31:48 - part of checkin [a6b1fd4985] on branch trunk - 518 (user: kinaba) [annotate]

http://apps.topcoder.com/wiki/display/tc/SRM+518


以下のような関数を考える。

int[] xor_count(int[] a, int[] b, int N)
{
	int[] c = {0} * N;
	for(int i=0; i<N; ++i)
		for(int k=0; k<N; ++k)
			c[i ^ k] += a[i] * b[k];
	return c;
}

高速化。

int[] xor_count_ultra(int[] a, int[] b, int N)
{
	a = xor_pre(a);
	b = xor_pre(b);
	c = a * b; // element-wise product
	return xor_post(c);
}

このようになるマジカルな変換 xor_pre, xor_post が存在する。

N=1 の場合、pre : {x} --> {x}
N=2 の場合、pre : {x,y} --> {x-y, x+y}
  xor_count( {x,y}, {u,v} ) = {xu+yv, yu+xv}
  と {x-y, x+y} * {u-v, u+v} = {xu+yv-xu-xv, xu+yv+yu+xv}
  から確認できる。
一般にNが2のベキの場合、xorの作用するビットのパターンが再帰的なので
  pre( [X,Y] ) = [pre(X)-pre(Y), pre(X)+pre(Y)]
と再帰的にすれば成り立つ






xorでなくて足し算の場合

int[] plus_count(int[] a, int[] b, int N)
{
	int[] c = {0} * 2N;
	for(int i=0; i<N; ++i)
		for(int k=0; k<N; ++k)
			c[i + k] += a[i] * b[k];
	return c;
}

も同様に。

int[] plus_count_ultra(int[] a, int[] b, int N)
{
	a = plus_pre(a);
	b = plus_pre(b);
	c = a * b; // element-wise product
	return plus_post(c);
}

とできるのが FFT