自动搬运

查看原文

来自洛谷，原作者为

	lndjy 退役oier，偶尔参与比赛出题，tag是我另一个身份，有人认识吗（）

搬运于2025-08-24 22:32:27，当前版本为作者最后更新于2020-08-03 15:33:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

序列 题解

upd:修了一下 LaTeX。

Subtask 1

答案显然是 $k+1$。

Subtask 2

根据乘法原理，答案为 $(k+1)^n$。

Subtask 3

暴力枚举序列每一个数的值然后判断是否满足条件。

Subtask 4

两个数异或和为 $0$ 就是两个数相等，那么如果把限制加边，答案就是 $k+1$ 的联通块个数次方。

Subtask 5

根据 Sub 4，可以想到统计每个联通块的方案数乘起来。对于每个联通块，暴力枚举第一个数的值，这样所有数都是确定的。然后判断是否都不大于 $k$。

时间复杂度 $O(nk)$。

Subtask 6

数据随机，很容易出现无解，输出 $0$ 即可。这个 Sub 来源是我原来没意识到这点导致最后一个子任务答案全是 $0$（（（

Subtask 7

延续 Sub 4,5 的想法，我们要快速计算第一个数有多少取值。

因为异或的结合律，所以联通块每一个数都是第一个数异或路径上数的异或和，如果路径上数异或和不唯一则无解。将这些数插入 01 trie，问题就转换为“有多少个数，使它与 trie 树中所有值的异或结果最大值不超过 $x$ ”。

下面，来分析怎么解决这个问题。

我们在 trie 树上 dfs ，用 $dfs(now,d,val)$ 表示处理到了节点 $now$ ，当前为第 $d$ 位，当前值为 $val$ 。对于 trie 树上的每个节点，根据儿子个数讨论。

• 没有儿子，则代表处理到了叶子。此时若值不大于 $x$ ，则返回 $1$ 。否则返回 $0$ 。
• 有两个儿子，则无论当前位填什么数，最大值都会出现在“对面”子树中。因此，我们将当前值加上 $2^d$ ，然后递归处理 $0/1$ 两棵子树。
• 只有一个儿子（假设为 $0$ 儿子），我们判断 $val+2^d$ 不大于 $x$ 是否成立。

1. 若成立，则当前位填 $0$ 时，后面位无论填什么都满足条件，因此填 $0$ 时答案为 $2^d$ ，填 $1$ 时，当前值加上 $2^d$ ，处理 $0$ 儿子。

2. 若不成立，则当前位只能填 $0$ 。当前值不变，处理 $0$ 儿子。

这样，每个节点只会被处理一次。

时间复杂度为 $O(n\log k)$ 。