传送门

有个神秘的结论就是任意一个边数大于点数的点双连通分量里面,可以通过循环移位的组合来得到点双里面的边的任意置换。这个结论是我卡了2h不会做之后打表打出来的。。。

然后就好做了,直接把点双求出来之后,如果一条边不属于任意一个点双,则他对答案的贡献(乘上去)就是$K$。然后考虑每个点双,记这个点双里面有$d$条边,如果这个点双里面没有环(孤立点或两个点之间一条边),贡献就是$K^d$;如果这个点双是一个环,则置换群比较规律,直接暴力用polya定理算出贡献就行了;否则,根据上面那个结论,边的顺序可以随便交换,所以贡献就是用不同的颜色划分边集的方案数,即$\binom{d+K-1}{K-1}$。

顺便讲个笑话,之前我和hgr,gjs他们看到一道题,就是把上面最后一种情况单独出出来了,$d,K\leq 10^5$。然后我们一直在套polya定理做,最后得出来一个含有第一类斯特林数的式子,差点就开始写第一类斯特林数求行了。结果发现别人AC代码才几百B,觉得有点不对劲,发现那整个斯特林数的式子能直接化成一个组合数(就是上面那个)。。。这个的印象还是很深刻的,所以今天做这题就没有陷进polya定理和斯特林数的深坑里去了2333

#include <cstdio>
#include <cstring>
#include <stack>
#define LL long long
#define MAXN 2010
using namespace std;

const LL P=1000000007;

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n,m,C;
int g[MAXN],nume;
int dfn[MAXN],low[MAXN],numw;
stack<int> S;
bool instack[MAXN];
int c[MAXN][MAXN],d[MAXN],d0[MAXN],numc;
LL binom[MAXN][MAXN];

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

void tarjan(int x,int pe){
    dfn[x]=low[x]=++numw;
    S.push(x);
    instack[x]=1;
    for(int i=g[x];~i;i=e[i].next)
        if(i^pe){
            if(!dfn[e[i].to]){
                tarjan(e[i].to,i^1);
                if(low[e[i].to]<low[x]) low[x]=low[e[i].to];
                if(low[e[i].to]>=dfn[x]){
                    numc++;
                    while(S.top()!=e[i].to){
                        c[S.top()][numc]=1;
                        instack[S.top()]=0;
                        d0[numc]++;
                        S.pop();
                    }
                    c[e[i].to][numc]=1;
                    instack[e[i].to]=0;
                    c[x][numc]=1;
                    d0[numc]+=2;
                    S.pop();
                }
            }else if(instack[e[i].to] && dfn[e[i].to]<low[x]) low[x]=dfn[e[i].to];
        }
}

LL getPow(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1) res=res*x%P;
        x=x*x%P;
        y>>=1;
    }
    return res;
}

int gcd(int x,int y){
    if(!y) return x;
    return gcd(y,x%y);
}

LL calc(int x){
    LL res=0;
    for(int i=0;i<x;i++)
        res=(res+getPow(C,gcd(i,x)))%P;
    res=res*getPow(x,P-2)%P;
    return res;
}

LL calc2(int x){
    return binom[C+x-1][C-1];
}

void init(){
    for(int i=0;i<MAXN;i++){
        binom[i][0]=1;
        for(int j=1;j<=i;j++)
            binom[i][j]=(binom[i-1][j-1]+binom[i-1][j])%P;
    }
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    init();
    memset(g,-1,sizeof g);
    scanf("%d%d%d",&n,&m,&C);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        addEdge(u,v);
        addEdge(v,u);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]){
            tarjan(i,-1);
            numc++;
            while(!S.empty()){
                c[S.top()][numc]=1;
                d0[numc]++;
                instack[S.top()]=0;
                S.pop();
            }
        }
    LL ans=1;
    for(int x=1;x<=n;x++)
        for(int i=g[x];~i;i=e[i].next)
            if(i&1){
                bool flag=0;
                for(int j=1;j<=numc;j++)
                    if(c[x][j] && c[e[i].to][j]){
                        d[j]++;
                        flag=1;
                        break;
                    }
                if(!flag) ans=ans*C%P;
            }
    for(int i=1;i<=numc;i++){
        if(d0[i]==1) continue;
        if(d[i]==d0[i]) ans=ans*calc(d0[i])%P;
        else if(d[i]==d0[i]-1) ans=ans*getPow(C,d[i])%P;
        else ans=ans*calc2(d[i])%P;
    }
    printf("%lld\n",ans);
}