问题求解III-HW13 题解

我们希望大家掌握 字符串的滚动哈希技术。简单来说，字符串滚动哈希可以在线性预处理后，$O(1)$ 地回答任意子串的哈希值。在拥有这项技术的前提下，我们只需要对输入串正着和倒着分别进行滚动哈希预处理，然后枚举字符串的每个位置作为“中间点”，二分最长的可以向左右延伸的回文长度，用哈希值验证即可。总时间复杂度 $O(n\log n)$。

一个重要的观察是：如果我们将初始的棋盘“黑白染色”——即将坐标和为偶数的格子归为一类，奇数的格子归为另一类，那么两个格子曼哈顿距离为奇数的充要条件就是它们属于不同的类。因此，我们只要保证这两类的格子使用的颜色集合交集为空即可。

不妨设两类格子的数量分别为 $N_1$ 和 $N_2$ (一个是 $\lfloor\frac{nm}{2}\rfloor$，另一个是 $\lceil\frac{nm}{2}\rceil$), 然后我们枚举给第一类格子使用 $k_1$ 种颜色，第二类格子使用 $k_2$ 种颜色 (颜色集合需要满足互不相交)，有：

$$ ans=\sum_{k_1=0}^k\sum_{k_2=0}^{k-k_1}\binom{k}{k_1}\binom{k-k_1}{k_2}S(N_1, k_1)S(N_2, k_2)k_1!k_2! $$

其中 $S(i, j)$ 表示将 $i$ 个可区分的小球放入 $j$ 个不可区分的桶里，不准存在空桶的方案数 (第一行式子里最后有 $k_1!k_2$ 是因为颜色实际上是可区分的)，这是经典的第二类斯特林数，有简单的动态规划状态转移方程：

$$ S(i, j) = S(i - 1, j - 1) + S(i - 1, j) * j $$

该公式的含义是：考虑最后一个小球，它可以自成一桶，从而剩下的 $i-1$ 个球放入剩下的 $j-1$ 个桶中；或者它不自成一桶，那么其他 $i-1$ 个球放入 $j$ 个桶后，最后一个球选一个桶放入 (注意虽然桶本身不可区分，但前 $i-1$ 个不同的球使得这些桶变得可区分了)。

综上，我们只要用预处理组合数和第二类斯特林数，最后枚举 $k_1, k_2$ 即可。总时间复杂度为 $O(nm + k^2)$。