快速沃尔什变换/快速莫比乌斯变换

笔者对快速沃尔什变换/快速莫比乌斯变换的理解也只是刚学阶段，本文只是写写自己的理解和一些其他博客略去的证明。(还没写完的部分可能会咕咕咕一段时间再写)

前置知识：卷积

对于多项式卷积，其思想是对于两个多项式，首先经过转换为点值表示得到，令，再对作一次转化为数组即为答案。

那么类比多项式卷积，位运算卷积也可以类似定义，第项和第项的乘积贡献到第项，则，此处对应某种位运算，那么只需要构造一种转换满足就能实现时间复杂度的位运算卷积(论构造手为什么是神)，具体构造方法可以由数学推导得出+真值表+矩阵求逆得出，由于笔者处于初学阶段，暂不去推构造证明

以下只讲与、或、异或三种位运算卷积且序列长度为的幂

与

构造 这样就可以在时间求出和的乘积，现在只需快速求出变换和

设序列长度为，下标范围为，由于和位运算的特殊性，考虑对按位分治，设

设是下标为的序列，是下标为的序列，如果已经求出了和，那么只要计算和相互的贡献就能求出

对于，有，考虑二进制表示，则在二进制表示上比多一个最高位的，即，因此对于任意若满足，也一定满足，又和构成双射，那么对于，在上恰好对有一次贡献，在上不变，因此可以推出下式： 那么的分治就完成了

再对序列做就能得到答案序列经过变换后的序列

对于，即为的反演，考虑矩阵 行变换后可得 (这部分矩阵证明反演笔者也不知道是否合理，凭感觉写的)

那么可以推出下式： 就能得到最终的答案序列

void mul(int n)
{
    for (int i = 0; i < n; i++)
        a[i] = a[i] * b[i] % mod;
}
void AND(ll *f, ll x, int n)
{
    for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
        for (int i = 0; i < n; i += o)
            for (int j = 0; j < k; j++)
                f[i + j] = (f[i + j] + f[i + j + k] * x) % mod;
}
void FWT_AND()
{
    AND(a, 1, n), AND(b, 1, n), mul(n), AND(a, mod - 1, n)
}

剩下的部分咕咕咕