自动搬运

查看原文

来自洛谷，原作者为

	KAMIYA_KINA 近若咫尺，却邈以山河

搬运于2025-08-24 21:24:30，当前版本为作者最后更新于2021-09-23 16:27:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Tag

动态规划，计数，组合数学。

Description

求一个长度为 $n$ 的序列 $\{a_n\}$，要求大于 $x$ 的 $a_i$ 的数量不能超过 $n-x+1$ 个，并且有一些 $a_i$ 是给定的，求有多少个序列满足这个条件。

给定的 $a_i$ 数量为 $m$，并且每一次测试模数为给定的 $M$。

$\texttt{data range:}1\leq n \leq 300,0 \leq m \leq n, 2\leq M \leq 10^9$.

Solution

我的描述已经解释了一定的题目，根据这个条件我们很容易就可以想出设 $s_i$ 为大于等于 $i$ 中有多少个编号，然后这个 $s_i$ 显然是不能大于 $n-i+1$ 的。

根据这个限制，我们可以得到一个很朴素的转移方程：

解释一下，这里的 $f_{i,j}$ 表示的是第 $i$ 个位置，$j$ 表示这个位置后面有 $j$ 个人。

那么我们对于上一个状态，无非就是将上一个状态中有 $j-k$ 个人的情况，然后从我要选的 $j$ 个人里面抽取 $k$ 个人出来站到第 $i$ 个位置上，那么方案就很显然了。

对于限制的情况，我们只用考虑第 $i$ 位之后已经确定的位置，那么就是说我们可以站在第 $i$ 个位置的人就会减少，所以 $j$ 的上界就是 $n-s_i-i+1$。

然后由于模数一直在变化，所以要用递推式解出组合数。

所以最后的答案就是 $f_{1,n-m}$。

做完了，时间复杂度 $O(n^3)$，可以通过本题。