제출 #1298801

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1298801		PieArmy	Star Trek (CEOI20_startrek)	C++20	100 / 100	83 ms	19164 KiB

startrek

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
#define int ll
const ll mod=1e9+7;
typedef array<array<ll,3>,3> mat;

ll sum(ll x,ll y){
	return (x+y)%mod;
}

ll mul(ll x,ll y){
	x%=mod;y%=mod;
	return (x*y)%mod;
}

ll fpow(ll x,ll y){
	ll res=1;
	while(y>0){
		if(y&1){
			res=mul(res,x);
		}
		x=mul(x,x);
		y>>=1;
	}
	return res;
}

mat matmul(mat x,mat y){
	mat res;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			res[i][j]=0;
			for(int l=0;l<3;l++){
				res[i][j]=sum(res[i][j],mul(x[i][l],y[l][j]));
			}
		}
	}
	return res;
}

mat matpow(mat x,ll y){
	mat res={1,0,0,0,1,0,0,0,1};
	while(y>0){
		if(y&1)res=matmul(res,x);
		x=matmul(x,x);
		y>>=1;
	}
	return res;
}

int n;
ll d;
vector<int>komsu[100023];
int dp[100023],cnt[100023];
int dp2[100023],cnt2[100023];
int dp3[100023],cnt3[100023];
int par[100023];
ll ans=0;

void dfs2(int pos){
	dp[pos]=dp2[pos];
	cnt[pos]=cnt2[pos];
	if(par[pos]){
		dp3[pos]=dp[par[pos]];
		cnt3[pos]=cnt[par[pos]];
		if(dp2[pos]==0){
			dp3[pos]--;
			if(dp3[pos]==0){
				cnt3[pos]=1;
				for(int x:komsu[par[pos]]){
					if(x==pos)continue;
					if(x==par[par[pos]])continue;
					cnt3[pos]+=cnt2[x];
				}
				if(par[par[pos]]){
					cnt3[pos]+=cnt3[par[pos]];
				}
			}
			else if(dp3[pos]==1){
				for(int x:komsu[par[pos]]){
					if(x==pos)continue;
					if(x==par[par[pos]])continue;
					if(dp2[x]==0){
						cnt3[pos]+=cnt2[x];
					}
				}
				if(par[par[pos]]&&dp3[par[pos]]==0){
					cnt3[pos]+=cnt3[par[pos]];
				}
			}
		}
		else if(dp3[pos]==0){
			cnt3[pos]-=cnt2[pos];
		}
		dp[pos]=!dp3[pos];
		cnt[pos]=0;
		for(int x:komsu[pos]){
			if(x==par[pos])continue;
			dp[pos]+=!dp2[x];
		}
		if(dp[pos]==0){
			cnt[pos]++;
		}
		for(int x:komsu[pos]){
			if(x==par[pos]){
				if(dp[pos]==1){
					if(dp3[pos]==0){
						cnt[pos]+=cnt3[pos];
					}
				}
				else if(dp[pos]==0){
					cnt[pos]+=cnt3[pos];
				}
				continue;
			}
			if(dp[pos]==1){
				if(dp2[x]==0){
					cnt[pos]+=cnt2[x];
				}
			}
			else if(dp[pos]==0){
				cnt[pos]+=cnt2[x];
			}
		}
	}
	for(int x:komsu[pos]){
		if(x==par[pos])continue;
		dfs2(x);
	}
}

void dfs(int pos){
	for(int x:komsu[pos]){
		if(x==par[pos])continue;
		par[x]=pos;
		dfs(x);
		dp2[pos]+=!dp2[x];
	}
	if(dp2[pos]>1)return;
	if(dp2[pos]==0)cnt2[pos]++;
	for(int x:komsu[pos]){
		if(x==par[pos])continue;
		if(dp2[pos]==1){
			if(dp2[x]==0){
				cnt2[pos]+=cnt2[x];
			}
		}
		else{
			cnt2[pos]+=cnt2[x];
		}
	}
}

const bool deb=false;

int32_t main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n>>d;
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		komsu[x].pb(y);
		komsu[y].pb(x);
	}
	if(n==2){
		cout<<fpow(2,d*2)<<endl;
		return 0;
	}
	dfs(1);
	dfs2(1);
	int ez=0;
	ans=0;
	ll kazan[2]={0,0};
	ll devam[2]={0,0};
	ll iht[2]={0,0};
	if(dp[1]){
		ans=mul(n-cnt[1],fpow(n,2*d-1));
		iht[1]=cnt[1];
	}
	else{
		iht[0]=cnt[1];
	}
	for(int i=1;i<=n;i++){
		if(deb)cout<<dp[i]<<"-"<<cnt[i]<<endl;
		if(dp[i]){
			ez++;
			kazan[1]=sum(kazan[1],n-cnt[i]);
			devam[0]=sum(devam[0],cnt[i]);
		}
		else{
			kazan[0]=sum(kazan[0],n-cnt[i]);
			devam[1]=sum(devam[1],cnt[i]);
		}
	}
	devam[0]=mul(devam[0],fpow(mul(n,n),mod-2));
	devam[1]=mul(devam[1],fpow(mul(n,n),mod-2));
	mat m= {1,0,0,
			kazan[0],devam[0],devam[1],
			kazan[1],devam[1],devam[0]};
	iht[0]=mul(iht[0],fpow(n,d==1?mod-2:(2*d-3)));
	iht[1]=mul(iht[1],fpow(n,d==1?mod-2:(2*d-3)));
	m=matpow(m,d-1);
	ans=sum(mul(ans,m[0][0]),sum(mul(m[1][0],iht[0]),
								mul(m[2][0],iht[1])));
	ll iht2[2];
	iht2[0]=sum(mul(iht[0],m[1][1]),mul(iht[1],m[2][1]));
	iht2[1]=sum(mul(iht[0],m[1][2]),mul(iht[1],m[2][2]));
	iht[0]=mul(iht2[0],n);
	iht[1]=mul(iht2[1],n);
	ans=sum(ans,sum(mul(iht[0],n-ez),mul(iht[1],ez)));
	cout<<ans<<endl;
}

• Subtask 1: 0 / 0
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 15 / 15