本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-22 16:36:24

:::::info[闲话] 模拟赛 T2，不会做（其实 T1 也不会），菜完了。
::::: :::::info[题目基本信息] 考察：数学，组合数学，动态规划 DP（个人认为中下位紫）。
题目简介：
给定 $\{a_n\},\{b_n\}$ 及常数 $k$，$q$ 次询问，每次询问给定 $x,y$，求当 $a_{n+1}=x,b_{n+1}=y$ 时有多少有序数对集合 $S$ 满足（对 $10^4+9$ 取模）：

• $|S|=k$
• $\forall(x_1,y_1),(x_2,y_2)\in S,(x_1,y_1)\ne (x_2,y_2)\Rightarrow x_1\ne x_2\land y_1\ne y_2$
• $\forall(x,y)\in S,\exists i\in[1,n+1],x<a_i\land y<b_i$

数据范围：

• $1\le n,q\le 10^5$
• $1\le k\le 30$
• $\forall i\in[1,n],1\le a_i,b_i\le 10^5$
• $1\le x,y\le 10^5$ ::::: 由于个人习惯，我们令 $a_i\leftarrow a_i-1,b_i\leftarrow b_i-1$，这样上面 $x<a_i\land y<b_i$ 的条件就可以取等了。
  把图画出来：
  
  注意到这些点位置合理的充要条件是位于这些红线（最高的一条，横坐标为 $i$ 的最上方的一条的纵坐标设为 $mx_i$）的下方，那么这就是经典 trick：从限制紧的部分开始决策，这样前面的决策一定会限制后面的决策，那么对于没有新加点的情况，我们容易设出如下 DP：
  设 $f_{i,j}$ 表示从右往左考虑到横坐标为 $i$ 的一列，选择了 $j$ 个点的方案数，那么容易得到状态转移方程：
  $$f_{i,j}=f_{i+1,j}+f_{i+1,j-1}\cdot\max(0,mx_i-j+1)$$ 这是没有新加点的情况，做 $q$ 次能得到 $\Theta(Vqk)$ 的时间复杂度，能过 $55$ 分。
  考虑新加一个点，画图可知它会覆盖中间连续的一段 $mx_i$，那么我们可以考虑把前后缀分别处理再拼起来。
  再设 $g_{i,j}$ 表示从左往右考虑到横坐标为 $i$ 的一列，从第 $i$ 列向右（包括该列）选择了 $j$ 个点的方案数，容易类比得到状态转移方程：
  $$g_{i,j}=g_{i-1,j}+g_{i-1,j+1}\cdot\max(0,mx_i-j)$$ 现在我们预处理好了 $f$ 和 $g$，现在将它们拼起来，首先容易二分出未被覆盖的部分和被覆盖的部分的分界点（为方便 $f$ 的分界点设为 $p$，$g$ 的分界点设为 $q$），然后枚举 $j_f$ 和 $j_g$ 分别表示 $f$ 和 $g$ 的第二维分别是多少，这样还有 $q-p+1$ 列可以填，选择 $j_g-j_f$ 列，容易得到这一种的贡献：
  $$f_{p+1,j_f}g_{p-1,j_g}\binom{q-p+1}{j_g-j_f}(b-j_f)^{\underline{j_g-j_f}}$$ 全部累加起来即可，精细实现即可通过本题。
  时间复杂度为 $\Theta(n+Vk+qk^2)$，空间复杂度为 $\Theta(Vk)$。

code