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

虞皓翔 · 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 !，个人习惯)。

转移分三种情况：

第 i 个字符使用若干 (正整数) 个，然后将这一段切掉 (也是最正常的情况)。
设这种字符使用了 l 个，则转移为
f_{i + 1, j + l, 0} \uparrow f_{i, j, k} \cdot \frac 1 {(k + l)!}
第 i 个字符准备和下一个字符进行容斥型合并，即它们在 \left( 3 \right) 式中使用加号产生贡献。
由于是容斥型合并，每多一个 "+" 号就要产生 -1 的系数。故转移方程为
f_{i, j + l, k + l} \uparrow - f_{i, j, k}
第 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;
}