快速沃尔什变换（FWT）快速莫比乌斯变换（FMT）

· · 个人记录

虽然一点不懂，但是看着代码短得感人，背过就好了吧。

或

FWT(A) = (FWT(A_0), FWT(A_1 + A_0)) IFWT(A) = (IFWT(A_0), IFWT(A_1 - A_0))

与

FWT(A) = (FWT(A_0 + A_1), FWT(A_1)) IFWT(A) = (IFWT(A_0 - A_1), IFWT(A_1))

异或

FWT(A) = (FWT(A_0 + A_1), FWT(A_0 - A_1)) FWT(A) = (FWT(\frac{A_0 + A_1}{2}), FWT(\frac{A_0 - A_1}{2}))

代码实现

记忆

有些东西不用全靠硬背，可以有技巧地背

或

进行或运算，通常数会往大里走，所以较高位的数要加上较低位的数 （雾）

与

与 与 或 相反，通常数会往小里走，于是 是较低位的数加上较高位的数 （大雾）

异或

有点特殊？ 有点像 FFT？那就记成 FFT 的形式就好了吧...

IFWT

IFWT 就是把 FWT 给还原一下就好了吧。

之前某位置加上了一个数，而现在那个数还没变 （大雾），那么就把那个数减掉就好了吧。

（对于异或）找不到之前那个数？没关系，可以列个方程解出来 （大雾）

注意！！

对于或卷积：（FWT:f[] -> f'[])

f'[i]=\sum_{j|i=i}f[j]

发现 f'[i] 为 i 的子集的权值和，因此可以做一些子集问题，如：P3175 [HAOI2015]按位或

子集卷积

P6097 【模板】子集卷积

给定a, b数组，令：

c_k = \sum_{i~and~j=0,i~or~j=k}a_i * b_j

即在 k 中找到两个互不相交的子集 i,j，计算 a_i * b_j 的总和

如果不要求互不相交，那么就是个 FWT_OR 的板子题了。如果要求互不相交，那么只需加上限制 |i| + |j| = |k|。

于是，我们可以枚举 |i|,|j|,|k|，然后将所有大小为 |i|,|j| 的 |a_i|,|b_j| 的总和乘一块加给 c_k，然后再将 c 数组卷回去，即为答案。

例题：P6570 [NOI Online #3 提高组]优秀子序列（民间数据）（洛谷数据可以被暴力水过，随机数据下本机也可过，但是CCF的评测机太慢，过不去）

例题：P4221 [WC2018]州区划分：自己卷自己的子集卷积。

7.29 Update:

从ztb那里学到的一些东西（对快速沃尔什变换的深入理解，后来发现似乎是快速莫比乌斯变换)

或卷积

我们定义一个高维前缀和数组：

\hat f_S = \sum_{T\subseteq S}f_T

我们发现如果这样的卷积符合 或卷积 的性质：

\hat h_S = \sum_{T \subseteq S} h_T =\sum_{T \subseteq S} \sum_{A|B = T} f_Ag_B =\sum_{A \subseteq S} \sum_{B \subseteq S}f_A g_B = \hat f_A \hat g_B

这样就可以 O(n) 乘法了。（ n 为总状态数，或者说是2^{|U|})

如何求 \hat f(S) ? 可以使用高维前缀和的方法（for(维度i） for (所有状态S) S += S - i)，其中 S - i 需要特判。复杂度 O(nlogn)。因此，如果我们直接枚举 S 中 i 两边的维度就可以使常数降为 1/2。

与卷积

我们定义一个类高维前缀和数组：

\hat f_S = \sum_{S\subseteq T}f_T

这个数组符合与卷积的性质：

\hat h(S) = \sum_{S \subseteq T} h(T) =\sum_{S \subseteq T} \sum_{A andB = T} f_Ag_B = \sum_{T, A, B}f_Ag_B[S \subseteq T][A and B = T] =\sum_{A} \sum_{B}f_A g_B[S \subseteq A and B] =\sum_{S \subseteq A} \sum_{S \subseteq B} f_Ag_B = \hat f_A \hat g_B

代码实现就是反过来（0看作1,1看作0）做一遍高维前缀和。

异或卷积

这个就用不了 FMT 了。

我们定义一个根本不是前缀和的辅助数组：

\hat f_S = \sum_{T}(-1)^{|S \& T|}f_T

然后艰难地寻找其有关卷积的性质：

\hat h_S = \sum_{T}(-1)^{|S \& T|}h_T = \sum_{T}\sum_{A \wedge B=T}(-1)^{|S \& T|} f_A g_B =\sum_{A, B}(-1)^{|S \& (A \wedge B)|}f_Ag_B

看起来推不下去了？仔细观察 |S \& (A \wedge B)| 这个式子，想一想它和 |S \& A| + |S \& B| 的关系。

