没见过的一种 DP 类型，我们称它为贡献延后计算。
具体来说就是我们只关心选出来了些什么，至于这些东西的顺序我们在转移的时候不重复的钦定即可。
考虑本题设 \(f_{i, j, k}\) 表决策到前 \(i\) 场面试，有 \(j\) 个人失败，并且 \(1 \sim i\) 选择的人中有 \(k\) 个人的耐心程度小于等于 \(j\)，注意最后一维状态是为了方便我们转移的过程中钦定顺序的。
思考转移，分成 \(s_{i + 1} = 0/1\) 两种情况，考虑 \(=1\) 的情况下：
- 我目前选择耐心 \(> j\) 的，那么 \(f_{i, j, k} \to f_{i + 1, j, k}\)，目前不乘上选择方案的原因是我们不知道人数，且方案数我们延后计算。
- 我目前选择耐心 \(\le j\) 的，那么 \(f_{i, j, k} \times (pre_j - k) \times C_{cnt_{j + 1}}^p \times C_{i - k}^p \times p! \to f_{i + 1, j + 1, k + p + 1}\)，转移的意思是我目前 \(\le j\) 的还可以选出 \((pre_j - k)\) 个，然后 \(p\) 表示前面新增了一些耐心 \(= j + 1\) 的，并且需要给它们安排位置，选择放置的顺序，最后 \(k + p + 1\) 是目前 \(\le j + 1\) 的人的个数。
我们大概了解了，就是我们目前只计算 \(\le j\) 的人的顺序的方案数，对于 \(> j\) 的人我们不管它，反正以后会计算方案数的。
那么 \(s_{i + 1} = 0\) 的情况是同理的：
- 我目前选择耐心 \(> j + 1\) 的，那么 \(f_{i, j, k} \times C_{cnt_{j + 1}}^p \times C_{i - k}^p \times p! \to f_{i + 1, j + 1, k + p}\)，依旧是不计算选出的方案数。
- 我目前选择耐心 \(\le j + 1\) 的，那么 \(f_{i, j, k} \times C_{cnt_{j + 1}}^p \times C_{i - k}^p \times p! \times (pre_{j + 1} - k - p) \to f_{i + 1,j + 1, k + p + 1}\)，仍然一样，只不过 \(pre_{j + 1} - k - p\) 表示我目前选择的这个位置上可能能选出多少个耐心 \(j + 1\) 的人，这是可以计算的。
这个 DP 的精妙之处就在于，它在第一个转移完全没有算方案数，而是等到所有信息全部完成后（信息完成后显然限制只会变大）一起计算，感觉这种题只能枚举状态做出来。