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()：
在这题中。。就是从
点置换的循环数 去推 边置换的循环数。。。

分类讨论：

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}

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

Posted by xiaodao
Category: SGU
Tags: Polya 计数法