Burnside 引理

ans = { 1 \over |G| } \sum_{f \in G} C(f) ,其中 C(f) 表示置换 f 中不动点的个数

Polya 定理

定义 L(f) 为置换 f 的循环节数,可以理解为对于任意一种状态至多经过 L(f) 次置换 f 可以变回原样。

易证置换 f 的不动点一定满足其自身的循环节为 L(f) ,即 C(f) = k^{L(f)} ,其中 k 表示颜色种数。

Polya 定理的公式即 ans = { 1 \over |G| } \sum_{f \in G} k^{L(f)}

READ MORE

f_i 表示 i 个时的高度之和, g_i 表示 i 个时的方案数,显然:

\begin{aligned} g_n &= \sum\limits_{i=1}^n {n \choose i} g_{n-i} \\ f_n &= g_n + \sum\limits_{i=1}^n {n \choose i} f_{n-i} \\ ans_n &= f_n \times g_n^{-1} \end{aligned}

其实到这里可以直接分治 NTT ,不过我们考虑多项式求逆的做法。 首先把 {n \choose i} 拆开,然后设 F_n = f_n / n!G_n = g_n / n!H_n = 1 / n!

\begin{aligned} G &= (2 - H)^{-1} \\ F &= (G - 1) (2 - H)^{-1} \\ ans_n &= F_n G_n^{-1} \end{aligned}

(推导时需要注意常数项系数,f_0 = 0,g_0 = h_0 = 1。)

READ MORE