题解

思路

所有编号都不同，所以排列方案总数是 $n!$。用总方案数减去能形成回文串的方案数即可。

设字母 $x$ 出现 $cnt_x$ 次，$h_x=\lfloor cnt_x/2\rfloor$。回文串存在的必要充分条件是出现奇数次的字母不超过一个。

若回文串存在，只需安排长度为 $\lfloor n/2\rfloor$ 的左半串。不同左半串的数量为

$$\frac{\lfloor n/2\rfloor!}{\prod_x h_x!}.$$

固定一个字母串后，每种字母的 $cnt_x$ 个编号可以任意放入该字母占据的位置，因此还要乘上 $\prod_x cnt_x!$。所以

$$pal=\frac{\lfloor n/2\rfloor!}{\prod_x h_x!}\prod_x cnt_x!.$$

答案是 $(n!-pal)\bmod (10^9+7)$。

做法

• $n\le 8$：枚举所有编号排列并直接判断得到的字符串是否为回文串。
• $n\le 20$：用混合进制状态记录每种字母已经放入左半串的数量，逐位置做状态 DP；状态数至多为 $2^{10}$，最后乘上各字母编号的阶乘。
• 只有 a、b：用二维 DP 依次选择下一对对称位置放哪种字母，并乘上可选的有序编号对数量。
• 无限制：使用上面的阶乘与逆阶乘公式。

正确性证明

任意排列要么形成回文串，要么形成非回文串，两类互不相交且覆盖全部 $n!$ 个排列。

回文串的左右两半必须逐位相同，因此每种字母有 $h_x$ 个位置出现在左半串；若有两个或更多奇数次字母，就不可能只用一个中心位置容纳所有剩余字符。反之，奇数次字母不超过一个时，任意左半串排列都唯一确定右半串和中心字母。

左半串是含 $h_x$ 个字母 $x$ 的多重集合排列，所以共有 $\lfloor n/2\rfloor!/\prod h_x!$ 种。对于固定字母串，每个字母的带编号字符可在该字母的全部位置间任意排列，共有 $cnt_x!$ 种，且不同字母之间独立。乘法原理得到公式中的 $pal$。最终从 $n!$ 中减去它，所得恰为非回文排列方案数。

复杂度

满分算法预处理阶乘与逆阶乘，时间复杂度为 $O(n+26)$，空间复杂度为 $O(n)$。