题解

思路

对目标串按“原字符、目标字符”统计 $3\times3$ 的错配矩阵。

做法

行和与列和必须分别等于原串中三种字符的数量。方向相反的两类错配可以各用一次交换消去，剩余错配只能组成 A→B→C→A 或反向的三元环，每个三元环需要两次交换；两种方向若同时出现，又可以先配成两两交换，因此规范表示中至多保留一种方向。于是用 $a$ 表示三元环数，用 $b,c,d$ 表示三对反向错配数，所需操作数为 $2a+b+c+d$，当 $a>0$ 时三元环有两个方向。

枚举满足 $2a+b+c+d\le K$ 的四元组。对每一种字符的原位置，用多项式系数选择它们分别变成另外两种字符的位置，三个多项式系数相乘就是该错配矩阵对应的目标串数，再乘三元环方向数并累加。

复杂度

阶乘和逆阶乘预处理为 $O(N)$，枚举复杂度为 $O(K^4)$，空间复杂度为 $O(N)$。