题目
描述
一个(n)个点(m)条边的无向图，求其(k)染色的方案数；
染色的方案必须满足对于任意一条边((u,v))，(u)和(v)不同色；
答案对(10^9+7)取模；
范围
(n le 10^5 , m le n + 5 , 3 le kle 10^5)
题解
-
题解说正常的染色问题是(NPC)问题，这题可以通过缩点来做；
-
将图重新定义为有边权((a,b))的图，(a)表示两边同色的边权，(b)表示两边不同色的边权；
-
如果让初始时((a,b)=(0,1)),那么答案就是每种染色之后所有边权乘积 之和；
-
考虑去掉一些可以直接计算答案的点(u)：
- 度数为(0)的点：
- 去掉之后将答案乘以(k);
- 度数为(1)的点((u,v))，考虑去掉(u)：
- 有(k-1)种情况(u,v)同色，(1)种情况(u,v)异色，所以去掉(u)之后答案乘上(a+(k-1)b);
- 度数为(2)的点((u,v_1),(u,v_2))，考虑去掉(u)，加入新边((v_1,v_2))：
- 若(v1,v2)同色，有(k-1)种情况(u)和(v1,v2)均不同色，(1)种情况(u)和(v1,v2)均同色；
- 新边的(a)即：$a = a_{1}a_{2} + (k-1)b_{1}b_{2} $
- 若(v1,v2)不同色，有(k-2)种情况(u)和(v1,v2)不同色，(1)种情况(u)仅和(v1)同色，(1)种情况(u)仅(和)(v1)同色；
- 新边的(b)即：$b = a_{1}b_{2} + a_{2}b_{1} + (k-2)b_1a_1 $
- 若(v1,v2)同色，有(k-1)种情况(u)和(v1,v2)均不同色，(1)种情况(u)和(v1,v2)均同色；
- 在缩图的过程重回产生重边，合并两条重边：
- ((a,b) = (a_1*a_2 ,b_1b_2 ))
- 度数为(0)的点：
-
考虑缩点之后的图不存在度数小于3的节点：
-
[egin{cases} 2m ge 3n \ m le n + 5 \ end{cases} ]
-
-
可以解得(n le 10 , m le 15);
-
然后(Bell(n)m)枚举划分统计答案即可；
#include<bits/stdc++.h> #define ll long long #define il inline using namespace std; const int N=200010,mod=1e9+7; int n,m,k,iv[N],fac[N],inv[N],hd[N],o,a[N],b[N],d[N],del[N<<1],vis[N],cnt,U[N],V[N],iE[N],iD[N],bl[N],ans1=1,ans2=0; struct Edge{int v,nt;}E[N<<1]; queue<int>q; il char gc(){ static char*p1,*p2,s[1000000]; if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin); return(p1==p2)?EOF:*p1++; } il int rd(){ int x=0;char c=gc(); while(c<'0'||c>'9')c=gc(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc(); return x; } il void adde(int u,int v){ d[u]++;d[v]++; E[o]=(Edge){v,hd[u]};hd[u]=o++; E[o]=(Edge){u,hd[v]};hd[v]=o++; } const int sz=12345671; struct HASH{ int o,hd[sz],nt[N]; ll val[N]; il void init(int i,int u,int v){ if(u>v)swap(u,v); ll x=(ll)u*(n+1)+v; nt[++o]=hd[x%sz],hd[x%sz]=o,val[o]=x; adde(u,v);a[i]=0,b[i]=1; } il int find(int u,int v){ if(u>v)swap(u,v); ll x=(ll)u*(n+1)+v; for(int i=hd[x%sz];i;i=nt[i])if(val[i]==x){return i;} nt[++o]=hd[x%sz],hd[x%sz]=o,val[o]=x; adde(u,v);a[++m]=1,b[m]=1; return m; } }H; il void merge(int u){ if(!~d[u])return; vis[u]=0; if(!d[u]){ d[u]=-1; ans1=(ll)ans1*k%mod; }else if(d[u]==1){ int v=0; for(int i=hd[u];~i;i=E[i].nt){ if(del[i])continue; del[i]=del[i^1]=1; v=E[i].v; break; } int t=H.find(u,v); ans1=(ll)ans1*(a[t]+(ll)b[t]*(k-1)%mod)%mod; d[u]=-1;--d[v]; if(d[v]<=2&&!vis[v]){vis[v]=1;q.push(v);} }else{ int v1=0,v2=0; for(int i=hd[u];~i;i=E[i].nt){ if(del[i])continue; del[i]=del[i^1]=1; if(!v1){v1=E[i].v;continue;} v2=E[i].v;break; } int t=H.find(v1,v2),t1=H.find(u,v1),t2=H.find(u,v2); a[t]=(ll)a[t] * ((ll)(k-1)*b[t1]%mod*b[t2]%mod + (ll)a[t1]*a[t2]%mod)%mod; b[t]=(ll)b[t] * ((ll)(k-2)*b[t1]%mod*b[t2]%mod + (ll)a[t1]*b[t2]%mod + (ll)b[t1]*a[t2]%mod)%mod; d[u]=-1;--d[v1];--d[v2]; if(d[v1]<=2&&!vis[v1]){vis[v1]=1;q.push(v1);} if(d[v2]<=2&&!vis[v2]){vis[v2]=1;q.push(v2);} } } il void cal(int y){ int re=1; for(int i=1;i<=m;++i){ if(bl[U[i]]==bl[V[i]])re=(ll)re*a[iE[i]]%mod; else re=(ll)re*b[iE[i]]%mod; } re=(ll)re*fac[k]%mod*inv[k-y]%mod; ans2=(ans2+re)%mod; } void dfs(int x,int y){ if(y>k)return; if(x==n+1){cal(y);return;} for(int i=1;i<=y+1;++i){ bl[x]=i; dfs(x+1,max(i,y)); } } int main(){ freopen("color.in","r",stdin); freopen("color.out","w",stdout); n=rd();m=rd();k=rd(); for(int i=1;i<=n;++i)hd[i]=-1; iv[1]=1;for(int i=2;i<=k;++i)iv[i]=(ll)(mod-mod/i)*iv[mod%i]%mod; for(int i=fac[0]=inv[0]=1;i<=k;++i){ fac[i]=(ll)fac[i-1]*i%mod; inv[i]=(ll)inv[i-1]*iv[i]%mod; } for(int i=1;i<=m;++i){ int u=rd(),v=rd(); H.init(i,u,v); H.find(u,v); } for(int i=1;i<=n;++i)if(d[i]<=2)q.push(i),vis[i]=1; while(!q.empty()) merge(q.front()),q.pop(); int tmp=0;for(int i=1;i<=n;++i)if(~d[i])iD[i]=++tmp; n=tmp;tmp=0; for(int i=1;i<=m;++i)if(!del[(i-1)<<1]){ int u=E[(i-1)<<1].v,v=E[(i-1)<<1|1].v; ++tmp;u=iD[u];v=iD[v]; U[tmp]=u;V[tmp]=v;iE[tmp]=i; } m=tmp;dfs(1,0); cout<<(ll)ans1*ans2%mod<<endl; return 0; }