考虑按位拆分统计贡献（这显然是可行的），先刨除掉 S 没出现的位，考虑剩下的 S 出现的位。如果 a = b，则 a \wedge b = 0,对原式子的贡献是0，对后面的式子的贡献是偶数，因此等效；如果 a \not= b，则 a \wedge b = 1，对原式子的贡献是1，对后面的式子的贡献同样是1.

于是我们有了一个惊人的发现：(-1)^{|S \& (A \wedge B)|} = (-1)^{|S \& A| + |S \& B|}，于是可以继续推：

\hat h_S = \sum_{A, B}(-1)^{|S \& A|} f_A (-1)^{|S \& B|} g_B =\hat f_A \hat g_B

这样我们就可以快速推异或卷积了。

可是这个 \hat f(S) 怎么搞？总不能再高维前缀和了吧。实际上我们可以模仿 DFT ，分奇偶分组分治讨论。

一维一维地考虑。初始时（只考虑自己） \hat f(S) = (-1)^{|0 \& 0|}f(S) = f(S)。对于当前维度（首位）是0的那一组（左边的那一组），它的值应该是原来的左边对应的 \hat f 值（因为|0S \& 0S|=|S|）再加上原来右边对应的 \hat f 值（因为|0S \& 1S|=|S|）；对于当前维度（首位）是1的那一组（右边），它的值应该是原来负的右边的对应的 \hat f 值（因为 |1S \& 1S| = |S| + 1，只有右边的和右边的与才会 +1）再加上左边的对应的 \hat f 值（因为|1S \& 0S|=|S|）。复杂度：O(nlogn)。

然后是逆变换。实际上还有个式子：

f_S = \frac{1}{2^n} \sum_T (-1)^{|S \& T|} \hat f_T

也比较好证，展开一下 \hat f_T ，再交换一下求和号可得：

right = 1/2^n \sum_{P}f_P\sum_{T}(-1)^{|S \& T| + |P \& T|}

右上角的式子很熟悉，它等于：|(S \wedge P) \& T|，于是：

right = 1/2^n \sum_{P}f_P\sum_{T}(-1)^{|(S \wedge P) \& T|}

关键在于证得：

\sum_{T \subseteq U} (-1)^{|T \& Q|} = 2^n[Q=\phi]

这是因为只要 Q 有一维有数，那么我们就可以摁着这一位，将 T 分成有这一位的和没有这一位的，这两类数量相同，且存在奇偶性不同的一一映射关系，然后式子就被消成 0 了。

然后就什么都好说了，这里就不再证了。

而这个 \frac{1}{2^n} \sum_T (-1)^{|S \& T|} \hat f_T 也好算，再来一遍 FWT ，最终除掉 1/2^n 即可（或者每层除以一个二也可）

（其实最简单的方法莫过于干了什么就“撤回”什么，可以直接推得沃尔什逆变换）。

小结

\hat f_S = \sum_{T \subseteq S} f_T

意义:（同高维前缀和）S 的所有子集的和。

\hat f_S = \sum_{S \subseteq T} f_T

意义：包含 S 的所有集合的和。

\hat f_S = \sum_{T}(-1)^{|S \& T|}f_T

意义：?????

2021.3.31 Update

对异或卷积有了新的理解。

可能需要先了解一下集合幂级数的概念。可以在吕凯风的集训队论文中找到。

观察异或运算，其本质上是二进制不进位加法，那么下标上的异或运算就是做长度为 2 的循环卷积，可以使用 FFT。并且，\omega_2^0 = 1,\omega_2^1 = -1，这两个单位根都是实数，于是就不用要求模数有原根了。

考虑 2^1 的情况，即一维的情况。假设原多项式为 f_0x^0 + f_1x^1，暴力代入单位根，得到的新多项式为 (f_0 + f_1)x^0 + (f_0 - f_1)x^1。

下面目前还不太理解。对于高维的情况，其 FFT 就是对每一维进行一遍 FFT。然后就得到了我们的 FWT 算法。

于是，我们不仅可以做 二维的不进位加法卷积，也可以做更高维的不进位加法卷积（如果模数友好存在那些单位根）

应用

4589: Hard Nim

经典Nim游戏（轮流取石子，无法操作者为负）。

n堆石子满足每堆石子的初始数量是不超过m的质数。

求先手必败局面数。

n <= 1e9, m <= 5e4

最朴素的方法自然是枚举每一种方案，判断其合法不合法。

\sum_{i=1}^{m}\sum_{j=1}^{m}\sum_{k=1}^m...(n~sigma)...\sum_{l=1}^m[i,j,k,...,l=prime,i~xor~j~xor~k~xor~...~xor~l=0]

复杂度：O(nm^n)

当只有两个sigma(n=2)的时候是：

\sum_{i=1}^m\sum_{j=1}^m[i,j=prime,i~xor~j=0]

即

\sum_{i~xor~j=0}{[i,j=prime]}

是异或卷积的形式。

（思维逐渐混乱）

根据FFT相关计数题目的经验，我们可以用权值数组。即 a[i] 表示异或值为 i 有多少种情况。然后就可以用FWT了。

