P5417 [CTSC2016] 萨菲克斯·阿瑞 题解

First Post:

Last Update:

很神的题啊。感觉刻画后缀数组的充要条件就很难想。

考虑找到一个充要条件来判断排列 是不是 的后缀数组。这等价于对每个 保证 。那显然有 。而且，如果 在后缀数组中的位置在 前面，那么 就是满的限制，否则 就是满的限制。这个条件的必要性显然。(上文中 可能等于 ，为了避免这种讨论，我们在串的末尾加入一个最小的字符)

那么，一个后缀数组可以产生一条不等式链：，其中的每个 都是 或 。

从后往前考虑每个位置的相对排名，可以构造性地说明这个条件是充分的。

定义 表示串 是否满足对于任意 ， 和 满足不等式链 的第 项的限制。

设排列 产生的不等式链为 。设 表示不等式链中一共有多少个 。

把充要条件换一种说法，就是所有使得 为真的串 的后缀数组都为 。

引理 1: 如果按题意限制，存在某个串的后缀数组 使得 ，那么所有 的排列 都可以是某个串的后缀数组。

证明：取出一个串 使得 为真，将 作为一个序列，乘上置换 ，乘上置换 ，设产生的新串为 ，那么 使得 为真（因为我们只是将 中的字符按照 的顺序进行了重排，不等式链没有改变，所以可以满足条件）。所以新串 的后缀数组为 ，也就证明了引理。

也就是说，原问题的答案变为 能被构造出来。

问题就分成了两部分：如何判断不等式链 能被构造出来，以及计算有多少个排列 使得 。

Part.1

这一部分较为简单：

将不等式链 按照 号分为 段，设每段段长为 。

从小到大考虑每个字符 。从左往右填写每一段。

如果 大于等于当前段未填的字符数，将这一段剩余部分全填 ，然后把 多出来的部分直接扔掉。

否则，将 个 填到这一段里面。

容易证明这个贪心算法的正确性。

值得注意的是，每个字符只会在一段内出现，且出现在一段内的字符其实可以被看做一种。

Part.2

这里我们可以忘记所有题目限制。

仍然考虑一条不等式链 ，并将其分拆为 的形式。

定义 表示如果 的某一项是 ， 的某一项也是 。

设 表示 ，这是 最多可能对应的排列个数。因为 是总长为 ，第 种字符有 个的字符串个数，而所有 的排列 ，都有这么一个字符串使得 为真，所以 的个数不会超过满足条件的 的个数，即 。

注意这里是不会超过 ，那么我们就要考虑多算了些什么。

比如说一条不等式链 ，我们算 时会将排列 算入，其对应的不等式链为 。

观察所有 计数到的 ，会发现，如果 的第 项是 ，那么 的第 项也是 。（即 ）。

因为如果 ，那么肯定存在一个 ，使得 ，也就是说前 个字符恰好是所有的前 种字符。那么 的第 项也得是 ，因为我们就是用 的 号来构造 的。

只是会把等号算多而已。观察算多的次数，如果 中有 个小于号， 中有 个小于号，那么 会被算 次（相当于任意地把原来一些不相等的字符合并起来，放在同一个 连续段中）。这符合容斥原理的形式，所以容斥时给 的系数是正确的。

于是可以用容斥计算 的 的个数：。

那么每个我们钦定的 中的 变成了 中的 的位置，都会给答案贡献 的容斥系数。

把上文的两部分合起来，可以得到一个 DP。

设 表示当前在不等式链上填了前 种字符，填了前 个位置，最后一个 连续段的段长是 。转移有三类 （下文中 ）：

  1. （把字母 填完）
  2. (用字母 给当前这一段收尾)
  3. （钦定一个 ，在原不等式链中是 ，所以要像二类转移那样把字母 截断；因为我们算的是新不等式链的多重组合，所以累加段长且不乘阶乘）

最后的答案为 。

用前缀和优化转移即可，时间复杂度 。

代码中将第一类转移和第三类转移进行了合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
const int N = 5e2 + 5,P = 1e9 + 7;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
int n,m;
int c[N];
int dp[N][N],sum[N][N];
int fac[N],ifac[N];
int main() {
	cin >> n >> m;
	for(int i = 1;i <= m;i++) cin >> c[i];
	fac[0] = 1;
	for(int i = 1;i <= n;i++) fac[i] = 1ll * fac[i - 1] * i % P;
	ifac[1] = 1;
	for(int i = 2;i <= n;i++) ifac[i] = 1ll * ifac[P % i] * (P - P / i) % P;
	ifac[0] = 1;
	for(int i = 1;i <= n;i++) ifac[i] = 1ll * ifac[i - 1] * ifac[i] % P;
	dp[0][0] = 1;
	int ans = 0;
	for(int t = 1;t <= m;t++) {
		if(!c[t]) continue;
		for(int i = 0;i <= n;i++)
			for(int j = 0;j <= n;j++)
				sum[i][j] = ((i > 0 && j > 0 ? sum[i - 1][j - 1] : 0) + dp[i][j]) % P,dp[i][j] = 0;
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= i;j++) { // 这里 j 要小于等于 i，否则求前缀和时会 RE
				// 身为最后一个字符，将当前这一段结束，此时段长为 j
				Plus(dp[i][0],1ll * ifac[j] * (sum[i - 1][j - 1] - (j > c[t] ? sum[i - c[t] - 1][j - c[t] - 1] : 0) + P) % P);
				// 将不新开，全放完 和 新开且容斥
				Plus(dp[i][j],P - (sum[i - 1][j - 1] - (j >= c[t] ? sum[i - c[t]][j - c[t]] : 0) + P) % P);
			}
		Plus(ans,dp[n][0]);
	}
	ans = 1ll * ans * fac[n] % P;
	cout << ans << endl;
	return 0;
}
≡