P12558 [UOI 2024] Heroes and Monsters 题解

· · 题解

:::::info[题目基本信息] 考察：动态规划 DP（NOI/NOI+/CTSC）。
题目简介：
给定 n 以及 \{a_n\},\{b_n\}，q 次询问，每次给定 l,r，求：

(\sum_{S\subseteq\bigcup_{i=1}^n\{i\},|S|\in[l,r]}[\exist\{p_n\}\in\{\{x_n\}|\forall i\in[1,n],x_i\in[1,n]\land\forall i,j\in[1,n],i\ne j,x_i\ne x_j\},\forall i\in[1,n],[i\in S]=[a_i>b_{p_i}]])\bmod 998244353

数据范围：

时间限制：1.5s。
空间限制：1GB。
::::: 计数题大部分时候会经历转化问题、发掘性质，判定合法，计算答案四个过程（不要把这四个过程完全割裂，有时算答案时也会出现转化，转化时顺便发掘了性质和判定，需要巧妙地选择进行哪一步），虽然一般这前三个部分一般不难但也许会给我们做 DP 和计数提供思考方向。一个好的例子是 CF2150D，在这道题中这三个过程体现得淋漓尽致。
我们先来暴力。

Part 1：转化问题：

这一步还是比较关键的。
贪心地想，如果 S 中的元素能够大于 \{b_n\} 中的元素，那么肯定是大于了 \{b_n\} 中的前 |S| 个元素，不在 S 中的元素同理。
那么我们先设 S^{-1}=\complement_{\bigcup_{i=1}^n\{i\}}S，对 \{a_n\} 和 \{b_n\} 升序排序，同时也令 S 和 S^{-1} 转变成一个有序数列，以编号大小升序排序，那么 S 合法的条件转化为：

Part 1：转化问题：

由于原条件中含有 |S|，考虑消掉 |S|，那么我们可以转化为：

Part 4：计算答案：

我们现在消去了 |S|，就可以只进行 \Theta(1) 次 DP，同时由于原条件中两个条件互相独立，所以我们考虑对前缀和后缀分别 DP。
更加具体地，对前缀 DP 时设 f_{i,j} 表示考虑到了长度为 i 的前缀，有 j 个元素在 S 中的 S 方案数，容易得出状态转移方程：

f_{i,j}=f_{i-1,j}+[a_i>b_j]f_{i-1,j-1}

同样的，设出 g_{i,j} 的状态为考虑到了长度为 i 的后缀，有 j 个元素不在 S 中的 S 方案数，并得出状态转移方程：

g_{i,j}=g_{i+1,j}+[a_i>b_{n-j+1}]g_{i+1,j-1}

现在，我们求出了 f_{i,j} 和 g_{i,j}，考虑如何计算 \{ans_n\}。

Part 1：转化问题：

显然我们不能直接找一个位置 k 直接拼起来 f_{k,j} 和 g_{k+1,j}，因为可能前缀的一些不在 S 中的和后缀的一些在 S 中的不合法，所以我们考虑找到一个符合条件的 k。
由于现在 |S| 已知，我们希望条件中出现 |S|（以及 |S^{-1}|），所以我们继续转化条件：

容易得到位置 k 合法的条件：

Part 2：发掘性质：

我们注意到当 p\ge 0 时，b_{|S|-p}\le b_{|S|}\le b_{|S|+p}，所以条件弱化为：

所以我们得到 k 就是最大的整数满足 a_i<b_{|S|}，这个可以使用双指针或者二分得到。

Part 4：计算答案：

最终，我们终于要计算 \{ans_n\} 了。
容易得到：

ans_p=\sum_{i=\max(0,p+k-n)}^{\min(k,p)}f_{k,i}g_{k+1,n-p-k-i}

其中，所有上界和下界均为了保证 f 和 g 存在。
然后做个前缀和就做完了。
时间复杂度为 \Theta(n^2+q)，空间复杂度为 \Theta(n^2)。

code