2025 ICPC 网络赛 第二场

这场去补考 OOP Final 了，没来打

The 2025 ICPC Asia East Continent Online Contest (II)
Date 2025/09/18
Solved

A	B	C	D	E	F	G	H	I	J	K	L	M
		O	O	O			Ø	O

H - Tree Shuffling

枚举端点 $x, y$ 并且钦定 $a_x \neq x, a_y \neq y$，中间随意。设链长为 $n$，方案数为 $n! - 2(n - 1)! + (n - 2)!$

void solve() {
    int n = read();

    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; i++) {
        int x = read(), y = read();
        g[x].eb(y), g[y].eb(x);
    }

    vector<int> d(n + 1);
    vector<vector<int>> subt(n + 1);

    auto dfs = [&](this auto&& dfs, int u, int fa) -> void {
        if (fa != 0) g[u].erase(ranges::find(g[u], fa));

        subt[u].eb(u);
        for (auto v : g[u]) {
            d[v] = d[u] + 1;
            dfs(v, u);
            for (auto p : subt[v]) {
                subt[u].eb(p);
            }
        }
    };
    dfs(1, 0);

    auto calc = [&](int n) -> Z {
        return comb.fac(n) - 2 * comb.fac(n - 1) + comb.fac(n - 2);
    };

    Z ans = 1;
    for (int lca = 1; lca <= n; lca++) {
        Z res = 0;
        for (auto v1 : g[lca]) {
            for (auto v2 : g[lca]) {
                if (v1 == v2) continue;
                for (auto u : subt[v1]) {
                    for (auto v : subt[v2]) {
                        int len = d[u] + d[v] - 2 * d[lca] + 1;
                        res += calc(len);
                    }
                }
            }
        }
        ans += res / 2;

        res = 0;
        for (int u : subt[lca]) {
            if (u == lca) continue;
            int len = d[u] - d[lca] + 1;
            res += calc(len);
        }
        ans += res;
    }
    cout << ans << '\n';
}

I - DAG Query

拉插一下就做完了

Z ask(int i, int j, int c) {
    cout << "? " << i << " " << j << " " << c << endl;
    Z res; cin >> res; return res;
}
Z qry() {
    cout << "!" << endl;
    Z res; cin >> res; return res;
}

Z LagrangeInterpolation(int n, auto x, auto y, auto k) {
    Z ans = 0;
    for (int i = 0; i < n; i++) {
        Z a = 1, b = 1;
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            a *= k - x[j];
            b *= x[i] - x[j];
        }
        ans += a * (y[i] / b);
    }
    return ans;
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
    }

    int t = 1000;
    vector<Z> x(t), y(t);
    for (int c = 1; c < t; c++) {
        x[c] = c;
        y[c] = ask(1, n, c);
    }
    Z k = qry();
    Z ans = LagrangeInterpolation(t, x, y, k);
    
    cout << ans << endl;
}

E - Zero

柿子在草稿纸上，草稿纸丢了，反正是个简单递推。

using mat = array<array<Z, 3>, 3>;
mat operator * (mat a, mat b) {
    mat c;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return c;
};

void solve() {
    int n = read();
    int m = read();

    Z C = power(Z(2), m);
    Z x = C - 1;
    vector<Z> f(5);
    f[1] = 1;
    f[2] = 0;
    for (int i = 3; i <= 4; i++) {
        f[i] = C * power(x, i - 2) - f[i - 2] * x;
    }

    if (n <= 4) {
        cout << f[n] << '\n';
        return;
    }

    mat coef {
        array<Z, 3> {-x, 0, 1},
        array<Z, 3> {1, 0, 0},
        array<Z, 3> {0, 0, x * x}
    };
    coef = power(coef, (n - 1) / 2 - 1);

    mat u;
    if (n & 1) {
        u = {
           array<Z, 3> {0, 0, f[3]},
           array<Z, 3> {0, 0, f[1]},
           array<Z, 3> {0, 0, C * power(x, 3)} 
        };
    } else {
        u = {
           array<Z, 3> {0, 0, f[4]},
           array<Z, 3> {0, 0, f[2]},
           array<Z, 3> {0, 0, C * power(x, 4)}
        };
    }

    u = coef * u;

    cout << u[0][2] << '\n';
}

D - Arcane Behemoths

柿子在草稿纸上，草稿纸丢了，反正是个简单数学。

二项式定理推一下

void solve() {
    int n = read();

    vector<int> a(n);
    for (auto &x : a) x = read();
    ranges::sort(a);

    Z ans = 0;
    Z coef1 = 1;
    Z coef2 = power(Z(2), n - 1);
    
    for (int i = 1; i <= n; i++) {
        ans += (1 + (coef1 - 1) / 2) * a[i - 1] * coef2;

        coef1 *= 3;
        coef2 /= 2;
    }

    cout << ans << '\n';
}

C - Jiaxun!

考虑下必要和充分条件的关系

其实就是 Hall 定理，和东北邀请赛那个题本质也差不多

其实二分也不是必要的

void solve() {
    int n = read();

    vector<int> f(8);
    for (int i = 1; i <= 7; i++) f[i] = read();

    int S = 0;
    for (int i = 1; i <= 7; i++) S += f[i];

    auto judge = [&](int x) -> bool {
        bool flag = 1;
        flag &= (3 * x <= S);
        flag &= (2 * x <= S - f[4]);
        flag &= (2 * x <= S - f[1]);
        flag &= (2 * x <= S - f[2]);
        flag &= (1 * x <= S - f[4] - f[2] - f[6]);
        flag &= (1 * x <= S - f[4] - f[1] - f[5]);
        flag &= (1 * x <= S - f[1] - f[2] - f[3]);
        return flag;
    };

    int ans = -1;
    for (int L = 0, R = inf; L <= R; ) {
        int mid = L + R >> 1;
        if (judge(mid)) ans = mid, L = mid + 1;
        else R = mid - 1;
    }
    cout << ans << '\n';
}