题解 AT2143 【[ARC062D] AtCoDeerくんとグラフ色塗り / Painting Graphs with AtCoDeer】

whiteqwq · 2021-01-16 13:48:30 · 题解

AT2143 [ARC062D] AtCoDeerくんとグラフ色塗り / Painting Graphs with AtCoDeer解题报告：

更好的阅读体验

题意

• 给定一个无向图，给它的边用k种颜色染色，定义一种操作为将一个环的颜色循环移位，定义两种染色方案相同当且仅当一种方案可以通过另一种方案操作得到，求本质不同染色方案数，对10^9+7取模。
• 数据范围：1\leqslant n\leqslant 50,1\leqslant m\leqslant 100,1\leqslant k\leqslant 100。

分析

比较好玩的一道题。

首先，我们可以利用一种神奇的边双联通分量求法（注意，这里求的边双联通分量是指不存在割点的连通分量）把整个图分成若干个边集，然后分类讨论：

void tarjan(int x,int last){
    dfn[x]=low[x]=++cnt;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        if(dfn[y]==0){
            stk[++top][0]=x,stk[top][1]=y;
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<=low[y]){
                int a=0,b=0;
                tot++;
                while(a!=x||b!=y){
                    a=stk[top][0],b=stk[top][1],top--;
                    sumg[tot]++,sump[tot]+=(bel[a]!=tot)+(bel[b]!=tot);
                    bel[a]=bel[b]=tot;
                }
            }
        }
        else if(dfn[y]<dfn[x]){
            stk[++top][0]=x,stk[top][1]=y;
            low[x]=min(low[x],dfn[y]);
        }
    }
}

• 对于单独的一条边，它可以染k种颜色；
• 对于一个环（即点数等于边数），它染色方案数可以直接用burnside引理来求： ans=\frac{1}{|G|}\sum_{g\in G}|X^g|=\frac{1}{n}\sum_{i=1}^n k^{\gcd(i,n)}

  （k^{gcd(i,n)}的意思就是指前\gcd(i,n)个可以随意染色，后面的直接按顺序填下去就好了）。

• 对于一个点数不等于边数的边双联通分量，我们可以证明如果两个染色方案的用的颜色及颜色的数量，那么它们一定可以通过操作互相得到，因此方案数等于m个球放入k个盒子（可空）的方案数，插板法得到答案是{m+k-1\choose m}。

证明： 首先很显然一个点数不等于边数的边双联通分量一定存在一个\geqslant 3度点。

然后我们可以证明一个\geqslant 3度点可以互换任意两条边： 因为这个\geqslant 3度点的第二条边会把大环分成两个小环，因此我们对于两个小环和一个大环进行下列操作：

第一次正操作第一个小环可以让前两条边转到小环上。

第二次正操作第二个小环可以让第三条边转到原来第二条边的位置。

第三次逆操作大环便可以把三条边转回来。

此时后两条边已经交换，且不难看出整个边双联通分量里的所有边只有这两条边移动了位置。

然后我们可以发现可以通过若干个环把任意两个点移动到一个\geqslant 3度点上，经过上面的操作交换两条边，又可以通过移过来时操作的逆操作把这两条边交换回去，这样我们就成功在不改变其他边的位置的情况下交换了两条边，这样就证明了上面的结论。

时间复杂度：O(n\log n)。

当然，如果你跟我一样无聊的话，可以把上面的式子化一下：\frac{1}{n}\sum_{i=1}^n k^{\gcd(i,n)}=\frac{1}{n}\sum_{d=1}^n\sum_{i=1}^n k^d[\gcd(i,n)=d]=\frac{1}{n}\sum_{d=1}^n[d\mid n]k^d\sum_{i=1}^{\frac{n}{d}}[\gcd(i,\frac{n}{d})=1]=\frac{1}{n}\sum_{d=1}^n [d\mid n]k^d\times\varphi(\frac{n}{d})，然后直接累乘做到O(n)。

注意要带上[d\mid n]，否则答案会多算一部分贡献（我就因为这调了半个小时）。

时间复杂度：O(n)。

代码

#include<stdio.h>
const int maxn=1005,mod=1000000007,maxx=1000;
int n,m,k,e,cnt,top,tot,prms,ans;
int start[maxn],from[maxn],to[maxn],then[maxn],dfn[maxn],low[maxn],stk[maxn][2],deg[maxn],sump[maxn],sumg[maxn],bel[maxn];
int phi[maxn],a[maxn],p[maxn],fac[maxn],nfac[maxn];
inline int min(int a,int b){
    return a<b? a:b;
}
inline void add(int x,int y){
    then[++e]=start[x],start[x]=e,from[e]=x,to[e]=y;
}
void tarjan(int x,int last){
    dfn[x]=low[x]=++cnt;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        if(dfn[y]==0){
            stk[++top][0]=x,stk[top][1]=y;
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<=low[y]){
                int a=0,b=0;
                tot++;
                while(a!=x||b!=y){
                    a=stk[top][0],b=stk[top][1],top--;
                    sumg[tot]++,sump[tot]+=(bel[a]!=tot)+(bel[b]!=tot);
                    bel[a]=bel[b]=tot;
                }
            }
        }
        else if(dfn[y]<dfn[x]){
            stk[++top][0]=x,stk[top][1]=y;
            low[x]=min(low[x],dfn[y]);
        }
    }
}
void sieve(int k){
    p[1]=phi[1]=1;
    for(int i=2;i<=k;i++){
        if(p[i]==0)
            a[++prms]=i,phi[i]=i-1;
        for(int j=1;j<=prms;j++){
            if(i*a[j]>k)
                break;
            p[i*a[j]]=1;
            if(i%a[j]==0){
                phi[i*a[j]]=phi[i]*a[j];
                break;
            }
            phi[i*a[j]]=phi[i]*(a[j]-1);
        }
    }
}
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1)
            res=1ll*res*a%mod;
        a=1ll*a*a%mod,b>>=1;
    }
    return res;
}
int calc(int n){
    int res=0,mul=1;
    for(int i=1;i<=n;i++){
        mul=1ll*mul*k%mod;
        if(n%i==0)
            res=(res+1ll*mul*phi[n/i]%mod)%mod;
    }
    return 1ll*res*ksm(n,mod-2)%mod;
}
inline int c(int n,int m){
    return n<m? 0:1ll*fac[n]*nfac[m]%mod*nfac[n-m]%mod;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    sieve(maxx);
    fac[0]=1;
    for(int i=1;i<=maxx;i++)
        fac[i]=1ll*fac[i-1]*i%mod;
    nfac[maxx]=ksm(fac[maxx],mod-2);
    for(int i=maxx;i>=1;i--)
        nfac[i-1]=1ll*nfac[i]*i%mod;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    for(int i=1;i<=n;i++)
        if(dfn[i]==0){
            top=0;
            tarjan(i,0);
        } 
    ans=1;
    for(int i=1;i<=tot;i++){
        if(sump[i]==1)
            ans=1ll*ans*k%mod;
        else if(sump[i]==sumg[i])
            ans=1ll*ans*calc(sump[i])%mod;
        else ans=1ll*ans*c(sumg[i]+k-1,sumg[i])%mod;
    }
    printf("%d\n",ans);
    return 0;
}