inline void XOR(int a[], int fwt[], int type)
{
for (int i = 0; i < n; i++) fwt[i] = a[i];
for (int len = 2; len <= n; len <<= 1)
{
for (int l = 0, mid = l + (len >> 1) - 1, r = len - 1; l < n; l += len, r += len, mid += len)
{
for (int a = l, b = mid + 1; b <= r; a++, b++)
{
(fwt[a] *= type) %= mod, (fwt[b] *= type) %= mod;
(fwt[a] += fwt[b]) %= mod;
(((fwt[b] += fwt[a] - 3 * fwt[b]) %= mod) += mod) %= mod;
}
}
}
}
定义 a⊕b=popcount(a AND b) mod 2,令 FWTa,i=j⊕i=0∑aj−j⊕i=1∑aj。
按这个的话,FWT 的初始化不应该是代码中注释掉的部分吗?