Submission #1228464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228464		Turkhuu	Star Trek (CEOI20_startrek)	C++20	100 / 100	100 ms	29000 KiB

startrek

#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
const int mod = 1e9 + 7, I = 100005;
int dp[I][2][2], dp1[I][2][2], dp2[I][2][2], win[I], win1[I], win2[I];
vector<int> adj[I];
void init(int x, int p) {
    int lose = 0;
    for (auto y : adj[x]) {
        if (y == p) continue;
        init(y, x);
        if (!win1[y]) lose++;
    }
    win1[x] = lose > 0;
    FOR(z, 0, 1) dp1[x][z][lose + !z > 0]++;
    for (auto y : adj[x]) {
        if (y == p) continue;
        FOR(z, 0, 1) FOR(q, 0, 1) (dp1[x][z][lose - !win1[y] + !q > 0] += dp1[y][z][q]) %= mod;
    }
}
void reroot(int x, int p) {
    int lose = 0, s[2][2][2]{};
    if (p) {
        if (!win2[x]) lose++;
        FOR(z, 0, 1) FOR(q, 0, 1) (s[win2[x]][z][q] += dp2[x][z][q]) %= mod;
    }
    for (auto y : adj[x]) {
        if (y == p) continue;
        if (!win1[y]) lose++;
        FOR(z, 0, 1) FOR(q, 0, 1) (s[win1[y]][z][q] += dp1[y][z][q]) %= mod;
    }
    win[x] = lose > 0;
    FOR(z, 0, 1) dp[x][z][lose + !z > 0]++;
    FOR(w, 0, 1) FOR(z, 0, 1) FOR(q, 0, 1) (dp[x][z][lose - !w + !q > 0] += s[w][z][q]) %= mod;
    for (auto y : adj[x]) {
        if (y == p) continue;
        win2[y] = lose - !win1[y] > 0;
        FOR(z, 0, 1) FOR(q, 0, 1) (((s[win1[y]][z][q] -= dp1[y][z][q]) %= mod) += mod) %= mod;
        FOR(z, 0, 1) dp2[y][z][lose - !win1[y] + !z > 0]++;
        FOR(w, 0, 1) FOR(z, 0, 1) FOR(q, 0, 1) (dp2[y][z][lose - !win1[y] - !w + !q > 0] += s[w][z][q]) %= mod;
        FOR(z, 0, 1) FOR(q, 0, 1) (s[win1[y]][z][q] += dp1[y][z][q]) %= mod;
        reroot(y, x);
    }
}
vector<vector<int>> mul(const vector<vector<int>>& a, const vector<vector<int>>& b) {
    int n = a.size(), t = b.size(), m = b[0].size();
    vector c(n, vector<int>(m));
    FOR(i, 0, n - 1) FOR(j, 0, m - 1) FOR(k, 0, t - 1) (c[i][j] += 1LL * a[i][k] * b[k][j] % mod) %= mod;
    return c;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; ll D;
    cin >> N >> D;
    FOR(i, 1, N - 1) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    init(1, 0);
    reroot(1, 0);
    vector a(2, vector<int>(2));
    int W = 0;
    FOR(i, 1, N) {
        W += win[i];
        FOR(z, 0, 1) FOR(q, 0, 1) (a[z][q] += dp[i][z][q]) %= mod;
    }
    vector b(2, vector<int>(2));
    b[0][0] = b[1][1] = 1;
    for (D--; D; D /= 2, a = mul(a, a)) if (D % 2) b = mul(b, a);
    cout << mul(mul({{N - W, W}}, b), {{dp[1][0][1]}, {dp[1][1][1]}})[0][0];
    return 6/22;
}

• 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