P7213 [JOISC 2020] 最古の遺跡 3

CSP T4 究极加强版。

首先注意操作的性质，等价描述如下：

• 每次从 \(2n\) 到 \(1\)，遇到一个 \(h_i\)，如果此时后面有 \(h_j = h_i\)，那么便将 \(h_i\) 减一，不断重复这个过程，然后进行下一步操作。

因为只关心后缀，所以可以从一个位置 \(i\) 将 \([1, i - 1]\) 和 \([i + 1, n]\) 分开考虑，这也说明了上述这个过程是对的。

发现一个位置 \(i\) 被减为 \(0\) 当且仅当在 \(i\) 后面存在 \([1, h_i]\) 的连续段，考虑从后往前根据这个 DP。

设 \(f_{i, j}\) 表示考虑到 \(i\) 的后缀此时减完之后（保留那些还有的）的极长连续段为 \([1, j]\) 的方案数，考虑到转移：

• 该位置没有保留下来，设前面没有保留下来的个数为 \(cnt2\)，则有 \(f_{i + 1, j} \times (j - cnt2) \to f_{i, j}\)。
• 该位置保留下来，分成两种情况考虑：
  • 该位置填入 \(> j + 1\) 的数，此时我们利用贡献延后的 trick，将这一位选择什么交给后面的转移考虑，有 \(f_{i + 1, j} \to f_{i, j}\)。
  • 该位置填入 \(j + 1\)，我们枚举之前有多少个数是可以拼接上来的，不妨设有 \(k - 1\) 个（包含该位置填的数那么增量就是 \(k\)），设前面保留下来的位置数为 \(cnt\)，那么此时会选择 \(k - 1\) 个填入这些数的位置，方案数也就是 \(\binom{cnt - (j - k)}{k - 1}\)，还要乘上一个排列的系数，要预处理一个排列系数数组 \(g\)，仔细考虑一下即可。