位运算卷积指，给定两个长度为 $n$ 的数组 $a,b$，0-index，求数组 $c=a*b$ 满足 $c_k=\displaystyle\sum_{i\otimes j=k}a_i\times b_j$，其中 $\otimes$ 表示一种位运算。
分治乘法解决此类问题的思想是，对于任意一种位运算而言，不同的位之间互不影响，所以可以通过某种方式去掉最高位的影响，然后向下分治。
以分治乘法解决或卷积为例：
发现对于一个长度为 $n$ 的数组而言，如果忽视下标二进制下的最高位，那么这个数组可以被分成前后两个长度为 $\frac{n}{2}$ 的下标对位相等的部分，也就是每次问题大小可以减半。
具体而言，对于 $c_k=\displaystyle\sum_{i|j=k}a_i\times b_j$，我们把数组 $a$ 分成两个部分 $a_0,a_1$，表示 $a$ 中下标的二进制最高位分别是 $0,1$ 的子数组，显然长度均为 $\frac{n}{2}$，下标的值域都是 $[0,\frac{n}{2})$，$b,c$ 进行同样操作。
然后以 $k$ 的最高位为 $0$ 为例，那么显然 $i,j$ 的最高位都要为 $0$，说明所有数只能从 $a_0$ 和 $b_0$ 中选取，而此时只需要满足 $k’=i’|j’$ 即可，其中 $x’$ 表示数 $x$ 去掉最高位变成的数。
所以 $c_0=a_0*b_0$，同理可以得到 $c_1=a_0*b_1+a_1*b_0+a_1*b_1=(a_0+a_1)*(b_0+b_1)-c_0$，其中 $+$ 是简单的对位加法，不难发现这样只需要分治下去做两次卷积即可，时间复杂度 $T_n=2T_{\frac{n}{2}}+\mathcal{O}(n)=\mathcal{O}(n\log n)$。
与和异或卷积可以同理解决，且复杂度不劣于 FWT，代码如下：
P4717 【模板】快速莫比乌斯 / 沃尔什变换 (FMT / FWT) – 洛谷
#include "bits/stdc++.h"
#define int __int128
#define f(i ,m ,n ,x) for (int i = (m) ,i##END = (n) ; i <= i##END ; i += (x))
#define f_(i ,m ,n ,x) for (int i = (m) ,i##END = (n) ; i >= i##END ; i -= (x))
using v128 = std :: vector < int > ;
const int N = 20 ,mod = 998244353 ;
int n ,a[1 << N] ,b[1 << N] ;
signed main (int argc ,char *argv[]) {
std :: ios :: sync_with_stdio (false) ,
std :: cin.tie (nullptr) ,std :: cout.tie (nullptr) ;
long long nn ; std :: cin >> nn ,n = nn ,n = 1 << n ;
auto Or = [] (auto &&self ,int len ,v128 a ,v128 b) -> v128 {
v128 c ; c.resize (len << 1 ,0) ;
if (len == 1) {
c[0] = a[0] * b[0] ,
c[1] = (a[0] + a[1]) * (b[0] + b[1]) - c[0] ;
return c ;
}
v128 A ,B ,C ;
A.resize (len ,0) ,B.resize (len ,0) ,C.resize (len ,0) ;
f (i ,0 ,len - 1 ,1) A[i] = a[i] ,B[i] = b[i] ;
C = self (self ,len >> 1 ,A ,B) ;
f (i ,0 ,len - 1 ,1) c[i] = C[i] ;
f (i ,0 ,len - 1 ,1)
A[i] = a[i] + a[i + len] ,B[i] = b[i] + b[i + len] ;
C = self (self ,len >> 1 ,A ,B) ;
f (i ,0 ,len - 1 ,1) c[i + len] = C[i] - c[i] ;
return c ;
} ;
auto And = [] (auto &&self ,int len ,v128 a ,v128 b) -> v128 {
v128 c ; c.resize (len << 1 ,0) ;
if (len == 1) {
c[1] = a[1] * b[1] ,
c[0] = (a[0] + a[1]) * (b[0] + b[1]) - c[1] ;
return c ;
}
v128 A ,B ,C ;
A.resize (len ,0) ,B.resize (len ,0) ,C.resize (len ,0) ;
f (i ,0 ,len - 1 ,1) A[i] = a[i + len] ,B[i] = b[i + len] ;
C = self (self ,len >> 1 ,A ,B) ;
f (i ,0 ,len - 1 ,1) c[i + len] = C[i] ;
f (i ,0 ,len - 1 ,1)
A[i] = a[i] + a[i + len] ,B[i] = b[i] + b[i + len] ;
C = self (self ,len >> 1 ,A ,B) ;
f (i ,0 ,len - 1 ,1) c[i] = C[i] - c[i + len] ;
return c ;
} ;
auto Xor = [] (auto &&self ,int len ,v128 a ,v128 b) -> v128 {
v128 c ; c.resize (len << 1 ,0) ;
if (len == 1) {
c[1] = a[1] * b[0] + a[0] * b[1] ,
c[0] = (a[0] + a[1]) * (b[0] + b[1]) - c[1] ;
return c ;
}
v128 A ,B ,C1 ,C2 ;
A.resize (len ,0) ,B.resize (len ,0) ,C1.resize (len ,0) ,C2.resize (len ,0) ;
f (i ,0 ,len - 1 ,1)
A[i] = a[i] + a[i + len] ,B[i] = b[i] + b[i + len] ;
C1 = self (self ,len >> 1 ,A ,B) ;
f (i ,0 ,len - 1 ,1)
A[i] = a[i] - a[i + len] ,B[i] = b[i] - b[i + len] ;
C2 = self (self ,len >> 1 ,A ,B) ;
f (i ,0 ,len - 1 ,1)
c[i] = C1[i] + C2[i] >> 1 ,c[i + len] = C1[i] - C2[i] >> 1 ;
return c ;
} ;
v128 a ,b ; a.resize (n) ,b.resize (n) ;
f (i ,0 ,n - 1 ,1) { long long aa ; std :: cin >> aa ,a[i] = aa ;}
f (i ,0 ,n - 1 ,1) { long long bb ; std :: cin >> bb ,b[i] = bb ;}
v128 c = Or (Or ,n >> 1 ,a ,b) ;
f (i ,0 ,n - 1 ,1) std :: cout << (signed) (c[i] % mod) << " \n"[i == n - 1] ,c[i] = 0 ;
c = And (And ,n >> 1 ,a ,b) ;
f (i ,0 ,n - 1 ,1) std :: cout << (signed) (c[i] % mod) << " \n"[i == n - 1] ,c[i] = 0 ;
c = Xor (Xor ,n >> 1 ,a ,b) ;
f (i ,0 ,n - 1 ,1) std :: cout << (signed) (c[i] % mod) << " \n"[i == n - 1] ,c[i] = 0 ;
return 0 ;
}
但是分治乘法在解决另一些问题的时候可以做到优于 FWT。
定义三进制 mex 卷积为：对于长度为 $n$ 的数组 $a,b$，卷积结果为数组 $c=a*b$ 满足 $c_k=\displaystyle\sum_{\text{mex}(i,j)=k}a_i\times b_j$，其中 $i,j$ 的 $\text{mex}$ 表示两个数在三进制下每位都取 $\text{mex}$ 后得到的数。
类似的，每个数组都分为形如 $a_0,a_1,a_2$ 的三个部分，不难发现：
$$c_0=a_1*b_1+a_1*b_2+a_2*b_1+a_2*b_2,c_1=a_0*b_2+a_2*b_0+a_0*b_0,c_2=a_0*b_1+a_1*b_0$$
可以看出 $c_0+c_1+c_2=(a_0+a_1+a_2)*(b_0+b_1+b_2),c_0=(a_1+a_2)*(b_1+b_2)$，其他的等式右边不太好拆成两个数组卷的形式，那咋办。
考虑扩域，设 $c_3=a_2*b_2$，于是有 $c_1=(a_0+a_2)*(b_0+b_2)-c_3$，而 $c_2=(a_0+a_1+a_2)*(b_0+b_1+b_2)-c_0-c_1$，所以每次需要递归做 $4$ 次卷积，每次数组长度除以 $3$，复杂度 $T_{n}=4T_{\frac{n}{3}}+\mathcal{O}(n)=\mathcal{O}(4^n)$，比 FWT 少一个 $\log$。
Tritwise Mex – Problem – QOJ.ac
#include "bits/stdc++.h"
#define int long long
#define f(i ,m ,n ,x) for (int i = (m) ,i##END = (n) ; i <= i##END ; i += (x))
using v64 = std :: vector < int > ;
int k ;
signed main (int argc ,char *argv[]) {
std :: ios :: sync_with_stdio (false) ,
std :: cin.tie (nullptr) ,std :: cout.tie (nullptr) ;
std :: cin >> k ;
int n = 1 ; f (i ,1 ,k ,1) n *= 3 ;
auto Mex = [] (auto &&self ,int len ,v64 a ,v64 b) -> v64 {
v64 c ; c.resize (len * 3 ,0) ; if (len == 1) {
c[0] = (a[1] + a[2]) * (b[1] + b[2]) ,
c[1] = a[0] * b[0] + a[0] * b[2] + a[2] * b[0] ,
c[2] = a[0] * b[1] + a[1] * b[0] ;
return c ;
}
v64 A ,B ,C ;
A.resize (len ,0) ,B.resize (len ,0) ,C.resize (len ,0) ;
f (i ,0 ,len - 1 ,1)
A[i] = a[i + len] + a[i + len * 2] ,
B[i] = b[i + len] + b[i + len * 2] ;
C = self (self ,len / 3 ,A ,B) ;
f (i ,0 ,len - 1 ,1) c[i] = C[i] ;
f (i ,0 ,len - 1 ,1)
A[i] = a[i] + a[i + len * 2] ,
B[i] = b[i] + b[i + len * 2] ;
C = self (self ,len / 3 ,A ,B) ;
f (i ,0 ,len - 1 ,1) c[i + len] = C[i] ;
f (i ,0 ,len - 1 ,1)
A[i] = a[i + len * 2] ,B[i] = b[i + len * 2] ;
C = self (self ,len / 3 ,A ,B) ;
f (i ,0 ,len - 1 ,1) c[i + len] -= C[i] ;
f (i ,0 ,len - 1 ,1)
A[i] = a[i] + a[i + len] + a[i + len * 2] ,
B[i] = b[i] + b[i + len] + b[i + len * 2] ;
C = self (self ,len / 3 ,A ,B) ;
f (i ,0 ,len - 1 ,1)
c[i + len * 2] = C[i] - c[i] - c[i + len] ;
return c ;
} ;
v64 a ,b ; a.resize (n ,0) ,b.resize (n ,0) ;
f (i ,0 ,n - 1 ,1) std :: cin >> a[i] ;
f (i ,0 ,n - 1 ,1) std :: cin >> b[i] ;
v64 c = Mex (Mex ,n / 3 ,a ,b) ;
f (i ,0 ,n - 1 ,1) std :: cout << c[i] << " \n"[i == n - 1] ;
return 0 ;
}