제출 #1288203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288203		Icelast	Star Trek (CEOI20_startrek)	C++20	45 / 100	102 ms	65404 KiB

startrek

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 1e5+5, INF = 4e18+9, mod = 1e9+7;
vector<ll> fact, invfact;
ll binpow(ll a, ll b){
    ll res = 1;
    while(b > 0){
        if(b&1){
            res*=a;
            res%=mod;
        }
        a*=a;
        a%=mod;
        b/=2;
    }
    return res;
}
ll modinv(ll x){
    return binpow(x, mod-2);
}
void calcfact(int n){
    fact.resize(n+1, 0);
    invfact.resize(n+1, 0);

    fact[0] = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = fact[i-1]*i;
        fact[i]%=mod;
    }
    invfact[n] = modinv(fact[n]);
    for(int i = n-1; i >= 0; i--){
        invfact[i] = invfact[i+1]*(i+1)%mod;
    }
}
ll nCk(ll n, ll k){
    if(k < 0 || k > n) return 0;
    return fact[n]*(invfact[k]*invfact[n-k]%mod)%mod;
}
ll distributing_apples(ll n, ll m){ // number of people, apple
    return nCk(m+n-1, n-1);
}
void solve(){
    ll n, D;
    cin >> n >> D;
    vector<vector<int>> adj(n+1);
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> f(n+1), g(n+1);
    {
        auto dfs = [&](auto dfs, int u, int p) -> void{
            f[u] = 0;
            g[u] = 0;
            int onlyv = 0, vv = -1;
            for(int v : adj[u]){
                if(v == p) continue;
                dfs(dfs, v, u);
                if(f[v] == 0) f[u] = 1;
                if(f[v] == 0){
                    vv = v;
                    onlyv++;
                }
            }
            if(f[u] == 1){
                if(onlyv == 1){
                    for(int v : adj[u]){
                        if(v == vv){
                            g[u] += g[v];
                        }
                    }
                }
            }else{
                for(int v : adj[u]){
                    if(f[v] == 1){
                        g[u] += g[v];
                    }
                }
                g[u]++;
            }
        };
        dfs(dfs, 1, 0);
    }
    {
        vector<int> t(n+1), tg(n+1);
        auto dfs = [&](auto dfs, int u, int p) -> void{
            t[u] = f[u];
            tg[u] = g[u];
            int m = adj[u].size();
            vector<int> pf(m+1, 0), sf(m+2, 0);
            vector<int> state(m+1);
            vector<int> pfg(m+1, 0), sfg(m+2, 0);
            vector<int> sg(m+1, 0);
            int it = 0;
            for(int v : adj[u]){
                it++;
                state[it] = (f[v] == 0);
                if(f[v] != f[u]) sg[it] = g[v];
            }
            for(int i = 1; i <= m; i++){
                pf[i] = pf[i-1] + state[i];
                pfg[i] = pfg[i-1] + sg[i];
            }
            for(int i = m; i >= 1; i--){
                sf[i] = sf[i+1] + state[i];
                sfg[i] = sfg[i+1] + sg[i];
            }
            it = 0;
            for(int v : adj[u]){
                it++;
                if(v == p) continue;

                int rb = f[u], rbg = g[u];

                f[u] = (pf[it-1] + sf[it+1] > 0);
                if(f[u] == 1){
                    if(pf[it-1] + sf[it+1] == 1){
                        g[u] = pfg[it-1] + sfg[it+1];
                    }else{
                        g[u] = 0;
                    }
                }else{
                    g[u] = pfg[it-1] + sfg[it+1];
                    g[u]++;
                }

                if((f[v] | (f[u] == 0)) == 1){
                    if(f[v] == 0 && f[u] == 0){
                        g[v] += g[u];
                    }else if(f[v] == 1 && f[u] == 0){
                        g[v] = 0;
                    }
                }else{
                    g[v] += g[u];
                }
                f[v] |= (f[u] == 0);

                dfs(dfs, v, u);
                f[u] = rb;
                g[u] = rbg;
            }
        };
        dfs(dfs, 1, 0);
        f = t;
        g = tg;
    }
    ll WC = 0, LC = 0, W = 0, L = 0;
    for(int i = 1; i <= n; i++){
        if(f[i] == 1){
            WC += g[i];
            W ++;
        }else{
            LC += g[i];
            L ++;
        }
    }
    WC %= mod;
    LC %= mod;
    ll E = (WC - LC + mod)%mod;

    ll LD = L * (binpow(n, 2*D) - binpow(E, D) + mod) % mod * modinv((binpow(n, 2*D)%mod + mod - E)%mod) % mod;
    ll ans;
    if(f[1] == 0){
        ans = LD * g[1] % mod;
    }else{
        ans = binpow(n, 2*D) - LD * g[1] % mod + mod;
        ans %= mod;
    }
    //cout << binpow(4, D) << "\n";
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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