題意：一個無向圖，用$k$種不同的顏色給每條邊染色，問能染出多少種不同的圖，如果兩張圖能通過循環移位環邊使得顏色相同，那么這兩張圖被認為是相同的

數學太差傷不起啊...補了一下Burnside定理的證明，這里寫一些類似筆記的東西...

置換$\left(\begin{matrix}1\cdots n\\i_1\cdots i_n\end{matrix}\right)$有合成運算$\circ$，滿足結合律，有單位元$\iota$，存在唯一逆元滿足$f\circ f^{-1}=\iota$，所有$n!$個置換構成集合$S_n$

如果$G\subseteq S_n$且滿足以下三條性質，定義它為置換群

1.$\forall f,g\in G,f\circ g\in G$

2.$\iota\in G$

3.$\forall f\in G,f^{-1}\in G$

每一個置換群都滿足消去律$f\circ g=f\circ h\Rightarrow g=h$

$\rho_n=\left(\begin{matrix}1&\cdots&n-1&n\\2&\cdots&n&1\end{matrix}\right)$，易證$C_n=\{\rho_n^i|1\leq i\leq n\}$是一個置換群

著色$\mathbf c$：$i$的顏色為$c(i)$，著色集合$\mathcal C$

定義$f*\mathbf c$為使$i_k$的顏色為$c(k)$的著色（就是把顏色沿著置換移動）

$\forall f\in G,\mathbf c\in\mathcal C,f*\mathbf c\in\mathcal C$

$(g\circ f)*\mathbf c=g*(f*\mathbf c)$

若$\mathbf c_1,\mathbf c_2\in\mathcal C$，$\exists f\in G$使$f*\mathbf c_1=\mathbf c_2$，稱$\mathbf c_1$等價于$\mathbf c_2$，記作$\mathbf c_1\sim\mathbf c_2$，這是$\mathcal C$上的等價關系

$\mathbf c$的穩定核$G(\mathbf c)=\{f|f\in G,f*\mathbf c=\mathbf c\}$是置換群

$\mathcal C(f)=\{\mathbf c|\mathbf c\in\mathcal C,f*\mathbf c=\mathbf c\}$

快要證Burnside定理了，先做一些準備工作

1.$\forall f,g\in G,f*\mathbf c=g*\mathbf c\Leftrightarrow f^{-1}\circ g\in G(\mathbf c)$

正：$(f^{-1}\circ g)*\mathbf c=f^{-1}*(g*\mathbf c)=f^{-1}*(f*\mathbf c)=\mathbf c\Rightarrow f^{-1}\circ g\in G(\mathbf c)$

反：$\mathbf c=(f^{-1}\circ g)*\mathbf c=f^{-1}*(g*\mathbf c)\Rightarrow f*\mathbf c=g*\mathbf c$

2.與$\mathbf c$等價的著色數$\left|\{f*\mathbf c|f\in G\}\right|=\dfrac{|G|}{|G(\mathbf c)|}$

由1得$f*\mathbf c=g*\mathbf c\Rightarrow g\in\{{f\circ h}|h\in G(\mathbf c)\}$，由消去律得$f\circ h=f\circ h'\Rightarrow h=h'$，所以對每個$f$恰有$|G(\mathbf c)|$個滿足要求的$g$，得證

現在來證Burnside定理：非等價著色數$N(G,\mathcal C)=\dfrac1{|G|}\sum\limits_{f\in G}|\mathcal C(f)|$

先用兩種方式計數滿足$f*\mathbf c=\mathbf c$的$(f,\mathbf c)$的對數

$\sum\limits_{f\in G}|\mathcal C(f)|=\sum\limits_{\mathbf c\in\mathcal C}|G(\mathbf c)|$

由2得$\sum\limits_{\mathbf c\in\mathcal C}|G(\mathbf c)|=|G|\sum\limits_{\mathbf c\in\mathcal C}\dfrac1{(與\mathbf c等價的著色數)}$

右邊的sigma中，每個等價類都貢獻$1$，所以它等于$N(G,\mathcal C)$，定理得證

在此題中，如果一個點雙只含一個環，就要用Burnside定理計數方案

設它有$n$條邊，這題的循環移位對應置換群$C_n$

$|\mathcal C(\rho_n^i)|=k^{(n,i)}$，這是因為如果$\rho_n^i*\mathbf c=\mathbf c$那么$c(p)=c(p+i)$，這個限制把$n$條邊分成了互相獨立的$(n,i)$組，每組必須同色

所以方案數是$\dfrac1n\sum\limits_{i=1}^nk^{(i,n)}$

如果一個點雙含多個環，那么我們有辦法交換任意兩邊

題解上的這張圖告訴我們，一個度數$\geq3$的點的兩條出邊可以被交換（圖中的綠和藍）

然后我們可以交換任意相鄰邊，先把它們轉到度數$\geq3$的點，做如上變換，再轉回去即可

然后我們可以交換任意兩邊，用至多兩次操作我們可以使它們相鄰，交換后倒著操作回去即可

所以這樣的點雙方案數只與顏色數有關，$n$條邊的點雙答案為$\binom{n+k-1}{k-1}$

不屬于任何點雙的邊對答案的貢獻就是$k$了

#include<stdio.h> #include<vector> #include<set> using namespace std; typedef long long ll; const int mod=1000000007; int mul(int a,int b){return a*(ll)b%mod;} void inc(int&a,int b){(a+=b)%=mod;} int pow(int a,int b){int s=1;while(b){if(b&1)s=mul(s,a);a=mul(a,a);b>>=1;}return s; } vector<int>g[60]; int fac[210],rfac[210],k; int C(int n,int k){return mul(fac[n],mul(rfac[k],rfac[n-k]));} int dfn[60],low[60],stk[60],tp,M,ans; set<int>s; int gcd(int a,int b){return a%b==0?b:gcd(b,a%b);} int burnside(int n){int i,s=0;for(i=1;i<=n;i++)inc(s,pow(k,gcd(i,n)));return mul(s,pow(n,mod-2)); } void dfs(int x){int t,n,m;dfn[x]=low[x]=++M;stk[++tp]=x;for(int y:g[x]){if(!dfn[y]){dfs(y);low[x]=min(low[x],low[y]);if(low[y]>=dfn[x]){s.clear();do{t=stk[tp--];s.insert(t);}while(t!=y);s.insert(x);n=s.size();m=0;for(int x:s){for(int y:g[x]){if(s.count(y))m++;}}m>>=1;if(m<n)ans=mul(ans,k);if(n==m)ans=mul(ans,burnside(m));if(n<m)ans=mul(ans,C(m+k-1,k-1));}}elselow[x]=min(low[x],dfn[y]);} } int main(){int n,m,i,x,y;scanf("%d%d%d",&n,&m,&k);for(i=1;i<=m;i++){scanf("%d%d",&x,&y);g[x].push_back(y);g[y].push_back(x);}fac[0]=1;for(i=1;i<=m+k;i++)fac[i]=mul(fac[i-1],i);rfac[m+k]=pow(fac[m+k],mod-2);for(i=m+k;i>0;i--)rfac[i-1]=mul(rfac[i],i);ans=1;for(i=1;i<=n;i++){if(!dfn[i])dfs(i);}printf("%d",ans); }

轉載于:https://www.cnblogs.com/jefflyy/p/9470630.html

總結

以上是生活随笔為你收集整理的[ARC062F]Painting Graphs with AtCoDeer的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。