【Baekjoon19394】Eulerian Orientation
选中边不好做，考虑删除边，一个删除 \(x\) 条边的图的权值是 \((m-x)^2\)，令 \(k\) 个合法图分别删除 \(x_1,x_2,...,x_k\)，答案就是 \(\sum_{i=1}^k (m-x_i)^2=km^2-2m\sum_{i=1}^k x_i+\sum_{i=1}^k x_i^2\)。
对于第一项，只需要求出合法图的个数。任意取出图的一个生成森林，如果将一条非树边 \((u,v)\) 选中，树上 \(u,v\) 两点间路径上的边的选中状态会翻转，即非树边任意选，树边由非树边选择方案唯一确定，易得 \(k=2^{m-n+cnt}\)。
对于第二项，考虑 \(\sum x_i\) 的组合意义，即对于每个合法的删除方案，选一条被删除的边的方案数之和。枚举选中的这条边是什么，求出钦定它删除后有多少种删除方案。如果选中割边，则 \(cnt\) 减少 \(1\)，否则 \(cnt\) 不变。
对于第三项，同样的套路，钦定两条边删除。如果都是割边，则 \(cnt\) 增加 \(2\)；如果一条割边一条非割边，则 \(cnt\) 增加 \(1\)；如果两条非割边，则 \(cnt\) 增加 \(0\) 或 \(1\)。前两种情况很简单，如果能求出删掉两条边使得图不连通的方案数，问题即可解决。
在图中随便找一棵生成森林。对于非树边赋一个随机权值，令一条树边的权值为覆盖它的非树边权值的异或和，则删除一个边集后图不连通在很大概率下当且仅当这个边集存在一个子集的异或和为 \(0\)，用这个方法去找出权值一样的树边即可，复杂度 \(O(n)\) 或 \(O(n \log n)\)，瓶颈在排序。
Code
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int fpow(int x,int b){
if(x==0) return 0;
if(b==0) return 1;
int res=1;
while(b>0){
if(b&1) res=res*x%mod;
x=x*x%mod;
b>>=1;
}
return res;
}
int n,m;
vector <pii > g[200005],t[200005];
mt19937_64 rnd(time(0));
int U[200005],V[200005],tp[200005];
ull We[200005],Wv[200005];
// 0: out tree, 1: in tree
bool vis[200005];
void dfs0(int u)
{
vis[u]=1;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i].fi;
if(vis[v]) continue;
tp[g[u][i].se]=1;
t[u].pb(mp(v,g[u][i].se)),t[v].pb(mp(u,g[u][i].se));
dfs0(v);
}
}
int cntB;
vector <ull> vec;
map <ull,int> ma;
int notB;
void dfs1(int u,int isrt)
{
vis[u]=1;
for(int i=0;i<t[u].size();i++)
{
int v=t[u][i].fi;
if(vis[v]) continue;
dfs1(v,0);
Wv[u]^=Wv[v];
}
if(!isrt)
{
if(!Wv[u]) cntB++;
else vec.pb(Wv[u]);
}
}
void solve()
{
for(int i=1;i<=n;i++) g[i].clear(),t[i].clear(),Wv[i]=0;
vec.clear();
cntB=notB=0;
for(int i=1;i<=m;i++) scanf("%lld%lld",&U[i],&V[i]),g[U[i]].pb(mp(V[i],i)),g[V[i]].pb(mp(U[i],i)),tp[i]=We[i]=Wv[i]=0;
int c=0;
for(int i=1;i<=n;i++) vis[i]=0;
for(int i=1;i<=n;i++) if(!vis[i]) dfs0(i),c++;
for(int i=1;i<=m;i++) if(!tp[i]) We[i]=rnd(),Wv[U[i]]^=We[i],Wv[V[i]]^=We[i],vec.pb(We[i]);
for(int i=1;i<=n;i++) vis[i]=0;
for(int i=1;i<=n;i++) if(!vis[i]) dfs1(i,1);
sort(vec.begin(),vec.end());
for(int i=0;i<vec.size();i++)
{
int j=i;
while(j<vec.size()&&vec[j]==vec[i]) j++;
j--;
notB+=1LL*(j-i+1)*(j-i+1);
i=j;
}
int ans=fpow(2,m-n+c)*m%mod*m%mod;
// cout<<ans<<endl;
ans=(ans-2LL*m%mod*cntB%mod*fpow(2,m-1-n+c+1)%mod+mod)%mod;
ans=(ans-2LL*m%mod*(m-cntB)%mod*fpow(2,m-1-n+c)%mod+mod)%mod;
// cout<<ans<<endl;
ans=(ans+cntB*cntB%mod*fpow(2,m-2-n+c+2)%mod)%mod;
ans=(ans+2LL*cntB*(m-cntB)%mod*fpow(2,m-2-n+c+1)%mod)%mod;
ans=(ans+notB%mod*fpow(2,m-2-n+c+1)%mod)%mod;
// cout<<ans<<endl;
int cnt=m*m-cntB*cntB-2LL*cntB*(m-cntB)-notB;
// cout<<m<<" "<<n<<" "<<c<<" "<<m-n+c<<" "<<cnt<<" "<<cntB<<" "<<notB<<endl;
ans=(ans+cnt%mod*fpow(2,m-2-n+c)%mod)%mod;
printf("%lld\n",ans);
}
signed main()
{
int _=1;
// cin>>_;
while(cin>>n>>m) solve();
return 0;
}