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

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

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

代码