序列 题解

lndjy · 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) 。