Submission #1291870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291870		kerem	Star Trek (CEOI20_startrek)	C++20	100 / 100	73 ms	29388 KiB

startrek

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define emb emplace_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define N 100000
#define inf (int)1e15
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;

const int mod=1000000007;

int gd[N+5],cnt[N+5];
vector<int> g[N+5],cntv[N+5],gdv[N+5];
void dfs1(int x,int ata){
	int n=g[x].size();
	gdv[x].assign(n,0);
	cntv[x].assign(n,0);
	
	gd[x]=1;
	int cnt0=0;
	for(int i=0;i<n;i++){
		if(g[x][i]==ata) continue;
		dfs1(g[x][i],x);
		gdv[x][i]=gd[g[x][i]];
		cntv[x][i]=cnt[g[x][i]];
		
		cnt0+=!gd[g[x][i]];
		gd[x]&=gd[g[x][i]];
	}
	gd[x]=!gd[x];
	if(cnt0==0){
		cnt[x]=1;
		for(int i=0;i<n;i++)
			if(g[x][i]!=ata)
				cnt[x]+=cnt[g[x][i]];
	}
	if(cnt0==1){
		for(int i=0;i<n;i++)
			if(g[x][i]!=ata && !gd[g[x][i]])
				cnt[x]=cnt[g[x][i]];
	}
}
void dfs2(int x,int ata,int pcnt,int pgd){
	int n=g[x].size();
	for(int i=0;i<n;i++){
		if(g[x][i]==ata){
			cntv[x][i]=pcnt;
			gdv[x][i]=pgd;
		}
	}
	
	int cnt0=0;
	for(int i=0;i<n;i++)
		cnt0+=!gdv[x][i];
	if(cnt0==0){
		gd[x]=0;
		int t=1;
		for(int i=0;i<n;i++)
			t+=cntv[x][i];
		cnt[x]=t;
		for(int i=0;i<n;i++)
			if(g[x][i]!=ata)
				dfs2(g[x][i],x,t-cntv[x][i],0);
	}
	if(cnt0==1){
		gd[x]=1;
		int t0=0,t1=0;
		for(int i=0;i<n;i++){
			if(!gdv[x][i])
				t0=cntv[x][i];
			else
				t1+=cntv[x][i];
		}
		cnt[x]=t0;
		for(int i=0;i<n;i++){
			if(g[x][i]==ata) continue;
			if(!gdv[x][i])
				dfs2(g[x][i],x,t1+1,0);
			else
				dfs2(g[x][i],x,t0,1);
		}
	}
	if(cnt0==2){
		gd[x]=1;
		cnt[x]=0;
		int t[2]={-1,-1},j[2];
		for(int i=0;i<n;i++){
			if(!gdv[x][i]){
				if(t[0]==-1)
					t[0]=cntv[x][i],j[0]=i;
				else
					t[1]=cntv[x][i],j[1]=i;
			}
		}
		for(int i=0;i<n;i++){
			if(g[x][i]==ata) continue;
			if(i==j[0])
				dfs2(g[x][i],x,t[1],1);
			else if(i==j[1])
				dfs2(g[x][i],x,t[0],1);
			else
				dfs2(g[x][i],x,0,1);
		}
	}
	if(cnt0>2){
		gd[x]=1;
		cnt[x]=0;
		for(int i=0;i<n;i++)
			if(g[x][i]!=ata)
				dfs2(g[x][i],x,0,1);
	}
}

struct Matrix{
	array<array<int,4>,4> arr;
	Matrix():arr(){}
};
Matrix operator *(Matrix A,Matrix B){
	Matrix ans;
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			for(int k=0;k<4;k++)
				ans.arr[i][j]+=A.arr[i][k]*B.arr[k][j]%mod;
			ans.arr[i][j]%=mod;
		}
	}
	return ans;
}
Matrix matFp(Matrix M,int x){
	Matrix ans;
	for(int i=0;i<4;i++)
		ans.arr[i][i]=1;
	for(;x;x>>=1,M=M*M)
		if(x&1) ans=ans*M;
	return ans;
}
int fp(int x,int y){
	int ans=1;
	for(;y;x=x*x%mod,y>>=1)
		if(y&1) ans=ans*x%mod;
	return ans;
}
void solve(){
	int n,D;
	cin >> n >> D;
	for(int i=1;i<n;i++){
		int x,y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	dfs1(1,0);
	dfs2(1,0,0,0);

	int t[4]={0,0,0,0};
	for(int i=1;i<=n;i++){
		t[gd[i]<<1]+=cnt[i];
		t[gd[i]<<1|1]+=n-cnt[i];
	}
	t[0]%=mod;t[1]%=mod;
	t[2]%=mod;t[3]%=mod;
	Matrix M;
	M.arr[0]={t[2],0,t[0],0};
	M.arr[1]={t[3],n*n%mod,t[1],0};
	M.arr[2]={t[0],0,t[2],0};
	M.arr[3]={t[1],0,t[3],n*n%mod};
	M=matFp(M,D);
	
	int stVec[4]={0,0,0,0};
	stVec[gd[1]<<1]+=cnt[1];
	stVec[gd[1]<<1|1]+=n-cnt[1];
	int ansVec[4]={0,0,0,0};
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++)
			ansVec[i]+=stVec[j]*M.arr[i][j]%mod;
		ansVec[i]%=mod;
	}
	int ans=(ansVec[2]+ansVec[3])*fp(n,mod-2)%mod;
	cout << ans << "\n";
}
int32_t main(){
	cout << fixed << setprecision(0);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

• 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