题解：P16245 【MX-X27-T6】若然能将一切舍弃的话

· · 题解

先考虑 DP。用 f_i(n) 表示只考虑第 0\sim i-1 位，f(n,k) 的最大值。若 n\geq 2^{i-1}k，则 k 个数的第 i-1 位都可以放 1，对按位与值的贡献为 2^{i-1}。由于 f_{i-1}(x)\leq 2^{i-1}-1，所以此时必然是第 i-1 位全部放 1 最优。有递推式：

f_i(n)=f_{i-1}(n-2^{i-1}k)+2^{i-1}

若 n<2^{i-1}k，则

f_i(n)=\max_{0\leq t<k}f_{i-1}(n-2^{i-1}t) 先给出一个引理：已知非负整数序列 $c_{1\sim n}$ 满足 $\sum\limits_{i=0}^{m-1}c_i2^i\geq 2^m$，则必然存在一个非负整数序列 $d_{1\sim n}$，满足 $d_i\leq c_i$ 且 $\sum\limits_{i=0}^{m-1}d_i2^i=2^m$。 :::info[证明] 考虑一个多重集 $S$，由 $c_0$ 个 $2^0$、$c_1$ 个 $2^1$、……、$c_{m-1}$ 个 $2^{m-1}$ 组成。 枚举 $i=0\sim m-1$，对于每个 $i$，不断将两个 $2^i$ 合并成一个 $2^{i+1}$。 合并后，显然 $S$ 中 $\leq 2^{m-1}$ 的数的和至多为 $2^m-1$。而我们知道 $S$ 的元素和 $\geq 2^m$，因此合并后一定有 $2^m\in S$。$\Box

:::

接下来直接给出关键的引理：f_{i-1}(n+2^{i-1})\geq f_{i-1}(n)。

:::info[证明]

显然 f_{i-1}(x) 的定义域为 0\leq x\leq (2^{i-1}-1)k。任取一个 f_{i-1}(n) 的最优解，则剩余容量为 (2^{i-1}-1)k-n。而 n+2^{i-1}\leq (2^{i-1}-1)k，也就是说 (2^{i-1}-1)k-n\geq 2^{i-1}，根据引理，必然存在一种补充的方法，使得 x_i 之和恰为 n+2^{i-1}。显然对原来的最优解进行补充不会使按位与值变小。\Box

:::

这说明当 n<2^{i-1}k 时，我们只需要取 g(n) 为 \leq (2^{i-1}-1)k 的数中，模 2^{i-1} 与 n 同余的最大的数，然后令 f_i(n)=f_{i-1}(g(n)) 即可。

设 d=n-(2^{i-1}-1)k，不难得到 g(n) 的表达式：

g(n)=\begin{cases} n & \text{if } n\leq (2^{i-1}-1)k\\ n-\left\lceil\dfrac{d}{2^{i-1}}\right\rceil 2^{i-1} & \text{otherwise} \end{cases}

设 S_i(n)=\sum\limits_{x=0}^n f_i(x)，考虑如何对 S_i 递推。

当 n\leq (2^{i-1}-1)k 时，S_i(n)=S_{i-1}(n)。

当 (2^{i-1}-1)k<n<2^{i-1}k 时，注意到从 (2^{i-1}-1)k+1，g(n) 表现为

(2^{i-1}-1)k+1-2^{i-1},(2^{i-1}-1)k+2-2^{i-1},\cdots (2^{i-1}-1)k+2^{i-1}-2^{i-1}

的循环。设 d=n-(2^{i-1}-1)k，r=d\bmod 2^{i-1}，可以得到

\begin{align*} S_i(n)&=S_{i-1}((2^{i-1}-1)k)\\ &\quad +\left(S_{i-1}((2^{i-1}-1)k)-S_{i-1}((2^{i-1}-1)k-2^{i-1})\right)\left\lfloor\frac{d}{2^{i-1}}\right\rfloor\\ &\quad +S_{i-1}((2^{i-1}-1)k+r-2^{i-1})-S_{i-1}((2^{i-1}-1)k-2^{i-1}) \end{align*}

当 n\geq 2^{i-1}k 时，设 r=(k-1)\bmod 2^{i-1}，可以得出

\begin{align*} S_i(n)&=S_{i-1}((2^{i-1}-1)k)\\ &\quad +\left(S_{i-1}((2^{i-1}-1)k)-S_{i-1}((2^{i-1}-1)k-2^{i-1})\right)\left\lfloor\frac{k-1}{2^{i-1}}\right\rfloor\\ &\quad +S_{i-1}((2^{i-1}-1)k+r-2^{i-1})-S_{i-1}((2^{i-1}-1)k-2^{i-1})\\ &\quad +2^{i-1}(n-2^{i-1}k+1)+S_{i-1}(n-2^{i-1}k) \end{align*}

取最小的 i 使得 r\leq (2^i-1)k，递归计算 S_i(l-1) 和 S_i(r) 即可，需要记忆化。

分析一下时间复杂度。观察转移，发现一个状态 S_i(n) 往 S_{i-1} 递归时，会用到一个和 n 有关的子状态和至多三个和 n 无关的子状态。设 T_j 为 S_j 的状态数，则 T_j\leq T_{j+1}+3，也就是说 T_j 是线性增长的。而递归层数是 \mathcal{O}(\log{r})，因此总状态数是 \mathcal{O}(\log^2{r}) 级别的。使用哈希表记忆化即可做到 \mathcal{O}(\log^2{r}) 的时间复杂度。

实现上比较卡常，我手写哈希表才能通过。

:::success[主要代码]

i128 prefix(int i, ll n) {
    if (!i || n <= 0) return 0;
    ll base = k * ((1ll << i - 1) - 1);
    i128 val1, val2, res;
    if (ht[i].query(n, res)) return res;
    if (n > base) {
        val1 = prefix(i - 1, base);
        val2 = prefix(i - 1, base - (1ll << i - 1));
    }
    auto calc = [&](ll d) -> i128 {
        return (val1 - val2) * (d >> i - 1) + prefix(i - 1, base + (d & ((1ll << i - 1) - 1)) - (1ll << i - 1)) - val2;
    };
    if (n <= base) res = prefix(i - 1, n);
    else if (n < (k << i - 1)) res = val1 + calc(n - base);
    else res = val1 + calc(k - 1) + ((i128)(n - (k << i - 1) + 1) << i - 1) + prefix(i - 1, n - (k << i - 1));
    ht[i].ins(n, res);
    return res;
}

:::