P11781 [COTS 2012] 机器统计 / MULTI 题解

zrl123456 · 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