自动搬运

查看原文

来自洛谷，原作者为

	虞皓翔 Eternal dominant seventh.

搬运于2025-08-24 22:10:34，当前版本为作者最后更新于2019-07-03 22:08:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

鉴于这题已经过了三年且网上没有靠谱题解，以及笔者写本文时所有 luogu AC 代码均是本人的代码，现在这里将简单介绍一下思路，起些抛砖引玉的作用。

如果要详细的题解 (比如细节等)，请左转 此处 以获得更好(cha)的阅读体验~

我们分 7 步来完成这道题。

---

---- Step 1 ----

首先考虑对于一个长度为 $n$ 的串 $s$ 和后缀数组 $p$，什么时候是合法的。

我们在 $s$ 的末端加一个字典序最小的字符，并令 $p_0 = n + 1$。

于是，$p$ 是 $s$ 的后缀数组的充要条件是，如果 $p_i + 1$ 在 $p_{i+1} + 1$ 的后面，则 $s_{p_i} < s_{p_{i+1}}$；如果 $p_i + 1$ 也在 $p_{i+1} + 1$ 的前面，则要有 $s_{p_i} \leq s_{p_{i+1}}$。

---

---- Step 2 ----

接下来我们就能推出，对于一个确定的后缀数组，怎样的串是满足条件的。

由 Step 1 的结论，所有 $s_i$ 会按照一定的顺序形成一条形如 $s_{p_1} \otimes s_{p_2} \otimes \cdots \otimes s_{p_n}$ 的不等式链，其中 $\otimes$ 为 $\leq$ 或 $<$。

举个例子：后缀数组 5 3 1 4 2 形成的不等式链即为 $s_5 \leq s_3 \leq s_1 < s_4 \leq s_2$。

---

---- Step 3 ----

我们先从最简单的情形着手，$m = 2$。(注：此处默认 $c_i = + \infty$)

为了防止计算重复，我们对于一个后缀数组 $sa$，定义它的秩为最小的 $m$，满足存在字符集大小为 $m$ 的字符串，使其后缀数组恰好为 $sa$。

因此一个后缀数组的秩等于它在 Step 2 的不等式链中 "$<$" 号的个数。

我们需要统计字符集大小为 $2$ 的 SA 的个数，不妨先来统计秩为 $2$ 的 SA 的个数。

设字符串中有 $A$ 个 a，$B$ 个 b。因此将它们进行带重复元素的排列，可知共有 $\dbinom {A + B} A$ 种情况。

我们要从中去掉秩为 $1$ 的情况。易知，秩为 $1$ 的后缀数组恰有一个 (其实就是 $\left[ n, n - 1, n - 2, \cdots, 3, 2, 1 \right]$)，因此由 $A$ 个 a，$B$ 个 b 构成的字符串中，秩为 $2$ 的后缀数组的个数就是 $\dbinom {A + B} A - 1$。

---

---- Step 4 ----

经历完 $m = 2$ 的情况，再来考虑 $m = 3$ 的情况。

还是先统计秩为 $3$ 的后缀数组个数。设其中有 $A$ 个 a，$B$ 个 b 以及 $C$ 个 c。

由可重排列，由这些元素构成的秩不超过 $3$ 的不同 SA 个数共有 $\dbinom {A + B + C} {A, B, C}$ 个。

当然，这些是秩不超过 $3$ 的。我们还是要将这些秩过小的排列 "容斥" 掉。

回到 Part 2 中的不等式链。首先，由于这些 SA 的秩不超过 $3$，因此不等式链中严格小于号 "$<$" 的个数不会超过 $2$。

考察所有 $\dbinom {A + B + C} {A, B, C}$ 个排列中的一个排列 $p$，设它的秩为 $2$。由于它是我们在统计秩为 $3$ 的排列中计入的，因此它的不等式链的形式本应该是：

$$x_1 \leq x_2 \leq \cdots \leq x_A {\color{red} {}<{}} x_{A + 1} \leq x_{A + 2} \leq \cdots \leq x_{A + B} {\color{blue} {}<{}} x_{A + B + 1} \leq x_{A + B + 2} \leq \cdots \leq x_{A + B + C} \qquad \left( 1 \right) $$

而事实上，它的秩可以是 $2$。也就是说，实际上，不等式链中只有 $1$ 个严格小于号。

然而 $\left( 1 \right)$ 式中的等号是必定取等的，因此这个唯一的小于号要么在红色位置，要么在蓝色位置。

