AtCoder NOMURA2020 F - Sorting Game

Tangninghaha · 2025-01-09 22:38:36 · 题解

Problme Statement

题意

对于一个长度为 M，值域为 [0,2^{N}) 的一个整数序列，

• Alice 先进行若干次操作，每一次操作选择一位，将序列中 所有数 二进制下这一位的值变为 0。

• Bob 接着可以进行若干次操作，每一次操作选择 相邻 两个数字，且这两个数字在二进制下有 恰好 一位不同，可以将这两个数交换。

求在可能的 2^{NM} 种序列中，有多少种序列，满足无论 Alice 如何操作，Bob 总存在一种操作方式，使得最后序列不降？

对 10^{9}+7 取模。

解法

Hint

寻找充要条件，再进行 DP 计数。

Solution

每一对逆序对需要进行一次交换。考虑两个位置 x 和 y，满足在第 d 位，x 为 1 而 y 为 0。如果有多个位满足 x 为 1，y 为 0，考虑最高的位。

我们断言，x 和 y 低于 d 的位相等，是 Bob 能够操作成升序的充要条件。

充分性：比 d 更高的位，若这些位 x 小于 y，则不满足逆序关系，无需考虑交换；若 x 大于 y，则 d 不是最高的满足条件的位。所以更高位也是相等的，所以 x 和 y 只有一个位（即 d）不同，可以交换。

必要性：如果 x 和 y 低于 d 的位不相等，找到不相等的位，只要 Alice 不操作这一位，Bob 就无法交换 x 和 y，必定无解。

那么，容易发现，某一位 d 第一个 1 到最后一个 0 之间的数，其低于 d 的位均相等。

考虑 DP 计数。从高位考虑到低位，先考虑填最高位。最高位是形如

000...00 | 1?????0 | 11...111

即先是一段连续的 0，再是 1 和 0 中间随便包裹一些东西，最后是一段 1，可能没有第二段。

最高位填完之后，第二段后面的位要相等，不妨视作一个数，而第一段和第三段对后面的位没有限制，相当于一个子问题，所以考虑设 f_{i,j} 表示有 i 位，长度为 j 的序列的合法方案数。

转移枚举第二段长度 k，系数有两部分：中间问号可以随便填，有系数 2^{k-2}。第二段可以钦定开始位置，有 j-k+1 种开始位置，有系数 j-k+1，子问题为 f_{i-1,j-k+1}。

还有一种情况是没有第二段，这时候考虑最高位填多少个 0，有 j+1 种方案。

故总转移式是

这样可以做到 O(nm^2)

进一步地，后面一部分可以简单地使用前缀和进行优化，做到 O(nm) 的复杂度，足以通过此题。

然而 wtc 有一种 O(n) 的做法...

Submission