Artifact 893844b7e5ed0726e2e8aec1bc99558deed882c4
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