不妨设 "$<$" 号在蓝色位置，则红色位置上的 $\leq$ 就可以取等了。

也就是说，此时，这个后缀数组即为满足 $s_{p_1} = s_{p_2} = \cdots = s_{p_{A + B}} = \texttt a, \ s_{p_{A + B + 1}} = s_{p_{A + B + 2}} = \cdots = s_{p_{A + B + C}} = \texttt b$ 的串 $s$ 的后缀数组。

因此，每个 "由 $A + B$ 个 $\texttt a$，$C$ 个 $\texttt b$ 构成的串" 的后缀数组，都会对我们的统计造成一个 "误判"。因此，我们要答案减去 $\dbinom {A + B + C} {A + B, C}$。

同理，"$<$" 也可以在红色位置，此时则需要减去 $\dbinom {A + B + C} {A, B + C}$。

可以看出，这是一个容斥的过程。因此，我们还需要把秩为 $1$ 的后缀数组补回来。此时，我们不再在式子中写 $1$ (恰有 $1$ 个秩为 $1$ 的后缀数组)，而是：

$$tot = \binom {A + B + C} {A, B, C} - \binom {A + B + C} {A + B, C} - \binom {A + B + C} {A, B + C} + \binom {A + B + C} {A + B + C} \qquad \left( 2 \right) $$

---

---- Step 5 ----

然鹅题目不是让你统计秩为 $m$ 的 SA 的个数！

那我们刚才搞那么多到底是为了啥？无非就是构造一个一一对应，将一个排列对应到一个串上去，使得计数不重不漏啊！

因此，对一个秩为 $r$ 的排列，我们就应当恰好在统计秩为 $r$ 为排列中统计进去！

具体地，我们按字典序从小到大枚举每个字符出现了几次，然后算出有多少个 "满秩" 的后缀数组。(这里 "满秩" 的意思是，这个串的字符集大小恰好等于该后缀数组的秩，不出现字符集冗余的情况)

但是这里还有一个比较关键的问题。有的秩比较小的后缀数组，它的来源是一个较大的字符集，而它所对应的 "满秩" 的字符串是不符合题目要求的。

举个例子，你有 $2$ 个 $\texttt a$ 和 $2$ 个 $\texttt b$，则 $\texttt {baa}$ 的后缀数组为 $\left[ 3, 2, 1 \right]$，秩为 $1$，而所对应的 "满秩" 字符串 $\texttt {aaa}$ 或 $\texttt {bbb}$ 均不满足题目要求 (任意字符你只有 $2$ 个)。

因此我们需要一点计数技巧，在这里可以采用 "合并" 这种操作。

考虑 $c_1, c_2, \cdots, c_m$ 从小到大填充的过程。如果一个字符，比如 $\texttt a$，出现了超过 $c_1$ 次。首先，它肯定达到了 $c_1$ 次。因此，一旦它达到了 $c_1$ 次，我们就可以将 $\texttt b$ 的 $c_2$ 次使用机会全都 "借" 给 $\texttt a$ (反正也是有借无还嘛)，从而完成 "合并" 的过程。

但是，能借后面的串用的前提是，$a$ 先把自己的 $c_1$ 次机会用完。

当然，不仅是 $\texttt a$，我们对待每个字符都是一视同仁的，只有把自己的机会用完了，才能 "借" 用下一个字符的机会。

---

---- Step 6 ----

最后就只剩下实现了，至于如何高效地完成这个容斥的过程，那就考虑用 DP 来求解容斥系数啦。

将 $\left( 2 \right)$ 式推广，设第 $i$ 小的字符有 $A_i$ 个。则整个容斥的过程可以看成枚举断点集合 ("$<$" 集合) $\left\{ z_1, z_2, \cdots, z_k \right\}$，则这一部分的贡献为

$$(-1)^{m - k} \binom {A_1 + A_2 + \cdots + A_m} {A_1 + A_2 + \cdots + A_{z_1}, A_{z_1 + 1} + \cdots + A_{z_2}, \cdots, A_{z_k + 1} + \cdots + A_{z_m}} \qquad \left( 3 \right) $$

首先，分子上的 $\left( A_1 + A_2 + \cdots + A_m \right)! = n!$ 是常量，可以预先提出来。然后对于每个长度为 $len$，对最终结果有一个阶乘倒数 $\dfrac 1 {len!}$ 的贡献。

