求满足以下条件的排列个数:
- 长度为 n。
- 恰有 k 个数满足:所有包含这个数的区间中,不同的最大值的个数恰有 m 个。
答案对 p 取模。
1≤n≤100,1≤m≤n,1≤k≤n,1≤p≤109。
首先定义 i−好数 为所有包含这个数的区间中,不同的最大值恰好有 i 个的数,问题就变成了求 m−好数 恰好有 k 个的 n 的排列的个数。
设 dpi,j,k 为满足恰好有 k 个 j−好数 的 i 的排列个数,那么可以通过枚举最大值的位置 p 和 p 左侧序列的 (j−1)−好数 个数来转移:
dpi,j,k=p=2∑i−1(p−1i−1)lft=0∑k−[j=1]dpp−1,j−1,lft×dpi−p,j−1,k−[j=1]−lft
注意边界 dp1,1,1=1 且 p=1 和 p=i 的情况要单独转移,并且 j>i 或者 j<1 的 dpi,j,0=i!。
转移的时候要注意卡常,有 0 就不做乘法。