[JOISC2020] 最古の遺跡 3
可以发现，第 \(i\) 根柱子最后的位置在所有曾经为 \(i\) 的位置中最大的。记 \(T_i\) 表示最终保留高度 \(i\) 的柱子编号。
考虑按照值域从大到小扫描，维护一个集合 \(S\) 表示尚未留下的位置集合，每次执行：
- \(S\gets S\cup \{X_i, Y_i\}\)
- \(T_i\gets \max S\)
- \(S\gets S\setminus \{T_i\}\)
但不太好转移。考虑从位置的角度刻画问题。
从后往前依次确定每一位的权值。可以发现，\(i\) 的最终权值为最大的 \(v\) 满足 \(v\leq a_i\) 且 \(\forall j>i, a'_j\not=v\)。
考虑设 \(f_{i,j}\) 表示后 \(i\) 个位置，\(1\sim j\) 都被占用而且 \(j+1\) 未被占用的方案数。
为方便转移，将相同的数看成不同的，最后答案乘以 \(\dfrac{1}{2^n}\)。
同时为了满足无后效性，我们不去关注初始权值 \(>j+1\) 的位置的具体取值造成的区别，也不关注由于两个 \(>j+1\) 位置之间造成的不合法性。
形式化地，我们用 \(f_{i,j}\) 对 \(a_{i\sim 2n}\) 计数，其满足：
- \(a\) 由 \(1\sim 2j\) 以及 \(*\) 构成，且 \(1\sim 2j\) 最多出现一次。
- 将所有非 \(*\) 位置提取出来组成序列 \(a'\) 并让所有 \(a'_x\gets \lceil\frac{a'_x}{2}\rceil\) 后，该序列进行题目中描述的操作后得到的最终序列中 \(1\sim j\) 都各有一个，且是否为 \(0\) 与题目中给定的限制相同。
- 所有 \(*\) 所在的位置都必须是最终不为 \(0\) 的位置。
注意到 \(\dfrac{f_{1,n}}{2^n}\) 就是最终的答案，因为此时计数的 \(a\) 序列中不可能有 \(*\)。
记 \(i+1\sim 2n\) 中有 \(c_1\) 个被钦定，\(c_0\) 个被舍弃。
考虑转移。
如果 \(a_i\) 最终为 \(0\)，则 \(a_i\) 只能为数字，它只能从 \(f_{i+1,j}\) 转移过来，此时 \(a_i\) 取值范围为 \([1,2j]\)，但其中恰好有 \(j+c_0\) 个已选，所以系数为 \((2j-j-c_0)=j-c_0\)。
如果 \(a_i\) 最终不为 \(0\)，则分类讨论：
- \(a_i\) 为 \(*\)，此时 \(f_{i,j}\gets f_{i+1, j}\)。
- \(a_i\) 为数字。
考虑枚举 \(a_i\) 最终权值是多少，记为 \(k\)。不难意识到 \(a_{i+1\sim 2n}\) 得到最终序列值域为 \([1,k)\cup(k,j]\)。问题变为先让 \(a_{i+1\sim 2n}\) 的值域变为 \([1,k)\cup (k,j]\)，然后再让 \(a_i\) 变为 \(k\)，此时 \(a_i\) 有 \(j-k+2\) 种取值。
注意到 \(k\) 作为分界点将问题分为两个部分，使得初始值和最终值不会跨过该点。因此考虑分开计算两个部分的贡献，发现 \((k, j]\) 对于 \([1,k)\) 的部分不会产生贡献，可以将其视为 \(*\)，所以 \([1,k)\) 部分的答案为 \(f_{i+1,k-1}\)，对于 \((k,j]\) 的答案可以看成先区分出数字和 \(*\)，然后再使得恰好为 \((k,j]\)。区分的贡献为 \(\binom{c_1-(k-1)}{j-k}\)，而使用 \((k,j]\) 中的数字使得最终恰好构成 \((k,j]\) 可以被平移到 \([1,j-k]\) 上。设其为 \(g(j-k)\)。
则贡献为 \(\displaystyle f_{i,j}\gets \sum_k f_{i+1, k-1}\times \binom{c_1-k+1}{j-k}\times (j-k+2)\times g(j-k)\)
关键在于计算 \(g(i)\)，其表示用 \(1,1,2,2,3,3\cdots i,i\) 组成序列能够使得最终值域为 \([1,i]\) 的方案数。不难发现和 \(f\) 是很像的。
同样考虑枚举 \(a_i\)，有 \(\displaystyle g(i)=\sum_j \binom{i-1}{j-1} g(j-1)\times g(i-j)\times (i-j+2)\)。
复杂度 \(\mathcal O(n^3)\)。