SGU 282. Isomorphism


http://endlesscount.blog.163.com/blog/static/8211978720122154253812/

思路

http://www.shuizilong.com/house/archives/poj-2154-color/
。。。置換太多。。怎麼辦!分組計數!!。。Pattern 為分拆數。。。http://en.wikipedia.org/wiki/Partition_(number_theory)

那麼對於每類 Pattern:

對應多少置換。。。 c()。。
循環的總數:g()。。

前者多項式係數。。乘以環排列。。除以相同長度的環即可。。比較容易。。
難點是 g():
在這題中。。就是從
點置換的循環數 去推 邊置換的循環數。。。

分類討論:

1. 對於邊所關聯的兩點。。不再同一個循環中:

。。。設這兩個循環的長度分別為 a, b 。。。
那麼這類邊一共有 ab 個。。所在邊循環的長度為 lcm(a, b)。。。
因此邊循環的數目為 ab / lcm(a, b) = gcd(a, b)。。。。

2.。。。。在同一個循環中。。

此處應有插圖。。。

總共對應 \binom{n}{2} 個邊置換。。。

幾乎所有的邊都是經過 n 次才會回到自己。。。
除了在偶數的情況下。。最長的那種邊。。恰好 n/2 次就會回到自己。。這會導致循環數 +1。。。

因此循環的個數為:

奇數:
\binom{n}{2} / n = (n-1)/2 = \floor{n/2}
偶數:
\binom{n}{2} / n + 1。。。(n-1) / 2 + 1 = \floor{n/2}

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2895999

Ext:
反過來從邊置換推點置換怎麼做????