NOMURA2020 F - Sorting Game

题意

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

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

对 $10^{9}+7$ 取模。

$1\le N,M\le 5000$

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

每一对逆序对需要进行一次交换。考虑两个位置 $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$ 种方案。

故总转移式是

$f_{i,j}=(j+1)f_{i-1,j}\sum_{k=2}^{j}f_{i-1,j-k+1}\times 2^{k-2}\times (j-k+1)$

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

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

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