【学习笔记】快速沃尔什变换（FWT)

引入

求
$$d_k=\sum _{ioptj=k}{a}_i{b}_j$$
其中$opt$是某种位运算。不准暴力

分析

我们已经知道可以用FFT来加速一个多项式卷积的运算。即将一个多项式转化为点值表示法，通过增加转换部分的用时来减少计算的用时，从而优化整个运算过程。

（图不是我画的）

于是我们想利用类似的思路，将数列$A$，$B$通过某种方式转化成另一种形式，从而加快计算的速度。

FWT与IFWT

按照上面的思路，我们想将数列$A$，$B$转化为数列$A^{\prime }$，$B^{\prime }$，然后算得
$$d_k^{\prime }=\sum _{i=1}^n{a}_k^{\prime }{b}_k^{\prime }$$
再将$D^{\prime }$转化为$D$即可。
观察我们想要计算的结果可知，变换
$$FWT(A)=A^{\prime }$$
的过程一定得是个关于$A$中各个元素的线性变换（如果有交叉项的话必定得不到$C$中的元素）。也就是说，上述的变换本质上就是一个矩阵$C$。再结合我们的需求，我们所要做的就是找到一个可逆矩阵$C$。
那么这个矩阵有什么特性呢？令
$$FWT(A)\cdot FWT(B)=FWT(D)$$
即需要满足对任意的$i$
$$FWT(A{)}_i\cdot FWT(B{)}_i=FWT(D{)}_i$$
也就是
$$\sum _{k=1}^n\sum _{j=1}^n{c}_{ij}{c}_{ik}{a}_k{b}_j=\sum _{k=1}^n{c}_{ik}{d}_k$$
结合题意
$$\sum _{k=1}^n\sum _{j=1}^n{c}_{ij}{c}_{ik}{a}_k{b}_j=\sum _{k=1}^n{c}_{ik}\sum _{moptl=k}{a}_m{b}_l$$
右式改为枚举$m,l$
$$\sum _{k=1}^n\sum _{j=1}^n{c}_{ij}{c}_{ik}{a}_j{b}_j=\sum _{k=1}^n\sum _{j=1}^n{c}_{ijoptk}{a}_k{b}_j$$
为使上式恒成立，可以规定
$$c_{ij}{c}_{ik}=c_{ijoptk}$$
于是我们就可以根据这个式子，按照实际的$opt$来构造这个矩阵了。
下面考虑有了矩阵$C$以后如何计算
$$FWT(A{)}_i=\sum _{k=1}^n{c}_{ik}{a}_k$$
为方便叙述，令$n=2^m$。我们将$n$拆成最高位为0与最高位为1两个部分。
$$FWT(A{)}_i=\sum _{k=1}^{\frac{n}{2}-1}{c}_{ik}{a}_k+\sum _{k=\frac{n}{2}}^n{c}_{ik}{a}_k$$
发现这个形式跟归并排序有点像，于是就想着分治，也就需要将两项进行变形为相似的形式。
我们对这个矩阵进一步的把玩发现：若令$x_i$为$x$的第$i$位，则
$$c_{ij}=\prod _{k=1}^m{c}_{i_k{j}_k}$$
所以我们可以把两项的矩阵系数拆出$k$最高位的部分。令剩下的为$k^{\prime }$，则
$$FWT(A{)}_i=c_{i_{1}0}\sum _{k=1}^{\frac{n}{2}-1}{c}_{i^{\prime }{k}^{\prime }}{a}_k+c_{i_{1}1}\sum _{k=\frac{n}{2}}^n{c}_{i^{\prime }{k}^{\prime }}{a}_k$$
那么可以发现：我们无需构造原来的大小为$n\times n$的矩阵，而仅需构造一个$2\times 2$的矩阵，就可以递归处理了
$$\begin{gathered} FWT(A{)}_i=c_{00}FWT(A_{lft})+c_{01}FWT(A_{rgt})i<\frac{n}{2} \\ FWT(A{)}_{i+\frac{n}{2}}=c_{10}FWT(A_{lft})+c_{11}FWT(A_{rgt})i\ge \frac{n}{2} \end{gathered}$$
同理，由于构造出来的矩阵可逆，所以FWT的逆变换可以直接利用$C$的逆矩阵做一次FWT即可。

基础位运算对应转移矩阵

与

C = ( 1 1 0 1 ) C=\left(

\right) C=(10​11​)

或

C = ( 1 1 0 1 ) C=\left(

\right) C=(10​11​)

异或

C = ( 1 1 1 − 1 ) C=\left(

\right) C=(11​1−1​)

例题与代码

题面
考虑DP。设$f[i][j]$表示以$i$为根的子树中异或和为$j$的数目，则
$$f[i][j\oplus k]=\sum _{j=0}^m\sum _{k=0}^{m}f[i][j]\cdot f[son[i]][k]$$
利用FWT优化即可

#include
#define reg register
#define ll long long
using namespace std;
const int mn = 1005, mod = 1e9+7;
const int inv2 = 500000004;
vector<int> g[mn];
ll f[mn][1030], h[1030];
ll cxor[2][2] = {{1,1},{1,mod-1}}, icxor[2][2] = {{inv2,inv2},{inv2,mod-inv2}};
int a[mn], n, m;
inline void fwt(ll *a, ll c[2][2])
{
    for(reg int len = 1; len < m; len <<= 1)
        for(reg int st = 0; st < m; st += len + len)
            for(reg int i = st; i < st + len; i++)
            {
                ll tmp = a[i];
                a[i] = (c[0][0] * a[i] + c[0][1] * a[i + len]) % mod;
                a[i + len] = (c[1][0] * tmp + c[1][1] * a[i + len]) % mod;
            }
}
void dp(int s, int fa)
{
    int siz = g[s].size();
    f[s][a[s]] = 1;
    for(reg int i = 0; i < siz; i++)
    {
        int t = g[s][i];
        if(t != fa)
        {
            dp(t, s);
            fwt(f[s], cxor), fwt(f[t], cxor);
            for(int j = 0; j < m; j++)
                h[j] = f[s][j] * f[t][j] % mod;
            fwt(h, icxor), fwt(f[t], icxor), fwt(f[s], icxor);
            for(int j = 0; j < m; j++)
                f[s][j] += h[j], f[s][j] %= mod;
        }
    }
}
inline int getint()
{
    int ret = 0; char c = getchar();
    while(c < '0' || c > '9') c = getchar();
    while(c >= '0' && c <= '9') ret = ret * 10 + c - '0', c = getchar();
    return ret;
}
int main()
{
    int T, x, y;
    T = getint();
    while(T--)
    {
        n = getint(), m = getint();
        for(reg int i = 1; i <= n; i++)
            a[i] = getint(), g[i].clear();
        for(reg int i = 1; i < n; i++)
        {
            x = getint(), y = getint();
            g[x].push_back(y), g[y].push_back(x);
        }
        for(reg int i = 1; i <= n; i++)
            for(reg int j = 0; j < m; j++)
                f[i][j] = 0;
        dp(1, 0);
        for(reg int i = 0; i < m; i++)
        {
            ll ans = 0;
            for(reg int j = 1; j <= n; j++)
                ans += f[j][i], ans %= mod;
            printf("%I64d", ans);
            if(i != m - 1) putchar(' ');
            else puts("");
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77