max+或卷积

max+或卷积 - Blog E

定义 C=A×BC=A\times BC=A×B 满足 Ci=max⁡j∨k=i(Aj+Bk)C_i=\max_{j\lor k=i}(A_j+B_k)Ci​=maxj∨k=i​(Aj​+Bk​)。

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

考虑用类似 karatsuba 的搞法。

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

A=concat⁡(A0,A1)B=concat⁡(B0,B1)C=concat⁡(C0,C1)\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}A=concat(A0​,A1​)B=concat(B0​,B1​)C=concat(C0​,C1​)​

C0=A0×B0C1=max⁡(A1×B0,A0×B1,A1×B1)=max⁡(A1×B0,max⁡(A0,A1)×B1)\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}C0​C1​​=A0​×B0​=max(A1​×B0​,A0​×B1​,A1​×B1​)=max(A1​×B0​,max(A0​,A1​)×B1​)​

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

#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);
}

作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接

阅读量 4

• Previous
  USACO 2022 一月月赛铂金组 T1 题解