max加或卷积

定义 $C=A\times B$ 满足 $C_i=\max_{j\lor k=i}(A_j+B_k)$。

约定 $\operatorname{concat}(A,B)$ 表示把 A，B 数组接起来，$\max(A,B)$ 表示 A，B 按位取 max。

考虑用类似 karatsuba 的搞法。

假设 A，B 长度都是 $2^n$，需要计算 $C=A\times B$，考虑按照下标的二进制最高位把 A,B,C 分成前后两半，即：

$$ \begin{aligned} A=\operatorname{concat}(A_0,A_1)\cr B=\operatorname{concat}(B_0,B_1)\cr C=\operatorname{concat}(C_0,C_1)\cr \end{aligned} $$

则有：

$$ \begin{aligned} C_0&=A_0\times B_0\cr C_1&=\max(A_1\times B_0,A_0\times B_1,A_1\times B_1)\cr &=\max (A_1\times B_0,\max(A_0,A_1)\times B_1) \end{aligned} $$

于是递归处理 3 个长度为 $2^{n-1}$ 的子问题即可。复杂度 $T(n)=3T(n-1)+O(2^n)=O(3^n)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


#define upd(i, j) c[i | j] = max(c[i | j], a[i] + b[j])
inline void solve(ll *a, ll *b, ll *c, ll *tmp, ll len) {
    if (len <= 4) {
        upd(0,0);upd(0,1);upd(0,2);upd(0,3);
        upd(1,0);upd(1,1);upd(1,2);upd(1,3);
        upd(2,0);upd(2,1);upd(2,2);upd(2,3);
        upd(3,0);upd(3,1);upd(3,2);upd(3,3);
        return;
    }
    ll hlen = len >> 1;
    solve(a, b, c, tmp, hlen);
    solve(a + hlen, b, c + hlen, tmp, hlen);
    for (ll i = hlen; i < len; i++) {
        tmp[i - hlen] = a[i];
        a[i] = max(a[i], a[i - hlen]);
    }
    solve(a + hlen, b + hlen, c + hlen, tmp + hlen, hlen);
    memcpy(a + hlen, tmp, sizeof(ll) * hlen);
}