一个奇妙的fwt构造方法

考虑一种奇妙的构造 $fwt$ 的方法

好像就是分治乘法

现在要求出 $c = a \times b$

不妨构造出右侧关于 $a,b$ 的直积的形式

比如说二进制下的不进位加法（异或）：

$$
\begin{cases}
c_0=a_0b_0+a_1b_1 \\
c_1=a_0b_1+a_1b_0
\end{cases}
$$

那么凑一凑后可以得到：

$$
\begin{cases}
d_0=c_0+c_1=(a_0+a_1)(b_0+b_1) \\
d_1=c_0-c_1=(a_0-a_1)(b_0-b_1)
\end{cases}
$$

那么就可以写一个函数，来得到 $d_0$ 和 $d_1$

大概长这样：

void C(ll &a, ll &b) {
    ll x[2] = { a, b };
    a = (x[0] + x[1]) % mod;
    b = (x[0] - x[1]) % mod;
}

那么逆变换也是如此编上去，也就是：

$$
\begin{cases}
c_0=\frac{d_0+d_1}{2} \\
c_1=\frac{d_0-d_1}{2}
\end{cases}
$$

大概长这样：

void D(ll &a, ll &b) {
    ll x[2] = { a, b };
    a = (x[0] + x[1]) * inv2 % mod;
    b = (x[0] - x[1]) * inv2 % mod;
}

那么只需要组装起来就行了：

template<typename T> void fwt(ll *a, int n, T t) {
    for(int i = 1 ; i < n ; i *= 2) {
        for(int j = 0, len = i * 2 ; j < n ; j += len) {
            for(int k = 0 ; k < i ; ++ k) {
                t(a[j + k], a[j + i + k]);
            }
        }
    }
}