CF1580B Mathematics Curriculum 做题记录

求满足以下条件的排列个数：

• 长度为 $n$。
• 恰有 $k$ 个数满足：所有包含这个数的区间中，不同的最大值的个数恰有 $m$ 个。

答案对 $p$ 取模。

$1 \le n \le 100, 1 \le m \le n, 1 \le k \le n, 1 \le p \le 10^9$。

首先定义 $i-\text{好数}$ 为所有包含这个数的区间中，不同的最大值恰好有 $i$ 个的数，问题就变成了求 $m-\text{好数}$ 恰好有 $k$ 个的 $n$ 的排列的个数。

设 $dp_{i,j,k}$ 为满足恰好有 $k$ 个 $j-\text{好数}$ 的 $i$ 的排列个数，那么可以通过枚举最大值的位置 $p$ 和 $p$ 左侧序列的 $(j-1)-\text{好数}$ 个数来转移：

$dp_{i,j,k}=\sum\limits_{p=2}^{i-1}\dbinom{i-1}{p-1}\sum\limits_{lft=0}^{k-[j=1]}dp_{p-1,j-1,lft}\times dp_{i-p,j-1,k-[j=1]-lft}$

注意边界 $dp_{1,1,1}=1$ 且 $p=1$ 和 $p=i$ 的情况要单独转移，并且 $j>i$ 或者 $j<1$ 的 $dp_{i,j,0}=i!$。

转移的时候要注意卡常，有 $0$ 就不做乘法。