poj 2888

n 种轮换（$|G|=n$）

第 i 种可以分成长度为 $\frac{n}{\gcd(n,i)}$ 的 $\gcd(n,i)$ 个轮换

$\forall g\in G$，$|X^g|$（不定点个数）等于规模为 $\gcd(n,i)$ 的环的答案然后搞一搞

傻逼poj

P4916

枚举 $d$

转化成有 $d$ 个球，要染 $\frac md$ 个，不能有连续 $k$ 个被染色

考虑插板，有 $\frac{m}{d}$ 个色球，$d-\frac{m}{d}$ 个无色球，把色球插入无色球之间

断换成链的手段是枚举首尾之间插入的色球数量

$\displaystyle \sum_{i=0}^k(i+1)\times f(\frac{m}{d}-i,\frac nd-\frac{m}{d}-1,k)$

$f(n,m,k)$ 表示把 $n$ 个球分成 $m$ 组，每组不超过 $k$ 个的方案数（容斥）

p4128

把点置换转化成边置换，再用 Polya（大体思路）

设点置换群 $\lang G,\cdot \rang$，取某个 $g \in G$，$g=\prod_i (a_{i,1},a_{i,2},...,a_{i,n_i})$

• $\forall i\neq j$，研究 $(a_i)$ 和 $(a_j)$

比如 $(u,v)$，会被置换成 $(u+1,v+1)$，$(u+2,v+2)$，直到 $(u+\mathrm{lcm}(n,m),v+\mathrm{lcm}(n,m))$。置换的长度就是两个环的长度的 $\mathrm{lcm}$，一共有 $n\times m$ 个元素，所以一共 $\frac{nm}{\mathrm{lcm}(n,m)}=\gcd(n,m)$ 个循环

• 研究 $(a_i)$（同一个循环节里面）

$\frac n2$ 个循环

设 $g$ 拆成 $k$ 个循环

边循环个数 $\sum_{i}^k \frac{n_i}2+\sum_{i=1}^{k-1}\sum_{j=i+1}^k \gcd(n_i,n_j)$

不能枚举 $n!$ 种点排列

发现如果 $\{n_k\}$ 相同，贡献相同

$\{n_k\}$ 加起来是 $n$，枚举 $n$ 的分拆数（妙）

算 $\{n_k\}$ 的贡献系数：钦定 $n_1 \leqslant n_2 \leqslant \dots \leqslant n_k$，把每个循环看作圆排列，设 $t_i$ 为长度为 $i$ 的循环数，则系数为 $\frac{n!}{\prod n_i \prod t_i!}$

dfs+Polya 计算