P4727 [HNOI2009] 图的同构计数 和 P4128 [SHOI2006] 有色图 题解

· · 题解

0x00 Burnside's lemma

这里需要一点群论的知识，设 G 是一个置换群群，将作用在集合 X 上，有以下结论：

\left|X/G\right|=\frac{1}{\left|G\right|}\sum_{g\in G} \left|X^g\right|

对于这个题来说 X 就是 n 个点的简单无向图集合，一共 2^{{n\choose 2}} 个。G 就是点标号的置换的集合，即排列的集合，一共 n! 个。g 就是一个排列，\left|X^g\right| 则表示按照 g 对图重标号后，有多少个图和原来一样。

若两个图同构，说明可以通过重标号一个图的方式得到另一个图，所以说 \left|X/G\right| 就等于有多少个不同构的数。这样转化重点就是计算 \left|X^g\right|。

0x01 计算 \left|X^g\right|

假设有一个 g，怎么计算 \left|X^g\right|，显然只需要关注边的情况，什么情况下一个图在 g 变换后与原图相同呢？假设现在有两个点 u,v，则他们重编号映射后就是 g_{u},g_{v}，由于要和原图相同，所以 u,v 的连边情况和原图要是相同的。这意味着在 g 的变化下有一些边是等价的，对于某一个等价类，要么全连上要么全不连，假设有 k 个等价类，则有 2^k 个图是不动点，即 \left|X^g\right|=2^k。

0x02 计算 k

寻找等价类的过程就是从某一条边 u\leftrightarrow v 出发，然后寻把 g_{u}\leftrightarrow g_{v} 这条边合并到一个等价类，然后 g_{g_u}\leftrightarrow g_{g_v} 合并，相当于是 u,v 每次分别走到 g 变换的点去，然后重复过程，直到回到最初的点，自然想到把 g 拆成若干个置换环。现在分类讨论 u,v 所在置换环的情况：

设当有 m 个置换环，置换环长度分别为 b_i，根据上面的推论有：

k=\sum_{i=1}^m\left\lfloor\frac{b_i}{2}\right\rfloor+\sum_{i=1}^m\sum_{j=1}^{i-1}\gcd(b_i,b_j)

0x03 统计排列

直接枚举排列显然是不行的，但是发现若排列的置换环长度 b 序列相同，贡献也是相同的，于是直接枚举 b，即 n 的一个整数拆分。考虑计算有多少个排列的置换环长度是 b，先考虑把 n 个数划分到每一个置换环里面，再考虑置换环内部排列方式。随便放有 n! 个排列，但是每一个置换环内部的排列先不计算，所以要除去 b_i!，但是长度相同的置换环交换还是同样的情况，所以也要出去，设长度为 i 的置换环有 c_i 个，就是要除 c_i!，所以划分方案一共是：

\frac{n!}{\prod (b_i!)\prod (c_i!)}

现在考虑置换环内部的排列情况，显然就是圆排列，有 (b_i-1)! 个，最终就是：

\frac{n!\prod (b_i-1)!}{\prod (b_i!)\prod (c_i!)}=\frac{n!}{\prod b_i\prod (c_i!)}

把前面提到的式子整理一下：

\begin{aligned} \left|X/G\right|&=\frac{1}{\left|G\right|}\sum_b \frac{n!2^k}{\prod b_i\prod (c_i!)}\\ &=\frac{1}{n!}\sum_b \frac{n!2^k}{\prod b_i\prod (c_i!)}\\ &=\sum_b \frac{2^k}{\prod b_i\prod (c_i!)}\\ k&=\sum_{i=1}^m\left\lfloor\frac{b_i}{2}\right\rfloor+\sum_{i=1}^m\sum_{j=1}^{i-1}\gcd(b_i,b_j) \end{aligned}

0x04 扩展问题

这道题中每一个图相当于是对边染色了，出现的染白，没出现的染黑，不妨多搞几个颜色。n 个点的无向完全图，有 m 中颜色，可以给边随意染色，问可以染出多少个本质不同的图。要解决这个问题我们回到计算 \left|X^g\right| 一步，最后的统计 2^k 就是再说染黑还是染白，自然有 m 种颜色就是 m^k。

\begin{aligned} \left|X/G\right|&=\sum_b \frac{m^k}{\prod b_i\prod (c_i!)}\\ k&=\sum_{i=1}^m\left\lfloor\frac{b_i}{2}\right\rfloor+\sum_{i=1}^m\sum_{j=1}^{i-1}\gcd(b_i,b_j) \end{aligned}

于是就得到了 P4128 一题做法。

#include<bits/stdc++.h>
// #define ONLINE_JUDGE
#define INPUT_DATA_TYPE int
#define OUTPUT_DATA_TYPE int
inline __attribute((always_inline)) INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;}

#define INV_DATA_TYPE long long
INV_DATA_TYPE exgcd(INV_DATA_TYPE a,INV_DATA_TYPE b,INV_DATA_TYPE &x,INV_DATA_TYPE &y){
    if(!b){
        x=1;
        y=0;
        return a;
    }
    INV_DATA_TYPE d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

INV_DATA_TYPE inv(INV_DATA_TYPE n,INV_DATA_TYPE p){
    INV_DATA_TYPE x,y;
    exgcd(n,p,x,y);
    x%=p;
    return x>=0?x:x+p;
}

long long mod,modp;
int b[70],gcd[70][70],m,p;
long long fact[1000],pwm[100000],res;

void calc(int K){
    register int i,j,k=0,cnt=0;
    register long long v=1;
    b[K]=-1;
    for(i=0;i<K;++i){
        k+=b[i]>>1;
        (v*=b[i])%=mod;

        ++cnt;
        if(b[i]!=b[i+1]){
            (v*=fact[cnt])%=mod;
            cnt=0;
        }

        for(j=0;j<i;++j)
            k+=gcd[b[i]][b[j]];
    }
    (res+=inv(v,mod)*pwm[k])%=mod;
}

void dfs(int st,int rst){
    if(!rst){
        calc(st);
        return;
    }
    for(;b[st]<=rst;++b[st]){
        b[st+1]=b[st];
        dfs(st+1,rst-b[st]);
    }
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("name.in", "r", stdin);
    freopen("name.out", "w", stdout);
    #endif

    register int i,j;
    int n=read();
    m=read();
    modp=(mod=read())-1;
    for(i=0;i<=n;++i)
        for(j=0;j<=n;++j)
            if(i==0||j==0)
                gcd[i][j]=i|j;
            else{
                if(i>=j) gcd[i][j]=gcd[i-j][j];
                else gcd[i][j]=gcd[i][j-i];
            }

    for(fact[0]=i=1;i<=n;++i) fact[i]=fact[i-1]*i%mod;
    for(pwm[0]=i=1;i<=n*n;++i) pwm[i]=pwm[i-1]*m%mod;

    b[0]=1;
    dfs(0,n);

    print(res);

    #ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    #endif
    return 0;
}