本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-12 10:09:00

:::::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\le n\le 5000$
• $\forall i\in[1,n],1\le a_i,b_i\le 2n$
• $\forall i,j\in[1,n],a_i\ne b_j$
• $\forall i,j\in[1,n],i\ne j,a_i\ne a_j$
• $\forall i,j\in[1,n],i\ne j,b_i\ne b_j$
• $1\le q\le n+1$
• $0\le l\le r\le n$

时间限制：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$ 合法的条件转化为：

• $\forall i\in[1,|S|]，a_{S_i}>b_i$
• $\forall i\in[1,|S^{-1}|],a_{S^{-1}i}<b{i+|S|}$

Part 3：判定合法：

根据贪心策略易证，上面的条件就是 $S$ 合法的充要条件。

Part 4：计算答案：

重头戏来了。
考虑枚举 $|S|$，设 $f_{i,j}$ 为考虑到第 $i$ 个数，有 $j$ 个数在 $S$ 中的合法 $S$ 方案数，根据上述容易得到转移方程：
$$f_{i,j}=[a_i>b_j]f_{i-1,j-1}+[a_i<b_{|S|+i-j}]f_{i-1,j}$$ 这时 $f_{n,|S|}$ 就是 $ans_{|S|}$，对它求前缀和就可以做到 $\Theta(n^3+q)$，过不了，考虑优化。

不要把这四个过程完全割裂，有时算答案时也会出现转化，转化时顺便发掘了性质和判定，需要巧妙地选择进行哪一步。

Part 1：转化问题：

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

• $\forall i\in[1,|S|]，a_{S_i}>b_i$
• $\forall i\in[1,|S^{-1}|],a_{S^{-1}{|S^{-1}|-i+1}}<b{n-i+1}$

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}|$），所以我们继续转化条件：

• $\forall i\in[1,|S|]，a_{S_{|S|-i+1}}>b_{|S|-i+1}$
• $\forall i\in[1,|S^{-1}|],a_{S^{-1}i}<b{i+|S|}$

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

• $\forall i\in[1,k]\cap S^{-1},a_i<b_{|S|+p}$，其中 $p$ 是一个未知的正整数。
• $\forall i\in[k+1,n]\cap S,a_i>b_{|S|-p}$，其中 $p$ 是一个未知的非负整数。

Part 2：发掘性质：

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

• $\forall i\in[1,k]\cap S^{-1},a_i<b_{|S|}$
• $\forall i\in[k+1,n]\cap S,a_i>b_{|S|}$

所以我们得到 $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