I Speak Whales (UVa Live Archive Africa and the Middle East - Africa and Arab - 2008/2009 Alexandria - Egypt)

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4369

問題

Walsh行列が与えられる。大きさ2^NのWalsh行列の列Rの行SからEの合計値を求めよ。
0<=N<=60
0<=R<=2^N
0<=S<=E<=2^N
E-S<=10000

解法

Walsh行列の(y,x)の値はy&xの立っているビットの数が偶数なら1、奇数なら-1になる。なのでO((E-S)loglogR)で計算可能。別の方法を使えばO(N)でも計算できる。