【BZOJ1478】Sgu282 Isomorphism
題意：用$m$種顔色去染一張$n$個點的完全圖，如果一個圖可以通過節點重新标号變成另外一個圖，則稱這兩個圖是相同的。問不同的染色方案數。答案對$P$取模。
$n\le 53,m\le 1000,P>n,P$是質數。
題解：對于本題來說，每個元素是所有邊，每個置換是邊的置換，而邊的置換難以表示，點的置換容易表示，是以我們考慮點置換和邊置換的關系。
如果兩個點置換有着相同的結構，則它們對應的邊置換的循環數相同。
$$\begin{pmatrix}1&2&3 \ 2&1&3\end{pmatrix}\rightarrow\begin{pmatrix}(1,2)&(1,3)&(2,3) \ (1,2)&(2,3)&(1,3)\end{pmatrix}$$
$$\begin{pmatrix}1&2&3 \ 1&3&2\end{pmatrix}\rightarrow\begin{pmatrix}(1,2)&(1,3)&(2,3) \ (1,3)&(1,2)&(2,3)\end{pmatrix}$$
一個點置換的結構：在表示成循環節時，循環的大小依次為$L_1,L_2,...L_K$。
$L_1,L_2,...L_K$可以組成一個$n$的劃分。
而當$n$=53時，$n$個劃分數不超過$300000$。
可以通過搜尋得出。
那麼一個結構為$L_1,L_2,...L_K$的點置換對應邊置換的循環數是什麼呢？
對于端點在不同點循環中的邊，設兩端點所在點循環大小為$L_1,L_2$，則這樣的邊一共有$L_1\times L_2$條，而每個循環有$lcm(L_1,L_2)$條邊，是以一共有$gcd(L_1,L_2)$個循環。
對于端點在同一點循環中的邊，設所在點循環的大小為$L$，這樣的邊一共有$C_L^2$條。然後分奇偶讨論：
如果$L$是奇數，那麼一個循環中有$L$條邊，是以循環數為${C_L^2\over L}={L-1\over 2}$。
如果$L$是偶數，那麼一個循環中有$L$條邊，但是如果兩端點相隔$L\over 2$，這個循環中有$L\over 2$條邊。是以循環數為${C_L^2-{L\over 2}\over L}+1={L\over 2}$。
是以一個大小為$L$的點循環中邊循環的數量是$\lfloor{L\over 2}\rfloor$。
結構為$L_1,L_2,...L_K$的點置換中邊循環的數量就是
$$\sum\limits_{i=1}^n\lfloor{L_i\over 2}\rfloor+\sum\limits_{i=1}K\sum\limits_{j=1}{i-1}gcd(L_i,L_j)$$
那麼有多少結構為$L_1,L_2...L_K$的點置換呢？可以先求出$n!\over {L_1!L_2!...L_K!}$得到每個點屬于哪個循環的方案數，而對于每個循環，我們可以先确定第一個點，然後其餘點任意排列，方案數是$(L_1-1)!(L_2-1)!...(L_K-1)!$。乘起來得到$n!\over {L_1L_2...L_k}$。
又由于存在一些$L$相等的情況，設有$t$種本質不同的$L$，每種個數為$B_i$，是以總方案數還要除掉$B_1!B_2!...B_t!$，是以總數為：
$$n!\over L_1L_2...L_KB_1!B_2!...B_t!$$
最後套上Pólya定理，令$c=\sum\limits_{i=1}^n\lfloor{L_i\over 2}\rfloor+\sum\limits_{i=1}K\sum\limits_{j=1}{i-1}gcd(L_i,L_j)$，$s={n!\over L_1L_2...L_KB_1!B_2!...B_t!}$，答案就是
$$\frac 1 {n!}\sum s\times m^c$$
|
歡迎來原網站坐坐！
>原文連結<