官方数据100pts,民间数据 WA*8,求助
查看原帖
官方数据100pts,民间数据 WA*8,求助
637073
wujingfey楼主2023/11/3 15:51
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5,mod=1e9+7;
int n,m,idx=1,h[N];
int dfn[N],low[N],tot;
int dcc[N],cnt;
int pre[N<<2];
struct NODE{
	int to,nxt;
}e[N<<2];
stack<int> stk;
vector<int> ee[N];//新图 
int node[N],edge[N],sum[N];//一个边双内的点数和边数
int dp[N],ans;//u为根的子树内至少选1个点的方案数 
int qp(int x,int b){
	int res=1,base=x;
	while(b){
		if(b&1) res=(res*base)%mod;
		base=(base*base)%mod;
		b>>=1;
	}
	return res;
}
void add(int a,int b){
	e[++idx]={b,h[a]};
	h[a]=idx;
}
void tarjan(int u,int in_edg){
	dfn[u]=low[u]=++tot;
	stk.push(u);
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(dfn[v]==0){
			tarjan(v,i);
			low[u]=min(low[u],low[v]);
		}else if(i!=(in_edg^1)){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]){	
		++cnt;
		while(1){
			int v=stk.top();
			stk.pop();
			dcc[v]=cnt;
			if(v==u) break;
		}
	}
}
void dfs(int x,int fa){
    dp[x]=pre[node[x]+edge[x]]%mod;//f[x]初值
    sum[x]=edge[x];
    for(auto y:ee[x]){
        if(y==fa) continue;
        dfs(y,x);
        sum[x]+=sum[y]+1;
        dp[x]=dp[x]*((dp[y]+pre[sum[y]+1])%mod)%mod;
        //y对f[x]的贡献,f[y]为选取,p[sum[y]+1]为不选取
    }
    dp[x]=(dp[x]+mod-pre[sum[x]])%mod;//减去一个点都不选的方案数
    ans=(ans+dp[x]*pre[m-sum[x]-(fa!=0)]%mod)%mod;//统计总的方案数
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	tarjan(1,0);
	for(int u=1;u<=n;u++){//缩点 
		for(int i=h[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(dcc[u]!=dcc[v]) ee[dcc[u]].push_back(dcc[v]);
			if(dcc[u]==dcc[v]) edge[dcc[u]]++;
		}
		node[dcc[u]]++;
	}
	pre[0]=1;
	for(int i=1;i<=2*n;i++) pre[i]=pre[i-1]*2%mod;
	for(int i=1;i<=cnt;i++){
		edge[i]/=2;
	}
	dfs(1,0);
	cout<<ans%mod;
	return 0;
}
2023/11/3 15:51
加载中...