Submission #1005118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005118		AlperenT_	Star Trek (CEOI20_startrek)	C++17	100 / 100	49 ms	28652 KiB

startrek

#include <bits/stdc++.h>
 

#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define int long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i, a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e5  ,  N = 1e5 +1 , lg = 20 , maxq = 202 , sq = 100   , inf = 1e8 +100 , maxk = 2022 , mod = 1e9 + 7;
int dp[maxn][2] , s[maxn][2] , par[maxn] , ans[maxn] , ted[maxn]  ; 
vector <int> G[maxn] ;

int po(int a, int b){
  if(b==0)return 1 ;
  int v = po(a,b/2) ;
  v =v*v % mod ; 
  if(b&1) v = v*a % mod ;
  return v ;
}

void down(int v, int p =0){
  dp[v][0] = 0;int sum =0 ; 
  for(int u : G[v]){
    if(u == p)continue ;
    down(u , v) ;
    dp[v][0] |= !dp[u][0] ;  
    sum += !dp[u][0 ];
  }
  if(dp[v][0] == 0){
    s[v][0] = 1; 
    for(int u : G[v]){
      if(u == p)continue ;
      s[v][0] += s[u][0] ; 
    }
  }else{
    if(sum==1)
    for(int u : G[v]){
      if(u == p || dp[u][0] == 1)continue ; 
      s[v][0] += s[u][0] ;
    }
  }
} 
void up(int v ,int p=0){
  int t[2] , f[2] ; 
  t[0] = t[1] = f[0] = f[1] =0 ;
  if(p != 0){
    t[dp[v][1]] ++ ;
    f[dp[v][1]] += s[v][1] ;
  }
  for(int u : G[v]){
    if(u == p)continue ;
    t[dp[u][0]]++;
    f[dp[u][0]]+=s[u][0] ; 
  } 
  for(int u : G[v]){
    if(u == p)continue  ;
    t[dp[u][0]]--;
    f[dp[u][0]]-=s[u][0] ;
    if(t[0] == 0){
      dp[u][1] = 0 ;
      s[u][1] = 1 + f[1] ;
    }else{
      dp[u][1] = 1 ; 
      if(t[0] == 1){
        s[u][1] += f[0] ; 
      }
      
    }
    t[dp[u][0]]++;
    f[dp[u][0]]+=s[u][0] ;
  }
  if(t[0] == 0){
    ans[v] = 0 ;
    ted[v] = f[1] + 1  ; 
  }else{
    ans[v] =1 ;
    if(t[0] == 1)ted[v] = f[0] ; 
  }
  for(int u : G[v]){
    if(u ==p)continue ;
    up(u , v) ;  
  }
}
struct mat{
  int a[4][4] , n , m ; 
  mat(){
    rep(i , 0 ,2)rep(j , 0 , 2)a[i][j] = 0 ; 
  }
};;

mat operator* (mat a , mat b){
  mat r ; 
  r.n = b.n ;
  r.m = a.m ;
  rep(i , 0 , r.n-1){
    rep(j , 0 , r.m-1){
      rep(k , 0 , a.n-1){
        r.a[i][j]=  (r.a[i][j] + a.a[k][j] * b.a[i][k]%mod)%mod ;
      }
    }
  }
  return r ; 
}
mat pw(mat a , int d){
  mat ans ;
  rep(i , 0, 1)ans.a[i][i] = 1 ;
  ans.n = ans.m = 2 ;
  while(d){
    if(d&1) ans = ans * a ;
    a = a*a ;
    d/=2; 
  }
  return ans ; 
}

signed main() { 
  ios::sync_with_stdio(false); cin.tie(0);   
  int n , d; cin >> n >> d ;
  rep(i , 1, n-1){
    int v , u ;cin >> v >> u ;
    G[v].pb(u) ;
    G[u].pb(v) ;
  }
  down(1) ;
  up(1) ;
  int t1 = 0  , t2 =0  ,t3 =0 ;  
  rep(i , 1, n){
    if(ans[i] == 0){
      t1 ++ ;
      t3 = (t3 + ted[i])%mod ;
      t2 = (t2 + n-ted[i])%mod ;
   }else{
     t3 = (t3 + n-ted[i])%mod ;
     t2 = (t2 + ted[i])%mod ;
   }
  }
  mat z ;z.n = 2 ; z.m = 2 ;
  z.a[0][1] = n*t1%mod ;
  z.a[0][0] = t2 ;
  //
  z.a[1][1] = n*(n-t1)%mod ;
  z.a[1][0] = t3 ;
  mat a ;a.n = 2 ; a.m = 1 ;
  a.a[0][0] = t1 ;a.a[1][0] = n-t1 ;
  mat x = pw(z , d-1) ;
  a = a*x ;
  int g = ted[1] * a.a[0][0] % mod ;
  if(ans[1] == 1)g = (po(n*n%mod , d) - g + mod)%mod ;
  cout << g << "\n" ;
}
/*

*/

• 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