题意

给定一张 N 个点 M 条边的无向图，每条边要染一个编号在 1 到 K 的颜色。

你可以对一张染色了的图进行若干次操作，每次操作形如，在图中选择一个简单环（即不经过相同点的环），并且将其颜色逆（顺）时针旋转一个单位。

两种染色方案被认为是本质相同的，当且仅当其中一种染色后的图经过若干次操作后可以变成另一种染色后的图。

问有多少本质不同的染色方案，输出对 10^9+7 取模。

思路

先在原图上求点双连通分量，这样图中的每条边都仅会被分到一个点双中。对于每个点双连通分量，考虑以下三种情况：

1. 只包含一条边 即这条边不在任何一个环中。这条边可以涂上任何颜色，对答案的贡献为 K 。

2. 包含一个简单环（边数 = 点数） 此时要求的是 K 种颜色的定长循环不同构环的个数。可以用 Polya 定理 求解。Polya 定理 是 Burnside 引理 的一种特殊情况。Burnside 引理：等价类数目为所有置换的不变元数目的平均值。而 Polya 定理 提供了在染色问题中计算不变元数目的具体方法：假设一个置换有 k 个循环，如果有 m 种可选的颜色，则这个置换的不变元数目为 m^k 。而对于本题来说，一个长度为 l 的环的顺时针转 p 次的置换有 gcd(l, p) 个循环，于是这个置换的不变元数目即为 K^{gcd(l, p)} 。代入 Burnside 引理 ，即可求得该点双的贡献。

3. 包含一个多个简单环（边数 > 点数） 可以证明任意一种置换都可以循环位移出来，直接组合数计算其贡献即可。设边数为 e ，则贡献为 C_{e+K-1}^e （隔板法）。

最后，根据乘法原理，最终的答案即为所有点双连通分量的贡献的积。

代码

#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
const int MAXN=55;
const int MAXM=110;
const int P=1E9+7;
struct Edge
{
    int from, to;
    Edge(int u, int v): from(u), to(v) {}
};
int n, m, k, cnt, t1, t2, tot;
int c[2*MAXM][MAXM], f[MAXM];
int dfn[MAXN], low[MAXN];
int s1[MAXN], s2[MAXM];
int c1[MAXM], c2[MAXM];
bool ins[MAXN];
vector<Edge> edges;
vector<int> g[MAXN];
int gcd(int a, int b)
{
    if (b==0) return a;
    return gcd(b, a%b);
}
int exgcd(int a, int b, int& x, int& y)
{
    if (b==0) x=1, y=0;
    else exgcd(b, a%b, y, x), y-=a/b*x;
}
int qpow(int a, int b)
{
    int r=1;
    while (b)
    {
        if (b&1) r=1ll*r*a%P;
        a=1ll*a*a%P; b>>=1;
    }
    return r;
}
int inv(int a)
{
    int x, y;
    exgcd(a, P, x, y);
    return (x%P+P)%P;
}
void init()
{
    memset(c, 0, sizeof c);
    c[0][0]=1;
    for (int i=1; i<=m+k; i++)
    {
        c[i][0]=1;
        for (int j=1; j<=i&&j<=m; j++)
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%P;
    }
    memset(f, 0, sizeof f);
    for (int i=1; i<=m; i++)
    {
        for (int j=1; j<=i; j++)
            f[i]=(f[i]+qpow(k, gcd(i, j)))%P;
        f[i]=1ll*f[i]*inv(i)%P;
    }
    edges.clear();
    for (int i=1; i<=n; i++) g[i].clear();
    memset(dfn, 0, sizeof dfn);
    memset(ins, 0, sizeof ins);
    cnt=tot=t1=t2=0;
}
inline void addEdge(int u, int v)
{
    edges.push_back(Edge(u, v));
    edges.push_back(Edge(v, u));
    g[u].push_back(edges.size()-2);
    g[v].push_back(edges.size()-1);
}
void tarjan(int u, int f)
{
    low[u]=dfn[u]=++cnt; ins[u]=1;
    for (int i=0; i<g[u].size(); i++)
    {
        int v=edges[g[u][i]].to;
        if (!dfn[v]||v!=f&&ins[v])
        {
            s2[++t2]=g[u][i];
            if (!dfn[v])
            {
                s1[++t1]=v;
                tarjan(v, u);
                low[u]=min(low[u], low[v]);
                if (low[v]>=dfn[u])
                {
                    c1[++tot]=1; c2[tot]=0;
                    do c1[tot]++; while (s1[t1--]!=v);
                    do c2[tot]++; while (s2[t2--]!=g[u][i]);
                }
            }
            else low[u]=min(low[u], dfn[v]);
        }
    }
    ins[u]=0;
}
int main()
{
//  freopen("A.in", "r", stdin);
//  freopen("A.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    init();
    for (int i=1; i<=m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        addEdge(u, v);
    }
    for (int i=1; i<=n; i++)
        if (!dfn[i]) tarjan(i, 0);
    int ans=1;
    for (int i=1; i<=tot; i++)
    {
        if (c1[i]==c2[i]) ans=1ll*ans*f[c2[i]]%P;
        else if (c1[i]<c2[i]) ans=1ll*ans*c[c2[i]+k-1][c2[i]]%P;
        else ans=1ll*ans*k%P;
    }
    printf("%d\n", ans);
    return 0;
}