学习笔记

P4980 【模板】Pólya 定理
Polya 定理模板，但是 莫比乌斯反演 也能直接做。

P2561 [AHOI2002]黑白瓷砖
很板的 Polya 定理。只要把旋转分类讨论以下即可。

LOJ 6185. 烷基计数
考虑 \(dp\), \(f_i\) 表示 \(i\) 个结点的烷基个数。
枚举根结点下接结点的方案(\(123\), \(132\), \(213\), \(231\), \(312\), \(321\))。
可以得到 \(f_n = \frac{1}{6}(2\sum\limits_{3i + 1 = n} f_i + 3\sum\limits_{2i + j + 1 = n} f_i f_j + \sum\limits_{i + j + k + 1 = n} f_i f_j f_k)\)

LOJ 6269. 烷基计数 加强版
把上面那个东西交换以下求和顺序即可。

LOJ 6538. 烷基计数 加强版 加强版
看到模数不同了，列生成函数式子：\(F(x) = \frac{1}{6}(2F(x^3) +3 F(x)F(x^2) + F^3(x)) + 1\)。
\(\frac{x}{6}(2F(x^3) + 3 F(x)F(x^2) + F^3(x)) + 1 - F(x) = 0\)。倍增时 \(F(x^2)\) 和 \(F(x^3)\) 已经求出。牛顿迭代即可。

SP419 TRANSP - Transposing is Fun
首先可以转化成这是一个置换，然后求其中的循环个数。
然后考虑一个位置变换后的编号，就是把他二进制的后 \(m\) 位提到前面。
现在求有多少本质不同的数。然后这个直接 \(Polya\) 就行了。

SP422 TRANSP2 - Transposing is Even More Fun
小优化，加快分解因子。

P4128 [SHOI2006]有色图, P4727 [HNOI2009]图的同构计数
感觉很巧妙。可以枚举这个对应关系拆分成的循环大小，这个的本质不同种类数其实相当于 \(n\) 的划分数。这个可以 \(dfs\) 来找。
然后就随便算一下贡献和种类数即可。

P6597 烯烃计数
可以考虑枚举那条碳双键的边两边的东西（是烷基），然后卷起来。
但是这样会算重（烯烃两边的东西交换重复算），这样子还是用 burnside 引理来解决就好了。

P6598 烷烃计数
设答案数组为 \(g\)，假设是有根树，根为重心，首先做一遍烷基计数。设为 \(f\)。
可以先把 \(f\) 中大于 \(\lfloor\frac{n}{2}\rfloor\) 的东西都去掉。
\(g_n = \frac{1}{24}( (6 \sum\limits_{i \times 4 + 1 = n} f_i) + (3\sum\limits_{2 \times (i + j) + 1 = n} f_i f_j) + (8\sum\limits_{3i + j + 1 = n} f_i f_j) + (6 \sum\limits_{i + j + 2 \times k + 1 = n} f_i f_j f_k) + (\sum\limits_{i + j + k + d + 1 = n} f_i f_j f_k f_d))\)
生成函数：\(G(x) = \frac{x}{24} ( 6F(x^4) + 3F(x^2)^2 + 8F(x^3) F(x) + 6 F(x^2)F(x)^2 + F(x)^4)\)，这样可拿到 \(40\) 分。
没考虑到的双重心的情况其实是两个大小相同的不同烷基拼接在一起，减去这些多余贡献即可。

P5818 [JSOI2011]同分异构体计数
这题只要把烷基的计数给弄出来，然后把根的度数 \(\le 2\) 的弄出来。再做个 \(dp\)。\(dp_{i, j}\) 表示 \(i\) 个环上结点 \(j\) 个根结点的方案数。
对于旋转的本质相同的, \(Polya\) 解决；对于翻转的，可以发现循环节 \(\le 2\), 把循环节为 \(1\) 的个数抽出来再做即可。

P4916 [MtOI2018]魔力环
可以先判调 \(n = m\)。首先用 Burnside 引理可以转化成 ： 对于 \(\gcd(n, m)\) 的所有因子 \(x\)，计算环长度为 \(\frac{n}{x}\)，有 \(\frac{m}{x}\) 个黑色魔力珠，不能有 \(k\) 个连续黑色魔力珠，且环不能旋转的答案（下文就解决这个问题， \(n\) 代替 \(\frac{n}{x}\)，\(m\) 代替 \(\frac{m}{x}\) ）
可以转化为再 \(n - m\) 的白珠子中塞入 \(m\) 个黑珠子的答案。这个可以用生成函数来求解，答案就是 \([x^m] (\sum\limits_{i = 0}^{k} x^i)^{n - m - 1} ((\sum\limits_{i = 0}^{k} x^i)^2 \bmod x^{k})\)
然后根据一些 推导 就可以快速求这玩意了。