抽象的情况出现了呢
查看原帖
抽象的情况出现了呢
186068
我怂了楼主2023/10/11 19:59

同志们下列代码下发样例4通过不了,但是AC了

什么情况qwq

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5e5+5,maxm=1e6+5,p=1e9+7;
int ksm(int x,int y){
	int r=1;
	while(y){
		if(y&1){
			r=r*x%p;
		}
		x=x*x%p;
		y>>=1;
	}
	return r;
}
struct linestar{
	signed cnt=0,head[maxm<<1],to[maxm<<1],last[maxn];
	void add(int x,int y){
		head[++cnt]=last[x];
		last[x]=cnt;
		to[cnt]=y;
	}
}edg;
int n,m,root;
struct tarjan{
	signed cnt,tot,low[maxn],dfn[maxn],note[maxn],E[maxn],U[maxn],s[maxn];
	bool ins[maxn];
	stack<int> st;
	vector<signed> v[maxn];
	int dp[maxn][2];
	void dfs(int x,int fa){
		low[x]=dfn[x]=++tot;
		st.push(x);
		ins[x]=true;
		for(int i=edg.last[x];i;i=edg.head[i]){
			int to=edg.to[i];
			if(to==fa){
				continue;
			}
			if(!dfn[to]){
				dfs(to,x);
				low[x]=min(low[x],low[to]);
			}
			else if(ins[to]){
				low[x]=min(low[x],dfn[to]);
			}
		}
		if(low[x]==dfn[x]){
			cnt++;
			int i;
			do{
				i=st.top();
				ins[i]=false;
				note[i]=cnt;
				E[cnt]++;
				st.pop();
			}while(x^i);
		}
	}
	void check(){
		for(int i=1;i<=n;i++){
			for(int j=edg.last[i];j;j=edg.head[j]){
				int to=edg.to[j];
				if(note[to]^note[i]){
					v[note[i]].push_back(note[to]);
				}
				else{
					U[note[i]]++;
				}
			}
		}
		for(int i=1;i<=cnt;i++){
			U[i]>>=1;
			dp[i][0]=ksm(2,U[i]);
			dp[i][1]=(ksm(2,U[i]+E[i])-dp[i][0])%p+p;
			dp[i][1]%=p;
		}
	}
	void cals(int x,int fa){
		// cout<<x<<'\n';
		s[x]=U[x];
		for(auto t:v[x]){
			if(t^fa){
				cals(t,x);
				s[x]+=s[t]+1;
			}
		}
	}
	int ans=0;
	void solve(int x,int fa){
		for(int to:v[x]){
			if(to^fa){
				solve(to,x);
				dp[x][1]=dp[x][0]*dp[to][1]%p+dp[x][1]*(2*dp[to][0]+dp[to][1])%p;
				dp[x][1]%=p;
				dp[x][0]=2*dp[to][0]*dp[x][0]%p;
			}
		}
		if(x==1){
			ans+=dp[x][1];
			ans%=p;
		}
		else{
			ans+=ksm(2,s[1]-s[x]-1)*dp[x][1]%p;
			ans%=p;
		}
	}
}tar;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		edg.add(x,y);
		edg.add(y,x);
	}
	tar.dfs(1,0);
	tar.check();
	tar.cals(1,0);
	tar.solve(1,0);
	cout<<tar.ans;
}
2023/10/11 19:59
加载中...