自动搬运

查看原文

来自洛谷，原作者为

	P2441M 却仍愿/坚信着/世间最美好的一切/正御风漂泊

搬运于2025-08-24 21:15:48，当前版本为作者最后更新于2024-01-07 01:01:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

原题链接：B3902 [NICA #3] 数计组数

这题明显是计数类DP题。容易想到令 $F_i$ 表示长度为 $i$ 的数计组数，我们需要考虑的是，$\forall j<i$，$F_j$ 与 $F_i$ 之间如何进行转移。

为了避免子问题互斥，可以想到在 $F_j$ 的基础上，新划分出一个长度为 $i-j$ 的区间 $S'$，使得新的长度为 $i$ 的数组是“数计的”。接下来，我们单独考虑区间 $S'$ 应如何填数。根据定义，$\mathop{\min}\limits_{a\in S'}\{{a}\}\geqslant i-j$，且 $i-j$ 应出现至少也仅有 $1$ 次。这同时也反映了，如果 $i-j\notin S$，则 $F[j]$ 与 $F[i]$ 之间不应该发生转移。

我们可以用排列组合计算区间 $S'$ 的排列数 $C_{i-j}$。预定义 $c_i=M-\mathop{min}\limits_{j\in[1,n],S[j]\geqslant i}\{j\}$，即 $S$ 中大于等于 $i$ 的元素个数（之所以写成这种形式，是为了方便使用 std::lower_bound 二分计算）。此时，$S'$ 的总排列数为 $c_{i-j}^{i-j}$。再考虑使得 $S'$ 不是“数计的”的排列数，相当于最小值不是 $i-j$，即不选 $i-j$，所以有 $(c_{i-j}-1)^{i-j}$ 种排列。综上，$S'$ 有

$$C_{i-j}=c_{i-j}^{i-j}-(c_{i-j}-1)^{i-j}$$

种排列数。

根据乘法原理，我们可以轻松地得到最终的状态转移方程：

$$F_0=1, F_i=\sum_{j\in[0,i),i-j\in S}{F_j\times C_{i-j}}. $$

上代码：

#include <iostream>
#include <cstring>

using namespace std;

constexpr int MAX_N = 2000, MAX_M = 100000, MAX_ELEM = 1000000, MOD = 1e9 + 7;
int n, m;
bool exists[MAX_ELEM + 1]; // 判定是否在集合中
int s[MAX_M + 1]; // 原始集合
int c[MAX_N + 1]; // c[i]表示S中>=i的数的个数
long long f[MAX_N + 1]; // f[i]表示长度为i的“数计的”数组个数

// 快速幂
long long quick_power(long long a, long long b) {
	long long res = 1;
	for (; b; b >>= 1) {
		if (b & 1) res = res % MOD * a % MOD;
		a = a % MOD * a % MOD;
	}
	return res;
}

int main() {
	memset(exists, 0, sizeof exists);
	memset(f, 0, sizeof f);

	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> s[i];
		exists[s[i]] = true;
	}

	// 二分计算c数组
	for (int i = 1; i <= n; ++i)
		c[i] = s + m + 1 - lower_bound(s + 1, s + m + 1, i);

	// 进行DP状态转移
	f[0] = 1;
	for (int i = 1; i <= n; ++i)
		for (int j = 0; j < i; ++j)
			if (exists[i - j]) {
				f[i] += f[j]
					* (quick_power(c[i - j], i - j) - quick_power(c[i - j] - 1, i - j) + MOD /* + MOD 是为了保证非负 */)
					% MOD;
				f[i] %= MOD;
			}

	cout << f[n] << endl;

	return 0;
}