http://endlesscount.blog.163.com/blog/static/8211978720122154253812/
思路
同 https://www.shuizilong.com/house/archives/poj-2154-color/
。。。置换太多。。怎么办！分组计数！！。。Pattern 为分拆数。。。http://en.wikipedia.org/wiki/Partition_(number_theory)
那么对于每类 Pattern：
对应多少置换。。。 c()。。
循环的总数：g()。。
前者多项式系数。。乘以环排列。。除以相同长度的环即可。。比较容易。。
难点是 g()：
在这题中。。就是从
点置换的循环数 去推 边置换的循环数。。。
分类讨论：
- 对于边所关联的两点。。不再同一个循环中：
。。。设这两个循环的长度分别为 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}
https://vjudge.net/solution/43124199
#include <lastweapon/number>
using namespace lastweapon;
const int N = int(5e1) + 9;
Int Fact[N]; VVI Partition; VI cur;
int n, m;
void gen(int n = ::n, int s = 1){
if (!n){
Partition.PB(cur);
}
else if (n >= s){
cur.PB(s); gen(n-s, s); cur.pop_back();
gen(n, s+1);
}
}
Int c(const VI P){
Int z = Fact[n]; int c = 0, l = P.front();
ECH(it, P){
z /= *it; if (*it != l){
z /= Fact[c]; l = *it;
c = 1;
}
else{
++c;
}
}
z /= Fact[c];
return z;
}
int g(const VI P){
int z = 0; REP(i, SZ(P)){
z += P[i] / 2; REP(j, i) z += __gcd(P[i], P[j]);
}
return z;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
RD(n, m, MOD); Fact[0] = 1; REP_1(i, n) Fact[i] = Fact[i-1] * i;
gen();
Int res = 0; ECH(it, Partition){
res += c(*it) * pow(m, g(*it));
//cout << c(*it) << " " << pow(m, g(*it)) << " " << res << endl;
}
res /= Fact[n];
cout << res << endl;
}
Ext:
反过来从边置换推点置换怎么做？？？？
