题目大意
给你一个\(n\)个点\(m\)条边的无向图（可能有重边），对于这个图的边集的子集（一共有\(2^m\)个），如果其导出的子图的每个联通块内都存在欧拉回路，我们就把答案加上这个子图的边数的平方，答案对\({10}^9+7\)取模。
\(n,m\leq 200000\)
题解
先求出这个图的DFS树。
记\(c\)为这个图的联通块个数。
通过观察发现，如果非树边任意选，那么确定非树边之后树边只有一种选择方案（从下往上做一遍树形DP可以得到方案）。
所以选择方案是\(2^{m-n+c}\)种。
但是这题要求的是边数的平方和。
假设当前删除了\(x\)条边，那么边数平方就是\({(m-x)}^2=m^2-2mx+x^2\)。
现在要求出删除一条边/两条边后的方案数（就是联通块个数）。
第一项很好计算，就是方案数\(\times m^2\)。
第二项很好计算，如果一条边是桥，那么\(c++\)，否则不变。
第三项不那么好计算。如果两条边都是桥，那么\(c+=2\)。如果一条边是桥但另一条边不是，那么\(c++\)。否则（两条边不是桥），有可能是\(c++\)，有可能\(c\)不变。
那么什么时候\(c\)会\(+1\)呢？可以用DZY Loves Chinese II这道题的方法，给每条非树边赋一个随机权值，每条树边的权值就是跨过这条树边的其他非树边的权值的异或和。
这样，删除两条非桥边会产生新的联通块当且仅当着两条边的权值相同。
那错误概率又是多少呢？
考虑这两条边的异或和是由哪些边组成的。异或和为\(0\)当且仅当每一位为\(0\)。每一位为\(0\)当且仅当这些边的这一位有偶数个\(1\)，这个概率是\(\frac 12\)。那么\(64\)位全部错误的概率是\(2^{-64}\)，正确的概率是\(1-2^{-64}\)。
然后直接把这些边按权值排序，每种权值统计一下就做完了。
时间复杂度：\(O(n+m)\)
什么？你说排序？有一种东西叫挑战排序，这种排序是\(O(m)\)的。（我没写）
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
const ll p=1000000007;
ll pw[200010];
struct graph
{
int v[400010];
int w[400010];
int t[400010];
int h[200010];
int n;
int b[400010];
void add(int x,int y,int z)
{
n++;
v[n]=y;
w[n]=z;
t[n]=h[x];
h[x]=n;
}
};
graph g;
int f[200010];
ll v[200010];
int b[200010];
int d[200010];
int lx[200010];
int ly[200010];
ll c[200010];
int shu[200010];
void dfs(int x,int fa,int dep)
{
f[x]=fa;
d[x]=dep;
b[x]=1;
int i;
for(i=g.h[x];i;i=g.t[i])
if(!b[g.v[i]])
{
dfs(g.v[i],x,dep+1);
shu[g.w[i]]=1;
g.b[i]=1;
}
}
void dfs(int x)
{
int i;
for(i=g.h[x];i;i=g.t[i])
if(g.b[i])
{
dfs(g.v[i]);
c[g.w[i]]=v[g.v[i]];
v[x]^=v[g.v[i]];
}
}
int n,m;
ll a[200010];
int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
srand(time(0));
scanf("%d%d",&n,&m);
int i,x,y;
pw[0]=1;
for(i=1;i<=m;i++)
pw[i]=pw[i-1]*2%p;
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
g.add(x,y,i);
g.add(y,x,i);
lx[i]=x;
ly[i]=y;
}
int cnt=0;
ll ans;
for(i=1;i<=n;i++)
if(!b[i])
{
dfs(i,0,1);
cnt++;
}
for(i=1;i<=m;i++)
if(!shu[i])
{
ll val=(ll)rand()*RAND_MAX+rand();
v[lx[i]]^=val;
v[ly[i]]^=val;
c[i]=val;
}
for(i=1;i<=n;i++)
if(!f[i])
dfs(i);
ans=(ll)m*m%p*pw[m-n+cnt]%p;
ll s=0;
int bcnt=0;
int t=0;
for(i=1;i<=m;i++)
if(c[i])
{
s=(s+pw[m-n+cnt-1])%p;
a[++t]=c[i];
}
else
{
s=(s+pw[m-n+cnt])%p;
bcnt++;
}
sort(a+1,a+t+1);
ans=(ans-2*m*s)%p;
ans=(ans+pw[m-n+cnt]*((ll)bcnt*bcnt%p))%p;
ans=(ans+pw[m-n+cnt-1]*2%p*bcnt%p*t)%p;
s=0;
int tot=0;
for(i=1;i<=t;i++)
if(i==1||a[i]!=a[i-1])
{
s=(s+(ll)tot*tot)%p;
tot=1;
}
else
tot++;
s=(s+(ll)tot*tot)%p;
ans=(ans+pw[m-n+cnt-1]*s)%p;
if(m-n+cnt>=2)
ans=(ans+pw[m-n+cnt-2]*(((ll)t*t-s)%p))%p;
ans=(ans+p)%p;
printf("%lld\n",ans);
return 0;
}