P7213 [JOISC2020] 最古の遺跡 3

这个题刚好是一个月前我们学校联赛组的人考的题的 T4 。今天有幸看见原题。

我当时顺便看了他们的题。想了一个小时，才想出来了如下的麻烦做法。

然后教练让我来讲这个题，我讲得很累，大家也都没有改。

题意：

有一个初始序列 \(a_1,a_2,…,a_{2n}\) ，其中满足 \(1\le i\le n\) 的 \(i\) 一定出现恰好两次。

你会进行若干轮操作，每次从前往后依次考虑每个 \(i\)，如果 \(a_i>0\) 且存在 \(i<j\) 满足 \(a_j=a_i\) ，那么就 \(a_i\) 就将减少 \(1\) 。

最后会有 \(n\) 个位置满足 \(a_i>0\) 。给定这 \(n\) 个位置，求有多少个初始的 \(a\) 满足条件。

做法：

令一个可重集 \(S\) 的“生成序列”\(s_i\) 满足 \(s_i=\sum_{x\in S} [x\le i]\) 。我们把那些最后 \(a_i>0\) 的位置涂成黑色。

令 \(M(S)\) 是满足 \(s_i=i\) 的最大的 \(i\) 。

考虑从后往前填初始的 \(a_i\)。如果一个位置是黑色的，那填入的权值 \(x\) 需要满足 \(x>M(S)\) ，然后把 \(x\) 加进 \(S\) ,否则，需要满足 \(x\le M(S)\) 。（这里的正确性读者自行思考。

我们要关注 \(M(S)\) 的变化，因为 \(x\) 的范围也随之变化。

令 \(dp_{i,j}\) 表示，从第 \(2n\) 个格子到第 \(i\) 个格子，当前 \(M(S)=j\) 。

1.加入黑色格子

在加入一个黑色位置时，我们不急着往里面填数。我们只会填那些满足 \(x_i\le M(S)\) 的数。

在 \(M(S)\) 发生变化，从 \(m\) 变成 \(m'\) 时，在空格子里选 \(m-m'\) 个，强令他们满足 \(m<x\le m'\) 。并且要选最后一个。设当前考虑到了第 \(i\) 个黑格子，则选择位置的方案数是 \(\tbinom{i-m-1}{m'-m-1}\) 。

现在我们填这 \(L=m'-m\) 个空格。令 \(g_i\) 是从前往后这些空格填的数， \(b_i=g_i-m\) ，则 \(1\le b_i\le L\) 。(填 g 的方案数只与 \(L\) 相关。我们设这里的方案是 \(F_L\) 。)

如果把 \(b_1\) 到 \(b_{L-1}\) 加入一个集合 \(T\) ,则 \(M(T)=0\) 。也就是说，\(T\) 的生成序列 \(s\) 满足，对于 \(i\geq 1\) ，都有 \(s_i<i\) 。

现在考虑从 \(1\) 到 \(L\) 把权值填入 \(b\) 中。在状态中记录前 \(L-1\) 个里已经填了 \(j\) 个，并且最后一个是否被填。即 \(f_{i,j,0/1}\) 。转移读者自行思考。

显然 \(F_L=f_{L,L-1,1}\) 。

有 \(dp_{i+1,m}\tbinom{z-m-1}{m'-m-1}F_{m'-m-1}->dp_{i,m'}\) ，其中 \(z\) 是 \(i\) 到 \(2n\) 中黑格子的个数。

当然，\(M(S)\) 没有改变的话，因为暂时不填，有 \(dp_{i+1,m}->dp_{i,m}\) 。

2.加入白色格子

在加入这个格子之前，有恰好 \(m\) 个黑格子满足权值 \(\le m\) ，并且白格子都满足 \(\le m\)。

令前面有 \(p\) 个白格子，则只剩下 \(m-p\) 种可能。但有一些权值会出现两次，这就算重了。

3.处理重复的问题，填黑色格子对后面白色格子的影响

\(M(S)\) 从 \(m\) 到 \(m'\) ，相当于权值在 \((m,m']\) 的数，有一半填入黑色格子，有一半留着给白色格子。

如果有一个权值，在黑格子中没出现，在白格子中出现两次，则它会使答案除以 \(2\) 。

所以我们重定义 \(F_i\) ，令 \(1\le i\le L\) 中没出现过的权值个数有 \(c\) 个，则 \(F_L\) 表示所有方案的 \(2^{-c}\) 的和。

这样就解决了白格子的重复问题。

复杂度是 \(O(n^3)\) 。

巴特西