WA 10pts 求助
查看原帖
WA 10pts 求助
363036
chlchl楼主2024/7/20 19:05

rt,请大佬帮忙康康,谢了!

#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

const int N = 1e6 + 10;
const int M = 1e6 + 10;
const ll P = 1e9 + 7;
int n, m, eu[M], ev[M];
int id, head[M << 1], nxt[M << 1], to[M << 1];
int clk, cnt, dfn[N], low[N], bel[N];
ll ans, num[N], edg[N], sume[N], f[N][2];
stack<int> st;
vector<int> g[N];

ll exp(ll a, ll b){
	ll cnt = 1;
	while(b){
		if(b & 1)
			(cnt *= a) %= P;
		(a *= a) %= P, b >>= 1;
	}
	return cnt;
}

void add(int u, int v){
	to[++id] = v;
	nxt[id] = head[u], head[u] = id;
}

void tarjan(int u, int fa){
	dfn[u] = low[u] = ++clk;
	st.push(u);
	for(int i=head[u];i;i=nxt[i]){
		int v = to[i];
		if(v == fa)
			continue;
		if(!dfn[v]){
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
		}
		else
			low[u] = min(low[u], dfn[v]);
	}
	if(low[u] == dfn[u]){
		++cnt;
		int v;
		do{
			v = st.top();
			st.pop();
			bel[v] = cnt, ++num[cnt];
		}while(v != u);
	}
}

void dfs(int u, int fa){
	sume[u] = edg[u];
	for(int v: g[u]){
		if(v == fa)
			continue;
		dfs(v, u);
		sume[u] += sume[v] + 1ll;
	}
}

void dp(int u, int fa){
	for(int v: g[u]){
		if(v == fa)
			continue;
		dp(v, u);
		(f[u][1] *= (f[u][0] * f[v][1] % P + (f[u][1] * (2ll * f[v][0] % P + f[v][1]) % P) % P) % P) %= P;
		(f[u][0] *= (2ll * f[v][0]) % P) %= P;
	}
	if(u == 1)
		(ans += f[u][1]) %= P;
	else
		(ans += f[u][1] * exp(2ll, sume[1] - sume[u] - 1ll) % P) %= P;
}

main(){
	scanf("%lld%lld", &n, &m);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld", &eu[i], &ev[i]);
		add(eu[i], ev[i]), add(ev[i], eu[i]);
	}
	tarjan(1, 1);
	for(int i=1;i<=m;i++){
		if(bel[eu[i]] != bel[ev[i]])
			g[bel[eu[i]]].push_back(bel[ev[i]]), g[bel[ev[i]]].push_back(bel[eu[i]]);
		else
			edg[bel[eu[i]]]++;
	}
	for(int u=1;u<=cnt;u++){
		f[u][0] = exp(2ll, edg[u]);//u 内的每条边可以选或不选 
		f[u][1] = ((exp(2ll, edg[u] + num[u]) - f[u][0]) % P + P) % P;
		//u 内的每条边、每个点都可以选或不选,但要减去一个点都没有选的情况 
	}
	dfs(1, 1);
	dp(1, 1);
	printf("%lld\n", (ans + P) % P);
	return 0;
}
2024/7/20 19:05
加载中...