[SHOI2006]有色图——Burnside引理

题面

解析

　　似乎是个挺经典的题呢。"[HNOI2009]图的同构"是这个的弱化版(只有两种颜色)。这个题还和$sgu282$一模一样。

　　这种求本质不同的方案数的题，考虑用$Burnside$引理统计答案。

　　这个题虽然是问的边染色的本质不同方案数，但边的置换并不好搞，因此还是考虑点的置换，假设点的置换为$(a_1,a_2,cdots,a_n)$，可以被拆分为$k$个不相交循环，假设长度为$b_1,b_2,cdots,b_k$，该置换下的不动点个数为$m$的该置换下边等价类个数次方。

　　我们对这个边分类讨论一下。

　　第一类是边的两个端点在同一个循环里。不难发现这种情况下置换前后边的长度是没有变的，又因为端点每次只会走一步，因此长度相等的边就属于同一等价类，而不同等价类的个数自然就是$leftlfloor frac{b}{2} ight floor$

　　第二类边是两个端点在不同循环里，不妨设分别在$b_1,b_2$中。每次置换，两个端点各自走一步，因此重新回到开始的两个起点需要$lcm(b_1,b_2)$步，也就是说有$lcm(b_1,b_2)$条边是等价的，那么等价类个数就是$frac{b_1*b_2}{lcm(b_1,b_2)}=gcd(b_1,b_2)$

　　所以一个置换总的边等价类个数为$sum_{i=1}^k b_i+sum_{i=1}^ksum_{j=i+1}^k gcd(b_i,b_j)$

　　但不能枚举每一种点的置换，于是可以枚举$b$，并且规定$b_1 leqslant b_2 leqslant cdots leqslant b_k$，那么现在的问题就变成了如何统计当前的$b$对应了多少种置换。

　　首先如果不考虑每个循环里点的顺序，那么答案就是$frac{n!}{prod b_i!}$，现在考虑每个环内的排序，钦定一个点的位置，剩下的点随便排，有$(b_i-1)!$种方案，那么答案就是$frac{n!}{prod b_i!}*prod (b_i-1)!=frac{n!}{prod b_i}$。但这时会记重，考虑$b_i=b_{i+1}$的情况，交换$b_i$和$b_{i+1}$内的点，可以发现交换前后对应的置换是不变的，假设$c_i$表示$b$内有多少个数等于$i$，即$c_i=sum_j [b_j == i]$，那么最终的答案就是$$frac{n!}{prod b_i prod_{c_i != 0}c_i}$$

　　因为最后的答案需要除以$n!$，因此该系数可以直接写成$$frac{1}{prod b_i prod_{c_i != 0}c_i}$$

　　$dfs$出$b$的所有方案，统计答案即可。

　代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn = 60;

int n, m, mod, gc[maxn][maxn], ans;
ll inv[maxn];

int add(int x, int y)
{
    return x + y < mod? x + y: x + y - mod;
}

ll qpow(ll x, int y)
{
    ll ret = 1;
    while(y)
    {
        if(y&1)
            ret = ret * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ret;
}

void init()
{
    inv[0] = inv[1] = 1;
    for(int i = 2; i <= n; ++i)
        inv[i] = (mod - mod / i) * inv[mod%i] % mod;
    for(int i = 1; i <= n; ++i)
        gc[0][i] = i;
    for(int i = 1; i <= n; ++i)
        for(int j = i; j <= n; ++j)
            gc[i][j] = gc[j%i][i];
}

int stak[maxn], top;

void dfs(int x, int idx, ll mul, int num)
{
    if(x == n)
    {
        ans = add(ans, qpow(m, idx) * mul % mod);
        return ;
    }
    int pre = stak[top], t1, t2;
    for(int i = pre; i <= n - x; ++i)
    {
        stak[++top] = i;
        t1 = idx + (i >> 1);
        for(int j = 1; j < top; ++j)
            t1 += gc[stak[j]][i];
        t2 = mul * inv[i] % mod;
        if(i == pre)
            t2 = t2 * inv[num+1] % mod;
        dfs(x + i, t1, t2, (i == pre)? num + 1: 1);
        -- top;
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &mod);
    init();
    stak[0] = 1;
    dfs(0, 0, 1, 0);
    printf("%d", ans);
    return 0;
}

View Code