这是一篇 Pólya 题解。若想了解 DGF（狄利克雷生成函数）做法请移步。
本质不同问题+染色一般用 Pólya 定理解决。
在考虑环形问题之前（即用 Pólya 定理之前），先考虑链状问题，即所有元素排列成链状时，显然可以设计如下的转移状态：fi, j 表示长度为 j，元素乘积为 i 的方案数。转移就大家各显神通吧。官方题解给出了 Θ(Ulog2U) 的转移（实际上只有改变维度顺序，但是足以比暴力转移优化掉一个 log ）。但是我用 Θ(Ulog3U) 不要脑袋暴力转移不加任何优化过了有些好笑。
算了还是讲讲吧。考虑序列一个一个加元素，那么第二维 j
可以先行枚举。第一维转移显然是调和级数，所以复杂度是 Θ(Ulog2U)。比起
3log
做法本质区别是改变维度遍历顺序，使得不需要考虑位置的优化。当然两种方法得出来的结果是相同的。
接下来是迁移到环上问题。我们重新复习一下 Pólya 定理：
给定群 G 在集合 X 上的作用和颜色集合 C，则不同的染色方案的数目 $$ |C^X/G|=\frac{1}{G}\sum_{g\in G}m^{c(g)} $$ 这里，m 是颜色数目，c(g) 是元素 g ∈ G 的置换表示的轮换分解中的轮换数目。
这里颜色集合比较显然，CX 即线性问题的所有染色方案，G 则是所有的环移动方案，即： r0, r1, …, rj − 1 这里的 j 即我们枚举的环长。那么关键是这里的 c(g)。对于 rk 对应的 g，令 d = gcd (j, k)，那么有 $c(g_{r_k})=f_{\sqrt[\frac{j}{d}]{i},d}$。这个转移式是 Θ(Ulog2U) 的。那么我们就得到一个 Θ(Ulog2U) 的做法了。