제출 #660080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
660080		Kahou	Star Trek (CEOI20_startrek)	C++14	100 / 100	532 ms	117036 KiB

startrek

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int mod = 1e9 + 7;
int add(int a, int b) {
        a += b;
        if (a >= mod) a -= mod;
        if (a < 0) a += mod;
        return a;
}
int mul(int a, int b) {
        return 1ll*a*b%mod;
}

const int N = 1e5 + 50, LG = 62;
int n, pw[LG];
ll d;
vector<int> adj[N];
pii dpdw[N], dpup[N], dp[LG][N][2], out[N][2], tmp[N][2]; 

void dfs(int u, int p) {
        int cnt, sum, sbd;
        cnt = sum = sbd = 0;
        for (int v:adj[u]) {
                if(v == p) continue;
                dfs(v, u);
                sum = add(sum, dpdw[v].S);
                sbd = add(sbd, dpdw[v].F*dpdw[v].S);
                cnt += dpdw[v].F;
        }
        dpdw[u].F = !cnt;
        if (cnt >= 2) return;
        dpdw[u].S = (cnt? sbd:sum+1);
}

void sfd(int u, int p) {
        int cnt, sum, sbd;
        cnt = dpup[u].F;
        sum = dpup[u].S;
        sbd = dpup[u].F*dpup[u].S;
        for (int v:adj[u]) {
                if (v == p) continue;
                sum = add(sum, dpdw[v].S);
                sbd = add(sbd, dpdw[v].F*dpdw[v].S);
                cnt += dpdw[v].F;
        }
        for (int v:adj[u]) {
                if (v == p) continue;
                sum = add(sum, -dpdw[v].S);
                sbd = add(sbd, -dpdw[v].F*dpdw[v].S);
                cnt -= dpdw[v].F;

                dpup[v].F = !cnt;
                if (cnt < 2) dpup[v].S = (cnt? sbd:sum+1);

                sum = add(sum, dpdw[v].S);
                sbd = add(sbd, dpdw[v].F*dpdw[v].S);
                cnt += dpdw[v].F;

                sfd(v, u);
        }
}

void solve() {
        cin >> n >> d;
        d++;
        for (int i = 1; i <= n-1; i++) {
                int u, v;
                cin >> u >> v;
                adj[u].push_back(v);
                adj[v].push_back(u);
        }
        pw[0] = mul(n, n);
        for (int k = 1; k < LG; k++) {
                pw[k] = mul(pw[k-1], pw[k-1]);
        }

        dfs(1, 0);
        sfd(1, 0);
        for (int u = 1; u <= n; u++) {
                if (dpdw[u].F) {
                        dp[0][u][dpup[u].F^1] = {1, (dpup[u].F? dpup[u].S : add(dpdw[u].S, dpup[u].S))};
                }
                else {
                        dp[0][u][0] = {1, (dpup[u].F ? 0 : dpdw[u].S)};
                }
        }
        for (int k = 1; k < LG; k++) {
                int sum = 0;
                int sa = 0, sb = 0;
                for (int u = 1; u <= n; u++) {
                        sum = add(sum, dp[k-1][u][1].F);
                        sa = add(sa, dp[k-1][u][0].S);
                        sb = add(sb, dp[k-1][u][1].S);
                }
                for (int u = 1; u <= n; u++) {
                        dp[k][u][0].F = add(dp[k][u][0].F, mul(dp[k-1][u][0].F, pw[k-1]));
                        dp[k][u][0].F = add(dp[k][u][0].F, -mul(dp[k-1][u][0].S, sum));
                        dp[k][u][0].F = add(dp[k][u][0].F, mul(dp[k-1][u][1].S, sum));
                        dp[k][u][0].S = add(mul(dp[k-1][u][0].S, sa), mul(dp[k-1][u][1].S, sb));

                        dp[k][u][1].F = add(dp[k][u][1].F, mul(dp[k-1][u][1].F, pw[k-1]));
                        dp[k][u][1].F = add(dp[k][u][1].F, -mul(dp[k-1][u][1].S, sum));
                        dp[k][u][1].F = add(dp[k][u][1].F, mul(dp[k-1][u][0].S, sum));
                        dp[k][u][1].S = add(mul(dp[k-1][u][1].S, sa), mul(dp[k-1][u][0].S, sb));
                }
        }

        bool flg = 0;
        for (int k = 0; k < LG; k++) {
                if (!(d&(1ll<<k))) continue;
                if (!flg) {
                        for (int u = 1; u <= n; u++) {
                                out[u][0] = dp[k][u][0];
                                out[u][1] = dp[k][u][1];
                        }
                        flg = 1;
                        continue;
                }
                int sum = 0;
                int sa = 0, sb = 0;
                for (int u = 1; u <= n; u++) {
                        sum = add(sum, dp[k][u][1].F);
                        sa = add(sa, dp[k][u][0].S);
                        sb = add(sb, dp[k][u][1].S);
                }
                for (int u = 1; u <= n; u++) {
                        tmp[u][0] = tmp[u][1] = {0, 0};

                        tmp[u][0].F = add(tmp[u][0].F, mul(out[u][0].F, pw[k]));
                        tmp[u][0].F = add(tmp[u][0].F, -mul(out[u][0].S, sum));
                        tmp[u][0].F = add(tmp[u][0].F, mul(out[u][1].S, sum));
                        tmp[u][0].S = add(mul(out[u][0].S, sa), mul(out[u][1].S, sb));

                        tmp[u][1].F = add(tmp[u][1].F, mul(out[u][1].F, pw[k]));
                        tmp[u][1].F = add(tmp[u][1].F, -mul(out[u][1].S, sum));
                        tmp[u][1].F = add(tmp[u][1].F, mul(out[u][0].S, sum));
                        tmp[u][1].S = add(mul(out[u][1].S, sa), mul(out[u][0].S, sb));

                        out[u][0] = tmp[u][0];
                        out[u][1] = tmp[u][1];
                }
        }
        cout << out[1][0].F << endl;
}

int main() {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        solve();
        return 0;
}

• 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