WNJXYKの博客

题目链接：CF #631 Div.2D

题目大意

假设你有一个序列 $a$ 长度为 $n$ 且满足 $1\leq a_1<a_2<\ldots<a_n \leq d$。同时我们要能由序列 $a$ 可以得到一个满足 $1\leq b_1<b2<\cdots<b_n$ 条件的序列 $b$：

给定 $d$ 问符合条件的序列 $a$ 有多少个，答案对 $M$ 取模。

题解

直接拿样例 OEIS，能找到一个符合要求的数列 A293711，然而它的公式并无用处，所以只能老老实实地做题。

随便画几个小样例，很容易就找一个比较明显的规律：$maxBit(a_{i+1}) > maxBit(a_i), i \in [1, n)$。其中 $maxBit(x)$ 能求出 $x$ 中最高位得二进制 1，比如 $maxBit(10_{10}) = maxBit(1010_{2}) = 1000_{2} = 8_{10}$。

这个规律与题目要求等价得证明十分简单：

充分性：如果有 $maxBit(a_{i+1}) > maxBit(a_i), i\in[1, n)$，那么一定有 $a_{i+1} > a_i, i \in [1, n)$ 与 $b_{i+1} > b_i, i \in [1, n)$。
前半部分可以通过二进制的性质与简单缩放得到这个结论，假设 $maxBit(a_{i+1}) = p$，那么有 $a_{i+1} \geq 2^p > \sum_{i=0}^{p-1} 2_i \geq a_i$。
后半部分，我们可以先由 $maxBit(a_{i}) > maxBit(a_{i-1}) > \cdots > maxBit(a_1)$ 得知 $maxBit(a_{i})$ 这个二进制位在 $a_1\cdots a_{i}$ 中第一次于 $a_{i}$ 中出现。又因为 $b_{i} = a_{i}~xor~a_{i-1}~xor~ \cdots ~xor~a_1$，所以 $maxBit(b_i) = maxBit(a_i),i\in[1, n]$，然后按照前半部分的推导即可得到结论。

必要性：$a_{i+1} > a_i, i \in [1, n)$ 与 $b_{i+1} > b_i, i \in [1, n)$ 可以推出 $maxBit(a_{i+1}) > maxBit(a_i), i \in [1, n)$。

这里我们用反证法，在满足题目条件的情况下，假设存在很多个位置不满足我们要推出的条件，我们找到最小的一个不满足条件的 $i$，那么有 $maxBit(a_{i+1}) \leq maxBit(a_i)$，又因为 $a_{i+1} > a{i}$，所以有 $maxBit(a_{i+1}) = maxBit(a_i)$。
假设 $maxBit(a_{i+1}) = maxBit(a_i) = p$，因为我们找的是第一个不满足条件的 i，所以在 $a_1, \cdots, a_{i+1}$ 中，最大的二进制位为 $p$ 且仅 $a_i, a_{i+1}$ 拥有它。
那么可以得到 $maxBit(b_{i+1}) < p = maxBit(b_i)$，即 $b_{i+1}<b_{i}$，矛盾。
所以原假设不成立，必要性得证。

一旦有了这个规律：$maxBit(a_{i+1}) > maxBit(a_i), i \in[1, n)$，题目就很简单了。
序列的长度 $n$ 小于等于 $\lfloor\log_2 d \rfloor + 1 \approx 30$，这样我们就可以进行 DP 了。

$dp[i][j]$ 表示长度为 i 的序列，结尾数字的 $maxBit$ 为 $2^j$ 的方案数。
转移方程为 $dp[i][j] = \sum_{k=0}^{j-1} dp[i-1][k] \times cnt(j)$，即我们要在长度为 $i-1$ 的序列末尾接上一个新的数字，$maxBit$ 为 $2^j$，那么之前的序列末尾的 $maxBit$ 为 $2^k$ 应该有 $k<j$。
最后就是 $cnt(j)$ 是什么，它是二进制最高位为 $2^j$ 的数字的个数。因为有结论，我们得知除了对数字的 $maxBit$ 有限制，其他都随便填且不能超过范围 $d$。这个很好算其实就是不超过 $d$ 二进制位 $j$ 为 1 的数字个数： cnt[j] = min(d, (2<<j) - 1) - (1<<j) + 1。

最终答案就是所有的 $dp$ 之和。

代码