2013-team4/code/combinatorics-formula

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

Burnside's Theorem
{{{
X为一个置换群，C为一个染色的集合，需要满足C在X作用下封闭。
此时不同染色数为N(G,C)=sigma(|C(f)|)/|G|, f∈G
C(f)表示在f置换下，C中元素c使满足f(c)==c的c的个数。
}}}
Dehedral Group Dn of order 2n
{{{
置换ρi，中的循环数#(ρk) = gcd(i,n)
并且每个环的长度都为n/gcd(i,n)

具有环数为k的置换，（k|n)
有φ(n/k)种。
（欧拉函数）
}}}
代码实现
{{{
//将calc(i)改成需要的函数用以计算
//复杂度sqrt(n)*O(calc)
int polya(int n){
    int res = 0;
    for(int i = 1; i * i <= n; i ++){
        if (n % i) continue;
        int j = n / i;
        res = (res + (LL)calc(i) * euler(j)) % MOD;
        if (j!=i) res = (res + (LL)calc(j) * euler(i)) % MOD;
    }
    res = res * (LL) inv(n) % MOD;
    return res;
}
}}}

Burnside's Theorem

X为一个置换群，C为一个染色的集合，需要满足C在X作用下封闭。
此时不同染色数为N(G,C)=sigma(|C(f)|)/|G|, f∈G
C(f)表示在f置换下，C中元素c使满足f(c)==c的c的个数。

Dehedral Group Dn of order 2n

置换ρi，中的循环数#(ρk) = gcd(i,n)
并且每个环的长度都为n/gcd(i,n)
具有环数为k的置换，（k|n)
有φ(n/k)种。
（欧拉函数）

代码实现

//将calc(i)改成需要的函数用以计算
//复杂度sqrt(n)*O(calc)
int polya(int n){
    int res = 0;
    for(int i = 1; i * i <= n; i ++){
        if (n % i) continue;
        int j = n / i;
        res = (res + (LL)calc(i) * euler(j)) % MOD;
        if (j!=i) res = (res + (LL)calc(j) * euler(i)) % MOD;
    }
    res = res * (LL) inv(n) % MOD;
    return res;
}