「JOISC 2020 Day2」遗迹

题目大意：

给定长度为 \(2n\) 的序列 \(h_i\)，满足对于所有 \(k \in [1,n]\)，均存在两个 \(i\) 满足 \(h_i = k\)，定义“地震”为如下操作：

• 对于所有 \(i \in [1,2n]\)，当且仅当 \(h_i > 0\) 且对于所有 \(j > i\) 都有 \(h_i \neq h_i\) 时，\(h_i \leftarrow h_i - 1\)

现进行了 \(n\) 次地震，最终有 \(n\) 个 \(h\) 依然不为 \(0\)，给定最终不为 \(0\) 的位置，要求求出初始可能的 \(h\) 的方案数。

做法

设 \(h_i\) 最终变为 \(h'_i\)。

首先考虑当给定初态时如何求末态。从后往前考虑，假设已存在的当前包含 \(h_i\) 的极长值域段为 \([k, h_i]\)，则 \(h'_i = k - 1\)。

这启发我们从后往前 dp。考虑到 \(h'_i = 0\) 当且仅当此时 \([1,h_i]\) 均已存在，我们设计如下状态：\(f_{i,j}\) 表示从后往前处理到第 \(i\) 个数，当前包含 \(1\) 的极长值域段为 \([1,j]\) 的方案数，为方便转移，我们区分相同的两个 \(h\)，同时设 \(h'_{i + 1}\) ~ \(h'_{2n}\) 中有 \(c0\) 个 \(0\)，\(c1\) 个非 \(0\)。

先对 \(h'_i\) 是否为 \(0\) 讨论：

• 若 \(h'_i = 0\)，则 \(h_i\) 可取 \([1,j]\) 中的任意值，从 \(f_{i+1,j}\) 转移，但需要注意先前已经存在于 \([1,j]\) 的 \((j + c0)\) 个数，因此转移系数为 \((j - c0)\)。
• 若 \(h'_i \neq 0\)，等价于 \(h'_i > j\)。还需讨论取值。
  1. 若 \(h'_i > j + 1\)，则包含 \(1\) 的极长连续段未改变，先不统计方案数，因此 \(f_{i + 1, j} \rightarrow f_{i,j}\) 即可。
  2. 若 \(h'_i = j + 1\)，则可能有两个连续段发生合并，再枚举 \(k\) 表示转移到 \(f_{i,k}\)。首先选定合并的连续段在 \(h\) 中的位置，系数为 \(\binom{c1-j}{k-j-1}\)，然后考虑 \(h_i\) 的可能取值，可取 \([j + 1,k]\) 中的任意值，因此系数为 \(k - j + 1\)。最后 \([j + 2,k]\) 待定，设这部分系数为 \(g_{k-j-1}\)。

若能预处理 \(g\)，则可以在 \(O(n^3)\) 复杂度内解决问题。

下面考虑求 \(g\)，\(g_n\) 表示 \(n\) 个数最终值域变为 \([1,n]\) 的方案数。枚举第一个数，即可得

直接转移即可。总复杂度 \(O(n^3)\)。