题解：P7213 [JOISC 2020] 最古の遺跡 3

wmrqwq · 2025-11-18 11:25:05 · 题解

我计数咋这么菜。

题目链接

P7213 - [JOISC 2020] 最古の遺跡 3

解题思路 & 参考代码

贡献延后转移 trick。

首先我们容易注意到对于一个合法的初始石柱状态，最终一定只会剩下 1 \sim n 中的数，且每个数恰好出现一次。

具体证明就是，初始 1 \sim n 所有数出现 2 次，显然的，对于一个数 x 若出现了两次，则一次操作会将其中一个 x 变为 x-1，若 x-1 也有两个数，则其中一个 x-1 会变为 x-2，因此，一次操作后，所有的数字出现个数仍然 \le 2，该结论成立。

考虑刻画这个形式，容易发现为遍历 i = n,n-1,\dots,2,1，把最后一个 \ge i 且之前未被标记过的数标记，最终被标记的位置就为原序列的最终石柱位置。

但是这东西不好直接做，考虑直接对着原序列 a 进行刻画，可以发现我们可以直接遍历 i = 2n,2n-1,\dots,2,1，同时在遍历过程中维护一个集合 S，如果此时 S 中包含了 1,2,3,\dots,a_i，那么 i 不能被加入 S 内，否则我们可以往 S 内加入一个最大的 \le a_i 的不在 S 中的数，设其为 a_i'（若没有则 a_i' = 0），此时 i 为其中一个最终石柱位置。

容易注意到这两个东西事实上是等价的，所以这样是对的。

刻画完后，我们可以考虑 dp。

为了方便，我们在下文转移时钦定所有数均是不同的，最后将答案乘上 \displaystyle\frac{1}{2^n} 即可。

假设从后往前第 i 个位置之前（不含第 i 个位置）已经有 s_0 个位置不为最终石柱位置，s_1 个位置为最终石柱位置。

设 f_{i,j} 表示考虑了后 i \sim 2n 个数，S 中含有 1 \sim j 且不含有 j+1 的方案数，考虑如何转移 f_{i,j}：

• 如果我们钦定第 i 个位置不为最终石柱位置，那么权值可以从 1 \sim j 中选取，由于之前最终石柱位置选取了 j 个，不在最终石柱位置的位置有 s_0 个，那么方案数就为 (j - s_0)，有转移： (j-s_0)f_{i+1,j} \to f_{i,j}
• 如果我们钦定第 i 个位置为最终石柱位置，可以进行以下分讨：
  • 若 a_i \ge a_i' > j + 1，考虑延后转移，即： f_{i+1,j} \to f_{i,j}
  • 否则有 a_i' = j + 1，那么此时 j 会改变，枚举 j 变为了 k \in [j+1,s_1+1]，那么我们需要把延迟转移的 a' 拿来填 [j+2,k]：
  • 显而易见的，决定延迟转移的柱子数量为 (s_1 - j)，选其中的 k - (j + 2) + 1 = k-j-1，为 \displaystyle\binom{s_1 - j}{k-j-1}。
  • 然后我们需要考虑 a_i 必须要满足 a_i' = j + 1 \le a_i \le k，有 (k - j + 1) 种方案。
  • 这里我们需要设一个 g_x 表示有 x 根柱子，操作后高度 a' 连续的方案数，因此我们需要带一个 g_{k-j-1} 的系数，有转移： f_{i+1,j}\displaystyle\binom{s_1 - j}{k-j-1}(k - j + 1)g_{k-j-1} \to f_{i,k}

考虑如何转移 g_x，可以枚举第一根柱子的最终高度 i，然后之后的 x-1 根柱子需要选取 i-1 个位置，方案数即为 \displaystyle\binom{x-1}{i-1}，同时容易注意到 <i 与 >i 的部分是相互独立的，所以可以直接乘上 f_{i-1}f_{x-i}，考虑 a_1 的方案数，i \le a_1 初始有 2(x-i-1) 种，由于有 x-i 种已经被选过了，因此还剩下 (x - i + 2) 种，因此有转移：