(下面就是 DP 状态定义啦)

用 $f_{i, j, k}$ 表示当前从小到大填充到第 $i$ 个字符，已经填充了 $j$ 个位置 (i.e. 当前 $A$ 的前缀和为 $j$)，最后一段的大小为 $k$ (i.e. $A.\mathrm{back}() = k$)，所得到的容斥系数。

要注意的一点是，注意，这个 DP 是基于贪心的，因此每个字符一定是能用则用，因此不使用的字符一定是一段后缀，即一旦一个字符未使用，就预示着这个串的 "终结"。

先扔掉 $c_i = 0$ 的字符，边界是 $f_{0, 0, 0} = 1$ (当然也可以是 $n !$，个人习惯)。

转移分三种情况：

1. 第 $i$ 个字符使用若干 (正整数) 个，然后将这一段切掉 (也是最正常的情况)。
   设这种字符使用了 $l$ 个，则转移为

$$f_{i + 1, j + l, 0} \uparrow f_{i, j, k} \cdot \frac 1 {(k + l)!} $$

2. 第 $i$ 个字符准备和下一个字符进行容斥型合并，即它们在 $\left( 3 \right)$ 式中使用加号产生贡献。
   由于是容斥型合并，每多一个 "$+$" 号就要产生 $-1$ 的系数。故转移方程为

$$f_{i, j + l, k + l} \uparrow - f_{i, j, k}$$

3. 第 $i$ 个字符准备和下一个字符进行正常合并 (即统计秩比较小的后缀数组)。由 Step 5，此时要求第 $i$ 个字符必须用满。
   因此转移系数还是 $+ 1$，方程为

$$f_{i, j + c_i, k + c_i} \uparrow f_{i, j, k}$$

以上 $a \uparrow b$ 表示 a += b (in C++)。

至于统计答案，相当于统计这个串在哪个字符处 "终结"，即答案等于 $\displaystyle \sum_{i=1}^m f_{i, n, 0}$

时间复杂度 $O \left( n^3 m \right)$。

---

---- Step 7 ----

最后一步相信大家都明白，对这个 DP 进行优化。

不难发现，当固定 $j' = j + l, k' = k + l$ 时，这个 DP 方程其实就得是一个对角线方向上的区间和！

因此，可以使用前缀和优化来解决，不过要注意一下求和的上下限。

于是单点转移就被优化到了 $O \left( 1 \right)$，总时间复杂度 $O \left( n^2 m \right)$，就可以通过了。

代码：

#include <bits/stdc++.h>
#define jl j
#define kl k

typedef long long ll;
const int N = 540, mod = 1000000007;

int n, m;
int c[N], fact[N], finv[N];
int f[N][N], F[N][N];

inline void add(int &x, const int y) {x = (x + y >= mod ? x + y - mod : x + y);}
ll PowerMod(ll a, int n, ll c = 1) {for (; n; n >>= 1, a = a * a % mod) if (n & 1) c = c * a % mod; return c;}

int main() {
	int i, j, k, l; ll ans = 0;
	scanf("%d%d", &n, &m);
	for (i = 1; i <= m; ++i) if (scanf("%d", c + i), !c[i]) --i, --m;
	for (*fact = i = 1; i <= n; ++i) fact[i] = (ll)fact[i - 1] * i % mod;
	finv[n] = PowerMod(fact[n], mod - 2);
	for (i = n; i; --i) finv[i - 1] = (ll)finv[i] * i % mod;
	for (**f = i = 1; i <= m; ++i) {
		for (j = 0; j <= n; ++j)
			for (k = 0; k <= j; ++k)
				add(F[j + 1][k + 1] = F[j][k], f[j][k] + (f[j][k] >> 31 & mod)), f[j][k] = 0;
		for (jl = 1; jl <= n; ++jl)
			for (kl = 1; kl <= jl; ++kl) {
				l = std::min(c[i], kl);
				f[jl][0] = (f[jl][0] + (ll)finv[kl] * (F[jl][kl] - F[jl - l][kl - l])) % mod;
				if (jl != n) {
					l = std::min(c[i] - 1, kl),
					f[jl][kl] = ((ll)f[jl][kl] - F[jl][kl] + F[jl - l][kl - l]) % mod;
				}
			}
		ans += f[n][0];
	}
	ans = ans % mod * fact[n] % mod;
	printf("%lld\n", ans + (ans >> 63 & mod));
	return 0;
}