P1386 座位安排 题解
KAMIYA_KINA
·
·
题解
Tag
动态规划，计数，组合数学。
Description
求一个长度为 n 的序列 \{a_n\}，要求大于 x 的 a_i 的数量不能超过 n-x+1 个，并且有一些 a_i 是给定的，求有多少个序列满足这个条件。
给定的 a_i 数量为 m，并且每一次测试模数为给定的 M。
## Solution
我的描述已经解释了一定的题目，根据这个条件我们很容易就可以想出设 $s_i$ 为大于等于 $i$ 中有多少个编号，然后这个 $s_i$ 显然是不能大于 $n-i+1$ 的。
根据这个限制，我们可以得到一个很朴素的转移方程：
$$
f_{i,j} =\sum_k\dbinom{j}{k}f_{i+1,j-k}
$$
解释一下，这里的 $f_{i,j}$ 表示的是第 $i$ 个位置，$j$ 表示这个位置后面有 $j$ 个人。
那么我们对于上一个状态，无非就是将上一个状态中有 $j-k$ 个人的情况，然后从我要选的 $j$ 个人里面抽取 $k$ 个人出来站到第 $i$ 个位置上，那么方案就很显然了。
对于限制的情况，我们只用考虑第 $i$ 位之后已经确定的位置，那么就是说我们可以站在第 $i$ 个位置的人就会减少，所以 $j$ 的上界就是 $n-s_i-i+1$。
然后由于模数一直在变化，所以要用递推式解出组合数。
$$
\dbinom nm=\dbinom {n-1}m+\dbinom {n-1}{m-1}
$$
所以最后的答案就是 $f_{1,n-m}$。
做完了，时间复杂度 $O(n^3)$，可以通过本题。