「CTSC2016」萨菲克斯·阿瑞 题解

问题重述

给定长度 $n$ 和 $m$ 种字符，第 $i$ 种字符最多出现 $c_i$ 次（$\sum c_i \ge n$）。统计所有满足限制的长度为 $n$ 的字符串中，不同的后缀数组（SA）的数量。字符的大小顺序固定：第 $1$ 种字符最小，第 $2$ 种次小，依此类推。答案对 $10^9+7$ 取模。

核心观察

后缀数组的等价条件与字符串的比较关系密切相关。关键在于：给定字符的大小顺序后，什么样的字符分布会对应不同的后缀数组。

重要观察：

1. 后缀数组由字符串中相邻字符的大小关系决定。
2. 将字符串按照字符种类分段，每段由同种字符组成。
3. 不同后缀数组的数量等价于合法的分段方式的数量，且需要满足每段字符的出现次数限制。

算法思路

动态规划状态设计

设 $f[i][j]$ 表示考虑前 $i$ 种字符（按照字符大小顺序），已经使用了 $j$ 个字符的方案数（这里的具体定义可能结合了后缀数组的结构性质）。

实际上，代码中的 $f[j][k]$ 是在处理到第 $i$ 种字符时，表示使用 $j$ 个字符，且最后一个块的某种特定状态为 $k$ 的方案数。$sum$ 数组是前缀和用于优化转移。

转移分析

对于第 $i$ 种字符，考虑它可以出现的次数为 $1$ 到 $c_i$。在转移时：

• 考虑新加入一个由第 $i$ 种字符组成的块
• 需要考虑该块与前一个块的字符大小关系（因为字符顺序固定）
• 需要满足出现次数的限制

组合计数优化

代码中使用阶乘和逆阶乘进行组合计数：

• $fac[i]$ 存储 $i!$
• $ifac[i]$ 存储 $(i!)^{-1}$ 最终答案乘 $fac[n]$ 是将组合对象转化为具体字符串的方案数。

关键技巧

1. 前缀和优化：使用 $sum$ 数组维护 $f$ 的前缀和，将 $O(n^3)$ 的转移优化到 $O(n^2)$。
2. 取模优化：adj() 函数高效处理负数的取模运算。
3. 边界处理：当 $c_i=0$ 时直接跳过这种字符，不参与计算。
4. 组合数处理：通过阶乘逆元快速计算组合因子。

复杂度分析

• 时间复杂度：$O(m \times n^2)$，其中 $n \le 500, m \le 500$，可接受。
• 空间复杂度：$O(n^2)$。

算法总结

本题的核心是将后缀数组的计数问题转化为字符分段方案的组合计数问题。通过固定字符大小顺序，将后缀数组的比较关系转化为段与段之间的约束条件。

代码实现采用了动态规划 + 前缀和优化的组合计数方法：

1. 按字符种类顺序依次考虑
2. 维护已使用字符数和当前段的状态
3. 通过前缀和优化快速计算转移
4. 最终乘上 $n!$ 将排列方案映射到字符串

这种方法巧妙避免了直接枚举所有字符串（数量巨大），也避免了直接处理后缀数组的复杂比较关系，将问题转化为了一个可高效计算的组合计数问题。

难点突破

1. 理解后缀数组与字符分段之间的关系
2. 设计出合适的状态表示段的结构信息
3. 推导出高效的转移方程
4. 实现前缀和优化降低复杂度

该解法体现了组合计数中常见的思路：将复杂结构的计数转化为分阶段构造 + 组合系数的计算，对于处理字符串和后缀数组相关的计数问题具有借鉴意义。