概述
如果题目中定义一种等价关系，满足等价关系的元素被看成同一类，只统计一次；这样的问题称为等价类计数问题。一般的等价类计数问题可以用 Burnside 引理或 Pólya定理解决。
刚复习了一遍 qwq 我当时写得真好
模板
置换
置换实际上就是一一映射，$f$ 可以看成定义域和值域为 $\lbrace 1,2,3,…,n\rbrace$ 的函数，其中 $f(1)=a_1$， $f(2)=a_2$ 等等。
$$
f=
\left(\begin{array}{cccc}
1&2&…&n \
a_1&a_2&…&a_n \
\end{array}\right)
$$
函数复合
如果
$$
f=
\left(\begin{array}{cccc}
1&2&…&n \
a_1&a_2&…&a_n \
\end{array}\right)
$$
且
$$
g=\left(\begin{array}{cccc} 1&2&…&n \ b_1&b_2&…&b_n \ \end{array}\right)
$$
是 $\lbrace 1,2,3,…,n\rbrace$ 的两个置换，则他们的复合按照先 $f$ 后 $g$ 的顺序放置得到一个新置换：
$$
g\circ f=
\left(\begin{array}{cccc}
1&2&…&n \\
a_1&a_2&...&a_n \\\end{array}\right)
\circ
\left(\begin{array}{cccc}
1&2&…&n \
b_1&b_2&…&b_n \
\end{array}\right)
$$
循环
为了处理方便，常常把置换分解成循环的乘积，其中每个循环代表一些元素“循环移位”。比如 $(1,4,3)$ 这个循环表示 $1\rightarrow 4$，$4\rightarrow 3$，$3\rightarrow 1$。
易证任意置换都可以分解为循环乘积的形式。
例题
在 2*2 方格中涂黑白两色，方格允许旋转，有几种方法？
假设不考虑方格允许旋转，则共有 16 种上色方案。本题中“旋转后相同”即为一个等价关系，有了等价关系，所有元素会被分为若干个等价类，我们需要统计的即为等价类的个数。
对于一个置换 $f$ ，若一个着色方案 $s$ 经过置换后不变，称 $s$ 为 $f$ 的不动点。将 $f$ 的不动点数目记为 $C(f)$，则可以证明等价类数目为置换群中所有 $C(f)$ 的平均值。此结论称为 Burnside 引理。
一般地，如果置换 $f$ 被分解为 $m(f)$ 个循环的乘积，那么每个循环内所有位置的颜色必须相同，假设涂 $k$ 种颜色，则有 $C(f)=k^{m(f)}$。带入 Burnside 引理的表达式之后得到 Pólya 定理：等价类的个数等于置换群种所有置换 $f$ 的 $k^{m(f)}$ 的平均数。
将 $t$ 种颜色的 $n$ 个小球排成一个环，允许旋转和翻转，有几种方法？
首先考虑旋转置换。记置换 $f_i$ 为将环形顺时针旋转 $i$ 个单位长度。显然，$m(f_i)=gcd(i,n)$ 。
其次考虑翻转置换。当 $n$ 为奇数时，$|G|=n$，且 $m(f)=(n-1)/2+1$；当 $n$ 为偶数时，$|G|=n$，且 $m(f)=n/2+1$。
记：
$$
a=\Sigma_{i=0}^{n-1} t^{gcd(i,n)}\
b=\begin{cases}
t^{(n-1)/2+1} , n=2k+1\
t^{n/2+1},n=2k
\end{cases}
$$
最终答案 $ans=(a+b)/2n$。