2018.10.25 uoj#308. 【UNR #2】UOJ拯救计划（排列组合）

传送门 有一个显然的式子：$Ans=\sum A(n,i)\ast 用i种颜色的方案数$ 这个东西貌似是个$NPC$。 于是需要仔细观察数据范围。 咦模数等于$6$？ 那么对于$A(n,i)$在$i\ge 3$的时候模$6$都是$0$了。 因此只用讨论$i=1$和$i=2$的方案数。 什么？ $i=1?$ 没错，题目上并没有说过$m!=0$啊。 还有就是貌似边数跟题目描述不太一样。 代码：

#include<bits/stdc++.h> using namespace std; inline int read(){ int ans=0; char ch=getchar(); while(!isdigit(ch))ch=getchar(); while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar(); return ans; } const int N=1e5+5,M=2e6+5,mod=6; int T,n,m,K,first[N],cnt=0,tot=0,fa[N],col[N],ans; struct edge{int v,next;}e[M<<1]; inline void addedge(int u,int v){e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt;} inline void add(int u,int v){addedge(u,v),addedge(v,u);} inline bool dfs(int p,int f){ col[p]=f; for(int i=first[p];i;i=e[i].next){ int v=e[i].v; if(~col[v]){if(!(col[v]^f))return false;} else if(!dfs(v,f^1))return false; } return true; } inline int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);} int main(){ T=read(); while(T--){ n=read(),m=read(),K=read(); if(!m){ ans=1; for(int i=1;i<n;++i){ ans<<=1; if(ans>=mod)ans-=mod; } --ans; if(ans<0)ans+=mod; ans=ans*K%mod*(K-1)%mod; ans+=K%mod; if(ans>=mod)ans-=mod; } else{ cnt=0,tot=0,ans=1; for(int i=1;i<=n;++i)first[i]=0,fa[i]=i,col[i]=-1; for(int i=1,u,v,fx,fy;i<=m;++i){ u=read(),v=read(),add(u,v),add(v,u),fx=find(u),fy=find(v); if(fx!=fy)fa[fx]=fy; } for(int i=1,f;i<=n;++i) if(~col[i])continue; else{ if(!dfs(i,0)){ans=0;break;} ++tot; } if(ans){ for(int i=1;i<tot;++i){ ans<<=1; if(ans>=mod)ans-=mod; } ans=ans*K%mod*(K-1)%mod; } } printf("%d\n",ans); } return 0; }