P8633 题解

寻逍遥2006 · 2023-04-20 13:05:23 · 题解

题意：就对于一个有 n 个节点的图进行 k 染色，本质不同的染色方式有多少种。

其中，两种染色方式相同称为对其中一个图的所有点重编号之后，两个图同构且对应点颜色相同。

考虑使用 Polya 定理，那么我们就需要找到所有置换，满足对点进行置换之后图仍然同构。

比如说，对于样例来说，所有满足条件的置换为 (1,2,3) 和 (3,2,1)。

由于 n\leqslant 10，所以可以考虑暴力枚举每一种置换是否满足上述条件既可。单次判断可以直接使用 O(m) 或者 O(n^2) 的暴力判断。

找到置换群 G 之后，根据 Polya 定理，答案即为 \dfrac{1}{|G|}\sum\limits_{g\in G}m^{\sigma(g)}，其中 \sigma(g) 表示每一个置换 g 的环的个数，这个部分可以 O(n) 求出。

总体复杂度为 O(m\times n!+|G|\times n) 或者 O(n^2\times n!+|G|\times n)。

由于时限宽松，这里给出一个较劣的 O(n^2\times n!+|G|\times n) 算法。

#include <bits/stdc++.h>
#define Mod 10007
using namespace std;
int Qread()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return x;
}
long long qpow(long long a,long long p)
{
    long long ret=1;
    for(;p;p>>=1,a=a*a%Mod)
        if(p&1) ret=ret*a%Mod;
    return ret;
}
int n,m,k,u,v;
long long ans,cnt;
bool ed[20][20];
int p[20];bool vis[20];
bool chk()
{
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        if(ed[i][j]^ed[p[i]][p[j]])
            return false;
    return true;
}
int get_cir()
{
    int ret=0,nw;
    for(int i=1;i<=n;i++) vis[i]=false;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]) continue;
        nw=i;
        do vis[nw]=true,nw=p[nw];
        while(nw!=i);
        ret++;
    }
    return ret;
}
int main()
{
    n=Qread(),m=Qread(),k=Qread();
    for(int i=1;i<=n;i++)
        p[i]=i;
    for(int i=1;i<=m;i++)
    {
        u=Qread(),v=Qread();
        ed[u][v]=ed[v][u]=true;
    }
    do
    {
        if(!chk()) continue;
        cnt++;
        ans=(ans+qpow(k,get_cir()))%Mod;
    }while(next_permutation(p+1,p+n+1));
    printf("%d\n",ans*qpow(cnt,Mod-2)%Mod);
    return 0;
}