Submission #1298790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298790		PieArmy	Star Trek (CEOI20_startrek)	C++20	100 / 100	80 ms	19188 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;

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;
}

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;

ll cal[60];

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);
	ll c=0,bad=0;
	for(int i=1;i<=n;i++){
		if(dp[i]){
			c=sum(c,cnt[i]);
		}
		else{
			bad++;
			c=sum(c,mod-cnt[i]);
		}
	}
	ll d2=0;
	for(int i=0;i<60;i++){
		for(int j=0;j<i;j++){
			cal[i]=mul(cal[i],fpow(c,1ll<<j));
			cal[i]=sum(cal[i],mul(cal[j],fpow(n,(2ll<<j)-2)));
		}
		cal[i]=sum(mul(cal[i],c),mul(bad,fpow(n,2ll<<i)));
		if(((d-1)>>i)&1){
			ans=mul(ans,fpow(c,1ll<<i));
			ans=sum(ans,mul(cal[i],fpow(n,2*d2)));
			d2+=(1ll<<i);
		}
	}
	ans=sum(ans,mul(bad,fpow(c,d-1)));
	ans=mul(ans,cnt[1]);
	if(dp[1])ans=sum(fpow(mul(n,n),d),mod-ans);
	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