CF1580B Mathematics Curriculum 做题记录

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

  • 长度为 nn
  • 恰有 kk 个数满足:所有包含这个数的区间中,不同的最大值的个数恰有 mm 个。

答案对 pp 取模。

1n100,1mn,1kn,1p1091 \le n \le 100, 1 \le m \le n, 1 \le k \le n, 1 \le p \le 10^9

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

dpi,j,kdp_{i,j,k} 为满足恰好有 kkj好数j-\text{好数}ii 的排列个数,那么可以通过枚举最大值的位置 pppp 左侧序列的 (j1)好数(j-1)-\text{好数} 个数来转移:

dpi,j,k=p=2i1(i1p1)lft=0k[j=1]dpp1,j1,lft×dpip,j1,k[j=1]lftdp_{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}

注意边界 dp1,1,1=1dp_{1,1,1}=1p=1p=1p=ip=i 的情况要单独转移,并且 j>ij>i 或者 j<1j<1dpi,j,0=i!dp_{i,j,0}=i!

转移的时候要注意卡常,有 00 就不做乘法。