板子 FWT

快速沃尔什变换，用于处理 \(C_k=\sum_{i\otimes j=k}A_i*B_j\) （\(\otimes\) 是集合运算符）几何卷积运算

对于 \(A\) 求出 \(fwt[A]\) ，使得 \(fwt[C]=fwt[A]*fwt[B]\) ，于是就 \(O(n)\) 了

我纯靠感性理解，更不会讲QAQ，这里只贴板子

几篇有帮助的博客：

• ACMLCZH的blog

• xht37的blog

\(or\) 或卷积

\(FWT\)： \[ fwt[a]=(fwt[a_0],\ fwt[a_0]+fwt[a_1]) \] \(IFWT\)：

\[ a=(a_0,\ a_0-a_1) \]

inline void FWT_or(int *f, int opt = 1) {
    for (int mid = 1; mid << 1 <= n; mid <<= 1)
        for (int i = 0; i < n; i += mid << 1)
            for (int j = 0; j < mid; ++j)
                f[i+mid+j] = ((LL)f[i+j] * opt + f[i+mid+j] + MOD) % MOD;
}

\(and\) 与卷积

非常相似呢，只管粘过来一改就好

\(FWT\)： \[ fwt[a]=(fwt[a_0]+fwt[a_1],\ fwt[a_1]) \] \(IFWT\)：

\[ a=(a_0-a_1,\ a_1) \]

inline void FWT_and(int *f, int opt = 1) {
    for (int mid = 1; mid << 1 <= n; mid <<= 1)
        for (int i = 0; i < n; i += mid << 1)
            for (int j = 0; j < mid; ++j)
                f[i+j] = ((LL)f[i+j] + f[i+mid+j] * opt + MOD) % MOD;
}

\(xor\) 异或卷积

最恶心的

\(FWT\)： \[ fwt[a]=(fwt[a_0]+fwt[a_1],\ fwt[a_0]-fwt[a_1]) \] \(IFWT\)：

\[ a=(\frac{a_0+a_1}{2},\ \frac{a_0-a_1}{2}) \]

inline void FWT_xor(int *f, int opt = 1) {
    for (int mid = 1; mid << 1 <= n; mid <<= 1)
        for (int i = 0; i < n; i += mid << 1)
            for (int j = 0; j < mid; ++j) {
                int fx = f[i+j], fy = f[i+mid+j];
                f[i+j] = (LL)opt * (fx + fy) % MOD;
                f[i+mid+j] = (LL)opt * (fx - fy + MOD) % MOD;
            }
}

（\(IFWT\) 时，opt 应为 \(2^{-1}\)）