Submission #1157472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157472		RSAMSD	Star Trek (CEOI20_startrek)	C++20	30 / 100	1095 ms	13764 KiB

startrek

#include<bits/stdc++.h>
using namespace std;
const int f = 1e5+10;
const long long mod = 1e9+7;
vector<int> g[f];
long long dp[f];
long long ways[f];
bool B[f];
bool F[f];
pair<long long,long long> dpI[f];
pair<long long,long long> dpI0[f];
struct matric{
	long long id[5][5];
	matric(){
		for(int i =0;i<5;i++){
			for(int j =0;j<5;j++){
				id[i][j] =0;
			}
		}
	}
};
long long powmod(long long a,long long p){
	long long ans = 1;
	while(p>0){
		if(p&1)ans = ans*a%mod;
		p/=2;a = a*a%mod;
	}
	return ans;
}
matric makemat(long long x,long long n){
	matric a;
	a.id[0][0] = (x+mod)%mod;
	a.id[1][0] = 1;
	a.id[0][1] = 0;
	a.id[1][1] = powmod(n,2);
	return a;
}
matric zarb(matric a,matric b){
	matric ans;
	for(int i =0;i<2;i++){
		for(int j =0;j<2;j++){
			ans.id[i][j] = 0;
			for(int h =0;h<2;h++){
				ans.id[i][j]+=(a.id[i][h]*b.id[h][j])%mod;
				ans.id[i][j]%=mod;
			}
		}
	}
	return ans;
}
matric powmat(matric a,long long p){
	matric ans = a;p--;
	while(p>0){
		if(p&1LL)ans = zarb(ans,a);
		p/=2LL;a = zarb(a,a);
	}
	return ans;
}
int dfs(int v,int par){
	int cnt =0;
	int much =0;
	int meny = 0;
	for(int u:g[v]){
		if(u==par)continue;
		cnt+=dfs(u,v);
		much+=!B[u];
	}
	if(much==0){
		B[v] = 0;
		for(int u:g[v]){
			if(u==par)continue;
			meny+=dp[u];
		}
		dp[v] = meny;
		// cout<<v<<'\n';
	}
	else if (much==1){
		B[v] = 1;
		for(int u:g[v]){
			if(u==par)continue;
			if(!B[u])meny+=dp[u];
		}
		dp[v] = meny;
	}
	else{
		B[v] = 1;
		dp[v] = 0;
	}
	cnt+=!B[v];
	dp[v]+=!B[v];
	ways[v] = much;
	return cnt;
}
int dfs2(int v,int par){
	int cnt =0 ;
	if(v!=1){
		if(!F[par]&&ways[par]-!B[v]==0)F[v] =1;
		else F[v] = 0;
	}
	else{
		F[1] = 0;
	}
	cnt = !(B[v]||F[v]);
	for(int u:g[v]){
		if(u==par)continue;
		cnt+=dfs2(u,v);
	}
	return cnt;
}
void dfsI1(int v,int par){
	dpI[v] = {0,0};
	for(int u:g[v]){
		if(u==par)continue;
		dfsI1(u,v);
		if(ways[v]+(F[v])-!B[u]==0){
			dpI[v].first+=dpI[u].second;
		}
		else if(ways[v]+(F[v])-!B[u]==1){
			dpI[v].second+=dpI[u].first;
		}
	}
	dpI[v].second+=(ways[v]+F[v]==1);
	// cout<<v<<" "<<dpI[v].first<<'\n';
}
void dfsI2(int v,int par){
	dpI0[v] = {0,0};
	if(par==1){
		if(B[v]==0){
			dpI0[v].first+=dpI[par].second;
			if(ways[par]+(F[par])-!B[v]==1){
				dpI0[v].first-=dpI[v].first;
			}
		}
		else if(ways[v]==1){
			dpI0[v].second+=dpI[par].first;
			if(ways[par]+(F[par])-!B[v]==0){
				dpI0[v].second-=dpI[v].second;
			}
			// cout<<"?";
		}
	}
	else if(par!=0){
		if(B[v]==0){
			dpI0[v].first+=dpI0[par].second;
		}
		else if(ways[v]==1){
			dpI0[v].second+=dpI0[par].first;
		}
	}
	dpI0[v].second+=(ways[v]+F[v]==1);
	// cout<<v<<" "<<dpI0[v].first<<" "<<dpI0[v].second<<'\n';
	for(int u:g[v]){
		if(u==par)continue;
		dfsI2(u,v);
	}
}
int main(){
	long long n,d;cin>>n>>d;
	for(int i =0;i<n-1;i++){
		int l,r;cin>>l>>r;
		g[l].push_back(r);
		g[r].push_back(l);
	}
	long long mI =0,mH = 0,I =0,hI =0;
	for(int i =n;i>=1;i--){
		dfs(i,0);
		if(B[i]){
			mH+=dp[i];
		}
		else {
			mI+=dp[i];
		}
		// cout<<mI<<" "<<mH<<'\n';
		// mI%=mod;mH%=mod;
	}
	// cout<<hI<<" "<<dfs(1,0)<<'\n';
	// cout<<I <<" "<< dfs2(1,0)<<'\n';
	hI = dfs(1,0);
	I = dfs2(1,0);
	dfsI1(1,0);
	dfsI2(1,0);
	long long myans =0;
	for(int i =1;i<=n;i++){
		myans+=dpI[i].first+dpI0[i].first;
		// cout<<i<<" "<<dpI[i].first<<" "<<dpI0[i].first<<'\n';
	}
	// myans-=n-I;
	// cout<<mH<<" "<<myans<<'\n';
	mH = myans;
	matric base;
	base.id[0][0] = I;
	base.id[0][1] =  (I*n%mod)*n%mod;
	base.id[1][0] = base.id[1][1] = 0;
	long long gI,fI;
	if(d>1){
		matric mp = powmat(makemat(mH-mI,n),d-1);
		base = zarb(base,mp);
	}
	gI = base.id[0][0];
	if(!B[1]){
		cout<<gI*dp[1]%mod;
	}
	else cout<<((powmod(n,2*d)-gI*dp[1])%mod+mod)%mod;
	// cout<<'\n'<<gI<<" "<<fI<<" "<<hI<<" "<<dp[1];
}

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