字符串计数：题解

思路

任意更长的奇回文中心都包含一个长度为 $3$ 的回文，所以美丽条件等价于对所有 $i$ 都有 $s_i\ne s_{i-2}$。忽略数量上限时，前两位各有 $26$ 种选择，之后每位有 $25$ 种，方案数为 $26^2\cdot25^{n-2}$。

又因为每个 $c_i>n/3$，同一个长度为 $n$ 的字符串中最多有两种字母超过各自上限。因此只需容斥到二阶。

做法

子任务 1：直接枚举

当 $n\le4$ 时逐位枚举 $26$ 种字母，检查数量上限和与前两位不同的条件。

子任务 2：逐对重新计数

固定两种字母 $A,B$，把字符分成 $A$、$B$、其他三类。状态记录当前长度、$A/B$ 使用次数和末两位类别；转移到“其他”时，若倒数第二位也是其他则有 $23$ 种，否则有 $24$ 种。对每对字母重新运行该 DP 后执行容斥，适用于 $n\le20$。

满分算法

上述三类 DP 的结果与具体选择哪两个字母无关，只与 $n$ 有关，因此只需预处理一次。设 $F_{x,y}$ 为指定字母 $A,B$ 恰好出现 $x,y$ 次的合法串数，$G_x=\sum_yF_{x,y}$ 为指定一种字母恰好出现 $x$ 次的方案数。

答案为

$$26^2\cdot25^{n-2}-\sum_i\sum_{x>c_i}G_x+\sum_{i<j}\sum_{x>c_i,y>c_j}F_{x,y}.$$

二维后缀和可以常数时间查询最后一项。

复杂度

枚举算法为 $O(26^n)$；逐对重算为 $O(26^2n^3)$；满分算法为 $O(n^3+26^2)$ 时间、$O(n^2)$ 空间。