Fast Walsh Transform

特别巧妙地构造（？）技巧。
前置技能：FFT。
Pick's
2
有空再来讲证明和具体意思。

for(int s = 1, x, y; s <= n; s <<= 1) for(int i = 0; i < n; i += s << 1) for(int j = 0; j < i; j++)
    x = a[i + j], y = a[i + j + s], a[i + j] = (x + y) % mod, a[i + j + s] = (x - y + mod) % mod;
//XOR: a[i + j] = x + y, a[i + j + s] = x - y
//AND: a[i + j] = x + y
//OR: a[i + j + h] = x + y

for(int s = 1, x, y; s <= n; s <<= 1) for(int i = 0; i < n; i += s << 1) for(int j = 0; j < i; j++)
    x = a[i + j], y = a[i + j + s], a[i + j] = (x + y) * rev % mod, a[i + j + s] = (x - y + mod) * rev % mod;
//XOR: a[i + j] = (x + y) / 2, a[i + j + s] = (x - y) / 2
//AND: a[i + j] = x - y
//OR: a[i + j + h] = y - x