考虑一种奇妙的构造 $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$

大概长这样:

1
2
3
4
5
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}
$$

大概长这样:

1
2
3
4
5
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;
}

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

1
2
3
4
5
6
7
8
9
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]);
}
}
}
}