Submission #1156989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156989		RSAMSD	Star Trek (CEOI20_startrek)	C++20	23 / 100	1096 ms	13040 KiB

startrek

#include<bits/stdc++.h>
using namespace std;
const int f = 1e5+10;
const int mod = 1e9+7;
vector<int> g[f];
long long dp[f];
bool B[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&1)ans = zarb(ans,a);
		p/=2;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];
	return cnt;
}
int main(){
	int 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--){
		hI = dfs(i,0);
		if(B[i]){
			mH+=dp[i];
		}
		else {
			mI+=dp[i];
			I++;
			// cout<<i<<'\n';
		}
		mI%=mod;mH%=mod;
	}
	matric base;
	base.id[0][0] = I;
	base.id[0][1] = I*n%mod;
	base.id[1][0] = base.id[1][1] = 0;
	long long gI,fI;
	if(d>1){
		matric mp = powmat(makemat(mI-mH,n),d);
		base = zarb(base,mp);
	}
	gI = base.id[0][0];
	if(d>1){
		fI = powmod(powmod(n,2),d-1)-gI;
		fI+=mod;fI%=mod;
	}
	else fI = n-gI;
	if(!B[1]){
		cout<<gI*dp[1]%mod;
	}
	else cout<<((powmod(n,2*d)-gI*dp[1])%mod+mod)%mod;
	// cout<<" "<<gI<<" "<<fI<<" "<<hI<<" "<<dp[1];
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 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