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:
反过来从边置换推点置换怎么做????