MO 真的很困难 | 5.15 做题记录

· · 个人记录

HDU2481 Toy

容易想到使用 Burnside 引理。考虑枚举移位长度 L 与 N 的 \gcd，设为 d。

对于一个 d，我们期望求出每 d 个点为一个周期的生成树个数。我们令边 (i,n+1) 和边 (i,i+1) 为第 i 组边，以 d 为周期的生成树要求：第 1 组边和第 d+1 组边状态相同且前 d+1 组边形成生成树。

容易想到矩阵快速幂维护动态规划，状态是一个 0/1 状态，表示当前考虑的点 i 和点 n+1 是否已经相连。所以矩阵大小是 2\times 2 的。时间复杂度是 O(2^3N^\frac{1}{3}\log N)。

启发：不要永远尝试推出特别恐怖的式子，可以找到其他方法解决。略微暴力一点也可能是好的选择。