employ

luanyanjia · 2025-11-01 19:50:11 · 题解

设 f_{i,j,k} 是前 i 位，当前有 j 个人寄了，有 k 个 x 满足 1 \le x \le i \land c_x \le j，只考虑所有 c \le j​ 的人的排列的方案数。

设 t_i 是 c_x = i 的 x 的个数，s 是 t 的前缀和。

直接转移，c 是 j 变大的时候枚举的要填在前面的 c_x = j+1 的个数。

• 当 s_i = 1：

  • 填 >j 的数：f_{i+1,j,k} \leftarrow f_{i,j,k}。
  • 填 \le j 的数：f_{i+1,j+1,k+c+1} \leftarrow f_{i,j,k}\binom{i-k}{c}\binom{t_{j+1}}{c}c!({s_j}-k)

• 当 s_i = 0：

  • 填 \le j 的数：f_{i+1,j+1,k+c+1} \leftarrow f_{i,j,k}\binom{i-k}{c}\binom{t_{j+1}}{c}c!({s_j}-k)
  • 填 j+1：f_{i+1,j+1,k+c} \leftarrow f_{i,j,k}\binom{i-k}{c-1}\binom{t_{j+1}}{c}c!
  • 填 > j 的数：f_{i+1,j+1,k+c} \leftarrow f_{i,j,k}\binom{i-k}{c}\binom{t_{j+1}}{c}c!​

答案就是 \sum\limits_{i=0}^{n-m}{f_{n,i,s_i}(n-s_i)!}。

一层里面所有 c 之和是 O(n) 的，因此总时间复杂度是 O(n^3)。