题解

问题分析

我们需要构造一个长度为 $n$ 的字符串，仅由 $5$ 种元音字母 $\{a, e, i, o, u\}$ 组成，使得该字符串的回文子序列数量最少（包括空字符串）。

核心思路

1. 回文子序列的计数方式

如果我们将相同的字母放在连续的段中，那么任何回文子序列只能由同一种字母构成（因为不同字母无法形成回文，除非对称位置字符相同，但若同字母连续，则跨字母的回文无法形成）。

对于一种出现次数为 $a$ 的字母，其非空回文子序列的个数为： [ 2^a - 1 ] （因为该字母的任意子序列都是回文，共有 $2^a$ 个子序列，减去 $1$ 个空序列）

因此，若五种字母的出现次数分别为 $a_0, a_1, a_2, a_3, a_4$，且相同字母连续放置，则总回文子序列数为： [ \sum_{i=0}^{4} (2^{a_i} - 1) + 1 = \sum_{i=0}^{4} 2^{a_i} - 4 ] 其中最后的 $+1$ 是空字符串。

结论：对于固定的 $(a_0, a_1, a_2, a_3, a_4)$，将相同字母连续放置是最优的排列方式。

2. 如何分配各字母的出现次数

我们需要最小化 $\sum_{i=0}^{4} 2^{a_i}$，其中 $\sum_{i=0}^{4} a_i = n$，且 $a_i \ge 0$ 为整数。

函数 $f(x) = 2^x$ 是凸函数（二阶导数为正）。根据凸函数的性质，对于固定和，当各变量尽可能接近时，函数值的和最小。

数学证明：假设存在两个数 $x$ 和 $y$ 满足 $x+2 \le y$，则： [ 2^{x+1} + 2^{y-1} < 2^x + 2^y ] 因为： [ 2^{x+1} + 2^{y-1} = 2 \cdot 2^x + \frac{1}{2} \cdot 2^y ] 而 $2^{x} + 2^{y} - (2 \cdot 2^x + \frac{1}{2} \cdot 2^y) = 2^{y-1} - 2^x > 0$（当 $y-1 \ge x+1$ 时成立）。

因此，通过不断将大的减少 $1$、小的增加 $1$，可以减小 $\sum 2^{a_i}$，直到所有 $a_i$ 相差不超过 $1$。

3. 最优分配方案

设 $n$ 除以 $5$ 的商为 $q = \lfloor n/5 \rfloor$，余数为 $r = n \bmod 5$。

则最优分配为：

• 有 $r$ 个字母出现 $q+1$ 次
• 其余 $5-r$ 个字母出现 $q$ 次

这样所有 $a_i$ 的差不超过 $1$，满足最优条件。

4. 构造字符串

按字母顺序（或任意顺序）输出：

• 前 $r$ 种元音各输出 $q+1$ 次
• 后 $5-r$ 种元音各输出 $q$ 次

相同字母连续输出，保证回文子序列数达到最小值。