官方数据100 但是民间数据 55 求问
查看原帖
官方数据100 但是民间数据 55 求问
982681
D0000楼主2024/10/3 08:37

代码:


#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>
#define int long long
int n,m,nn[500005],mm[500005],p[500005],d[500005],dp[500005][3],mod=1e9+7,base2[500005];
bool b[500005];
std::vector<std::vector<int> >v(500005),rv(500005);
std::vector<std::pair<int,int> >e;
int qu(int x){
	if(x-p[x])p[x]=qu(p[x]);
	return p[x];
}
void merge(int x,int y){
	x=qu(x),y=qu(y);
	if(x-y)p[x]=y,nn[y]+=nn[x];
}
void dfs(int now=1,int p=-1,int dd=0){
	d[now]=dd;
	b[now]=1;
	for(int vv:v[now])if(vv-p){
		if(b[vv])merge(now,vv),d[now]=std::min(d[now],d[vv]);
		else{
			dfs(vv,now,dd+1);
			if(d[vv]<d[now])merge(now,vv),d[now]=std::min(d[now],d[vv]);
		}
	}
}
int mul(int a,int x){
	if(!x)return 1;
	int t=mul(a,x/2);
	t=1ll*t*t%mod;
	if(x%2)return 1ll*t*a%mod;
	return t;
}
void dds(int now=1,int p=-1){
	if(rv[now].size()==1&&now!=1){
		dp[now][0]=base2[mm[now]];
		dp[now][1]=base2[mm[now]+nn[now]]-dp[now][0];
		dp[now][1]%=mod;
		dp[now][1]+=mod;
		dp[now][1]%=mod;
		return;
	}
	dp[now][0]=base2[mm[now]];
	dp[now][1]=base2[mm[now]];
	for(int vv:rv[now])if(vv-p){
		dds(vv,now);
		dp[now][0]=(2ll*dp[vv][0]*dp[now][0])%mod;
		dp[now][1]=(2ll*dp[vv][0]+dp[vv][1])*dp[now][1]%mod;
	}
	for(int vv:rv[now])if(vv-p){
		dp[now][2]=(dp[now][2]+1ll*dp[now][0]*mul((2ll*dp[vv][0])%mod,mod-2)%mod*1ll*(dp[vv][1]+2ll*dp[vv][2])%mod)%mod;
		//printf("%d:",1ll*dp[now][0]*mul((2ll*dp[vv][0])%mod,mod-2)%mod);
	}
	//printf("%d %d %d\n",dp[now][0],dp[now][1],dp[now][2]);
	dp[now][1]=(((1ll*dp[now][1]*base2[nn[now]]-dp[now][0])%mod)+mod)%mod;
} 
signed main(){
	//printf("%d ",mul(2,10));
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++){//puts("*");
		int u,v;
		scanf("%lld%lld",&u,&v);
		::v[v].push_back(u);
		::v[u].push_back(v);
		e.push_back(std::make_pair(u,v));
	}
	for(int i=1;i<=n;i++)p[i]=i,nn[i]=1;//puts("*");
	dfs();
	for(std::pair<int,int>zyh:e){
		int x=zyh.first,y=zyh.second;
		x=qu(x),y=qu(y);
		if(x==y)mm[x]++;
		else rv[x].push_back(y),rv[y].push_back(x);
	}
	base2[0]=1;
	for(int i=1;i<=5e5;i++)base2[i]=(base2[i-1]<<1)%mod;
	dds();
	//for(int i=1;i<=n;i++)printf("%d %d %d\n",dp[i][0],dp[i][1],dp[i][2]);
	printf("%d",(dp[1][1]+dp[1][2])%mod);
}
2024/10/3 08:37
加载中...