虽然这题暴力即可，但这题一看就有组合DP做法，而且系数固定，显然可以用多项式科技优化，遂让AI写了一下此做法。这是一个基于容斥原理结合生成函数的组合计数问题，使用NTT进行优化。算法思路容斥原理转化：我们要计算没有相邻字符相等的排列数。直接计算比较困难，我们使用容斥原理。对于每种字符 ，假设它的出现次数为 。我们可以枚举该字符中有 对相邻字符是相等的（即“坏”连接）。如果选定了 对相邻相等，相当于将这 个字符分成了个“块”。生成函数构建：对于每种字符 ，设我们要分成 个块（即选了 个坏连接）。将 个物品分成 个有序非空块的方案数是插板法 。在最终的排列中，我们有总共 个块。这些块的...
