Submission #701564

#	Time	Username	Problem	Language	Result	Execution time	Memory
701564		PCTprobability	Star Trek (CEOI20_startrek)	C++17	50 / 100	34 ms	5204 KiB

startrek

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1000000007;
#define fi first
#define se second
#define pb push_back
ll modPow(ll a,ll b,ll c){
  ll r=1;
  while(b){
    if(b&1) (r*=a)%=mod;
    (a*=a)%=mod;
    b/=2;
  }
  return r;
}
vector<ll> g[100000];
int v[100000];
bool win[100000];
void dfs(ll a,ll b){
  v[a]=1;
  for(auto e:g[a]){
    if(e==b) continue;
    dfs(e,a);
    if(!win[e]) win[a]=true;
    v[a]+=v[e];
  }
}
ll cnt=0;
void dfs2(ll a,ll b,ll x){
  if(x==0) cnt++;
  if(x==1){
    ll k=0;
    for(auto e:g[a]){
      if(e==b) continue;
      if(!win[e]) k++;
    }
    if(k>=2) return;
  }
  for(auto e:g[a]){
    if(e==b) continue;
    if(x==1&&win[e]) continue;
    dfs2(e,a,x^1);
  }
}
ll cnt2=0;
void dfs3(ll a,ll b,ll x){
  if(x) cnt2++;
  if(x==0){
    ll k=0;
    for(auto e:g[a]){
      if(e==b) continue;
      if(!win[e]) k++;
    }
    if(k>=2) return;
  }
  for(auto e:g[a]){
    if(e==b) continue;
    if(x==0&&win[e]) continue;
    dfs3(e,a,x^1);
  }
}
int main(){
  ll n,d;
  cin>>n>>d;
  if(n==2){
    cout<<modPow(4,d,mod)<<endl;
    return 0;
  }
  assert(n<=1000&&d<=100000);
  for(int i=0;i<n-1;i++){
    ll a,b;
    cin>>a>>b;
    a--;
    b--;
    g[a].pb(b);
    g[b].pb(a);
  }
  ll x=0,y=0;
  ll z=0;
  ll type=0,x1=0,y1=0;
  for(int i=0;i<n;i++){
    cnt=0,cnt2=0;
    for(int j=0;j<n;j++) win[j]=false;
    dfs(i,-1);
    ll cn=0,V=0;
    for(auto e:g[i]){
      if(!win[e]){
        cn++;
        V=e;
      }
    }
    if(cn) z++;
    if(cn>=2){
      x++;
    }
    if(cn==1){
      dfs3(V,i,1);
      x+=modPow(n,mod-2,mod)*(n-cnt2);
      x%=mod;
      y+=cnt2;
      y%=mod;
      if(i==0){
        type=1;
        x1+=modPow(n,mod-2,mod)*(n-cnt2);
        y1+=cnt2;
      }
    }
    if(cn==0){
      dfs2(i,-1,0);
      y-=cnt;
      y+=mod;
      y%=mod;
      x+=modPow(n%mod,mod-2,mod)*cnt;
      x%=mod;
      if(i==0){
        type=1;
        x1+=modPow(n%mod,mod-2,mod)*cnt;
        y1-=cnt;
        y1+=mod;
      }
    }
  }
  x1%=mod;
  y1%=mod;
  for(int i=1;i<d;i++){
    z=(z*y + x*modPow(n,2*i,mod));
    z%=mod;
  }
  if(type==0){
    cout<<modPow(n,2*d,mod)<<endl;
  }
  else{
    cout<<(x1*modPow(n,2*d,mod)+y1*z)%mod<<endl;
  }
}

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