a6b1fd4985 2011-09-28        kinaba: 
a6b1fd4985 2011-09-28        kinaba: http://apps.topcoder.com/wiki/display/tc/SRM+518
a6b1fd4985 2011-09-28        kinaba: 
a6b1fd4985 2011-09-28        kinaba: 
a6b1fd4985 2011-09-28        kinaba: 以下のような関数を考える。
a6b1fd4985 2011-09-28        kinaba: 
a6b1fd4985 2011-09-28        kinaba: int[] xor_count(int[] a, int[] b, int N)
a6b1fd4985 2011-09-28        kinaba: {
a6b1fd4985 2011-09-28        kinaba: 	int[] c = {0} * N;
a6b1fd4985 2011-09-28        kinaba: 	for(int i=0; i<N; ++i)
a6b1fd4985 2011-09-28        kinaba: 		for(int k=0; k<N; ++k)
a6b1fd4985 2011-09-28        kinaba: 			c[i ^ k] += a[i] * b[k];
a6b1fd4985 2011-09-28        kinaba: 	return c;
a6b1fd4985 2011-09-28        kinaba: }
a6b1fd4985 2011-09-28        kinaba: 
a6b1fd4985 2011-09-28        kinaba: 高速化。
a6b1fd4985 2011-09-28        kinaba: 
a6b1fd4985 2011-09-28        kinaba: int[] xor_count_ultra(int[] a, int[] b, int N)
a6b1fd4985 2011-09-28        kinaba: {
a6b1fd4985 2011-09-28        kinaba: 	a = xor_pre(a);
a6b1fd4985 2011-09-28        kinaba: 	b = xor_pre(b);
a6b1fd4985 2011-09-28        kinaba: 	c = a * b; // element-wise product
a6b1fd4985 2011-09-28        kinaba: 	return xor_post(c);
a6b1fd4985 2011-09-28        kinaba: }
a6b1fd4985 2011-09-28        kinaba: 
a6b1fd4985 2011-09-28        kinaba: このようになるマジカルな変換 xor_pre, xor_post が存在する。
a6b1fd4985 2011-09-28        kinaba: 
a6b1fd4985 2011-09-28        kinaba: N=1 の場合、pre : {x} --> {x}
a6b1fd4985 2011-09-28        kinaba: N=2 の場合、pre : {x,y} --> {x-y, x+y}
a6b1fd4985 2011-09-28        kinaba:   xor_count( {x,y}, {u,v} ) = {xu+yv, yu+xv}
a6b1fd4985 2011-09-28        kinaba:   と {x-y, x+y} * {u-v, u+v} = {xu+yv-xu-xv, xu+yv+yu+xv}
a6b1fd4985 2011-09-28        kinaba:   から確認できる。
a6b1fd4985 2011-09-28        kinaba: 一般にNが2のベキの場合、xorの作用するビットのパターンが再帰的なので
a6b1fd4985 2011-09-28        kinaba:   pre( [X,Y] ) = [pre(X)-pre(Y), pre(X)+pre(Y)]
a6b1fd4985 2011-09-28        kinaba: と再帰的にすれば成り立つ
a6b1fd4985 2011-09-28        kinaba: 
a6b1fd4985 2011-09-28        kinaba: 
a6b1fd4985 2011-09-28        kinaba: 
a6b1fd4985 2011-09-28        kinaba: 
a6b1fd4985 2011-09-28        kinaba: 
a6b1fd4985 2011-09-28        kinaba: 
a6b1fd4985 2011-09-28        kinaba: xorでなくて足し算の場合
a6b1fd4985 2011-09-28        kinaba: 
a6b1fd4985 2011-09-28        kinaba: int[] plus_count(int[] a, int[] b, int N)
a6b1fd4985 2011-09-28        kinaba: {
a6b1fd4985 2011-09-28        kinaba: 	int[] c = {0} * 2N;
a6b1fd4985 2011-09-28        kinaba: 	for(int i=0; i<N; ++i)
a6b1fd4985 2011-09-28        kinaba: 		for(int k=0; k<N; ++k)
a6b1fd4985 2011-09-28        kinaba: 			c[i + k] += a[i] * b[k];
a6b1fd4985 2011-09-28        kinaba: 	return c;
a6b1fd4985 2011-09-28        kinaba: }
a6b1fd4985 2011-09-28        kinaba: 
a6b1fd4985 2011-09-28        kinaba: も同様に。
a6b1fd4985 2011-09-28        kinaba: 
a6b1fd4985 2011-09-28        kinaba: int[] plus_count_ultra(int[] a, int[] b, int N)
a6b1fd4985 2011-09-28        kinaba: {
a6b1fd4985 2011-09-28        kinaba: 	a = plus_pre(a);
a6b1fd4985 2011-09-28        kinaba: 	b = plus_pre(b);
a6b1fd4985 2011-09-28        kinaba: 	c = a * b; // element-wise product
a6b1fd4985 2011-09-28        kinaba: 	return plus_post(c);
a6b1fd4985 2011-09-28        kinaba: }
a6b1fd4985 2011-09-28        kinaba: 
a6b1fd4985 2011-09-28        kinaba: とできるのが FFT