题解

思路

令 $a_i,b_i$ 分别是两个名字中字母 $i$ 的出现次数。设 $x_i$ 表示昵称中有多少个位置把 $A'$ 的字母 $i$ 配成了 $B'$ 的字母 $i+1$。那么 $B'$ 实际使用的字母 $i$ 数量为

必须满足 $c_i\le b_i$。固定所有 $x_i$ 后，不同昵称对的排列数为

做法

按字母从 A 到 Y 做 DP。若上一字母有 $p=x_{i-1}$ 个向后匹配，当前选择 $x=x_i$，容量约束等价于

因此转移是上一层 DP 的一个前缀和，再乘 $\binom{a_i}{x}$。维护前缀和后，每层时间为 $O(a_i)$。最后在 Z 处要求 $a_Z+x_Y\le b_Z$，再乘上 $A$ 的多重集排列数。

$N\le9$ 时可以枚举所有 $x_i$；$N\le2000$ 时可不维护前缀和，直接枚举相邻两层状态。

正确性说明

每个合法昵称对按位置唯一决定每个 $x_i$；反之，满足容量约束的 $x_i$ 可以从 $B$ 中取出所需字符。固定 $x_i$ 时，先排列 $A'$ 的多重集，再从每种字母的所有位置中选择 $x_i$ 个改为下一字母，恰得到公式中的计数，且不会重复。DP 恰好枚举所有满足相邻容量约束的 $x_i$，所以求和后得到全部合法昵称对。

复杂度

满分算法时间复杂度为 $O(N+M+26)$，空间复杂度为 $O(N)$。