考虑类似快速幂的方法，以快速幂的格式，把 a[~] 当作 x，做多项式快速幂，最终答案就是 a[0]。复杂度大概O(m~logm~logn)（有点悬？）

一想到多项式快速幂，我们就成功的走向了大弯路，甚至复杂度都有点保不住。不要忘记FFT,NTT,FWT都是借助点值表示加速的本质。在转化成点值表示以后，仍支持交换律，结合律等，因此可以直接把每个点值做快速幂。复杂度O(m~logm~+~m~logn)

Code: 
limi = 1;
while (limi <= m)   limi <<= 1;
for (register int i = 0; i <= m; ++i)   A[i] = (!depri[i]);
FWT_xor(A, 1);
for (register int i = 0; i <= limi; ++i)    A[i] = quickpow(A[i], n);
FWT_xor(A, -1);
printf("%lld\n", A[0]);

CF662C Binary Table

先看题解 CF662C 【Binary Table】吧。

有一个 n 行 m 列的表格，每个元素都是 0/1 ，每次操作可以选择一行或一列，把 0/1 翻转，即把 0 换为 1 ，把 1 换为 0 。请问经过若干次操作后，表格中最少有多少个 1 。

n<=20, m<=1e5

考虑枚举行翻转情况为State。设一开始第 i 列的情况为 S_i，则对于每个 State 来说，答案为(F_s表示某一列状态为 s 的最大贡献（1个数）：

\sum_{i=1}^m{F_{State~xor~S_i}}

转换枚举对象： 枚举 对行操作后的列状态 X（方便直接使用 F_X 统计答案） 和 S_i (Q_s 表示状态为 S 的列有多少个):

\sum_{X=0}^{2^n}\sum_{S = 0}^{2^n}{[State~xor~S = X]F_{X}* Q_{S}}

稍作变换：

\sum_{X=0}^{2^n}\sum_{S = 0}^{2^n}{[State = X~xor~S]F_{X}* Q_{S}}

即：

\sum_{X~xor~S=State}{F_X * Q_S}

然后预处理出 F 和 Q ，FWT即可。

练习题

P3175 [HAOI2015]按位或

A国的贸易

附

FWT模板（调试用）

inline void FWT_or(ll *a, int type) {
    for (register int i = 1; i < limi; i <<= 1) {
        for (register int j = 0; j < limi; j += (i << 1)) {
            for (register int p = 0; p < i; ++p) {
                a[i + j + p] = (a[i + j + p] + a[j + p] * type) % P;
                if (a[i + j + p] < 0)   a[i + j + p] += P;
            }
        }
    }
}

inline void sol_or() {
    memcpy(tp1, A, sizeof(A));
    memcpy(tp2, B, sizeof(B));
    FWT_or(tp1, 1); FWT_or(tp2, 1);
    for (register int i = 0; i < limi; ++i) C[i] = tp1[i] * tp2[i] % P;
    FWT_or(C, -1);
    for (register int i = 0; i < limi; ++i) printf("%lld ", C[i]);
    puts("");
}
inline void FWT_and(ll *a, int type) {
    for (register int i = 1; i < limi; i <<= 1) {
        for (register int j = 0; j < limi; j += (i << 1)) {
            for (register int p = 0; p < i; ++p) {
                a[j + p] = (a[j + p] + a[i + j + p] * type) % P;
                if (a[j + p] < 0)   a[j + p] += P;
            }
        }
    }
}

inline void sol_and() {
    memcpy(tp1, A, sizeof(A));
    memcpy(tp2, B, sizeof(B));
    FWT_and(tp1, 1); FWT_and(tp2, 1);
    for (register int i = 0; i < limi; ++i) C[i] = tp1[i] * tp2[i] % P;
    FWT_and(C, -1);
    for (register int i = 0; i < limi; ++i) printf("%lld ", C[i]);
    puts("");
}
inline void FWT_xor(ll *a, int type) {
    for (register int i = 1; i < limi; i <<= 1) {
        for (register int j = 0; j < limi; j += (i << 1)) {
            for (register int p = 0; p < i; ++p) {
                ll nx = a[j + p], ny = a[i + j + p];
                a[j + p] = (nx + ny) % P;
                a[i + j + p] = (nx - ny + P) % P;
                if (type == -1) {
                    a[j + p] = a[j + p] * inv2 % P;
                    a[i + j + p] = a[i + j + p] * inv2 % P;
                }
            }
        }
    }
}

inline void sol_xor() {
    memcpy(tp1, A, sizeof(A));
    memcpy(tp2, B, sizeof(B));
    FWT_xor(tp1, 1); FWT_xor(tp2, 1);
    for (register int i = 0; i < limi; ++i) C[i] = tp1[i] * tp2[i] % P;
    FWT_xor(C, -1);
    for (register int i = 0; i < limi; ++i) printf("%lld ", C[i]);
    puts("");
}