Codeforces 1330D. Dreamoon Likes Sequences

正文索引 [隐藏]

题目链接: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$:

b_i = \begin{cases}
a_1, &i = 1, \\
b_{i-1}\ xor\ a_i, &i > 1.
\end{cases}

给定 $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$ 之和。

代码