GPT-5.6给我的原创题目破解了！？

原题链接：138701.零昼回声：双相树谱
userId_undefined
Lin.Zikang
禁言
永恒钻石出题人

2026-08-16 16:15:44

发布于：浙江

26阅读
0回复
0点赞

U138701.零昼回声：双相树谱

//测试GPT-5.6 Sol
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MOD = 998244353;
const int G = 3;

int qpow(ll a, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return (int)r;
}

void NTT(vector<int>& a, bool invert) {
    int n = (int)a.size();

    for (int i = 1, j = 0; i < n; ++i) {
        int bit = n >> 1;

        while (j & bit) {
            j ^= bit;
            bit >>= 1;
        }

        j ^= bit;

        if (i < j)
            swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        int wn = qpow(G, (MOD - 1) / len);

        if (invert)
            wn = qpow(wn, MOD - 2);

        for (int i = 0; i < n; i += len) {
            ll w = 1;

            for (int j = 0; j < len / 2; ++j) {
                int x = a[i + j];
                int y = (int)(a[i + j + len / 2] * w % MOD);

                a[i + j] = x + y;
                if (a[i + j] >= MOD)
                    a[i + j] -= MOD;

                a[i + j + len / 2] = x - y;
                if (a[i + j + len / 2] < 0)
                    a[i + j + len / 2] += MOD;

                w = w * wn % MOD;
            }
        }
    }

    if (invert) {
        int inv_n = qpow(n, MOD - 2);

        for (int& x : a)
            x = (int)((ll)x * inv_n % MOD);
    }
}

vector<int> convolution(const vector<int>& a,
                        const vector<int>& b) {
    if (a.empty() || b.empty())
        return {};

    // 小卷积直接暴力，减少 NTT 常数
    if ((ll)a.size() * b.size() <= 256) {
        vector<int> c(a.size() + b.size() - 1, 0);

        for (int i = 0; i < (int)a.size(); ++i) {
            if (!a[i]) continue;

            for (int j = 0; j < (int)b.size(); ++j) {
                if (!b[j]) continue;

                c[i + j] =
                    (c[i + j] + (ll)a[i] * b[j]) % MOD;
            }
        }

        return c;
    }

    int need = (int)a.size() + (int)b.size() - 1;

    int len = 1;
    while (len < need)
        len <<= 1;

    vector<int> A(a.begin(), a.end());
    vector<int> B(b.begin(), b.end());

    A.resize(len);
    B.resize(len);

    NTT(A, false);
    NTT(B, false);

    for (int i = 0; i < len; ++i)
        A[i] = (int)((ll)A[i] * B[i] % MOD);

    NTT(A, true);

    A.resize(need);

    return A;
}

int n;

vector<vector<int>> g;

vector<int> va;
vector<int> vb;

vector<int> sz;
vector<int> parent_tmp;

vector<int> answer;

vector<char> removed;

/*
    在 removed[] 意义下，
    找 st 所在连通块的重心。

    全程迭代，防止链状树爆栈。
*/
int find_centroid(int st) {
    vector<int> order;
    vector<int> stk;

    stk.push_back(st);
    parent_tmp[st] = -1;

    while (!stk.empty()) {
        int u = stk.back();
        stk.pop_back();

        order.push_back(u);

        for (int v : g[u]) {
            if (removed[v])
                continue;

            if (v == parent_tmp[u])
                continue;

            parent_tmp[v] = u;
            stk.push_back(v);
        }
    }

    for (int i = (int)order.size() - 1; i >= 0; --i) {
        int u = order[i];

        sz[u] = 1;

        for (int v : g[u]) {
            if (removed[v])
                continue;

            if (parent_tmp[v] == u)
                sz[u] += sz[v];
        }
    }

    int total = (int)order.size();

    for (int u : order) {
        int mx = total - sz[u];

        for (int v : g[u]) {
            if (removed[v])
                continue;

            if (parent_tmp[v] == u)
                mx = max(mx, sz[v]);
        }

        if (mx * 2 <= total)
            return u;
    }

    return -1;
}

/*
    搜集某个重心分支。

    qa[d] = 该分支中距离重心为 d 的节点的 a 权和
    qb[d] = 该分支中距离重心为 d 的节点的 b 权和
*/
void collect_poly(int start,
                  int parent,
                  vector<int>& qa,
                  vector<int>& qb) {
    struct State {
        int u;
        int p;
        int dep;
    };

    vector<State> stk;

    stk.push_back({start, parent, 1});

    while (!stk.empty()) {
        State cur = stk.back();
        stk.pop_back();

        int u = cur.u;
        int p = cur.p;
        int dep = cur.dep;

        if ((int)qa.size() <= dep) {
            qa.resize(dep + 1, 0);
            qb.resize(dep + 1, 0);
        }

        qa[dep] += va[u];
        if (qa[dep] >= MOD)
            qa[dep] -= MOD;

        qb[dep] += vb[u];
        if (qb[dep] >= MOD)
            qb[dep] -= MOD;

        for (int v : g[u]) {
            if (removed[v] || v == p)
                continue;

            stk.push_back({v, u, dep + 1});
        }
    }
}

void add_convolution_to_answer(const vector<int>& c,
                               int sign) {
    int lim = min(n, (int)c.size());

    for (int d = 1; d < lim; ++d) {
        if (sign == 1) {
            answer[d] += c[d];

            if (answer[d] >= MOD)
                answer[d] -= MOD;
        } else {
            answer[d] -= c[d];

            if (answer[d] < 0)
                answer[d] += MOD;
        }
    }
}

void centroid_decomposition(int start) {
    int c = find_centroid(start);

    /*
        pa/pb 表示当前整个连通块，
        按照距离重心 c 的深度聚合。
    */
    vector<int> pa(1, va[c]);
    vector<int> pb(1, vb[c]);

    /*
        先减去每一个分支内部的错误贡献。
    */
    for (int v : g[c]) {
        if (removed[v])
            continue;

        vector<int> qa(1, 0);
        vector<int> qb(1, 0);

        collect_poly(v, c, qa, qb);

        vector<int> bad = convolution(qa, qb);

        add_convolution_to_answer(bad, -1);

        if (pa.size() < qa.size()) {
            pa.resize(qa.size(), 0);
            pb.resize(qb.size(), 0);
        }

        for (int d = 1; d < (int)qa.size(); ++d) {
            pa[d] += qa[d];
            if (pa[d] >= MOD)
                pa[d] -= MOD;

            pb[d] += qb[d];
            if (pb[d] >= MOD)
                pb[d] -= MOD;
        }
    }

    /*
        再加入整个连通块的卷积。
    */
    vector<int> all = convolution(pa, pb);

    add_convolution_to_answer(all, +1);

    /*
        删除重心并继续分治。
    */
    removed[c] = 1;

    for (int v : g[c]) {
        if (!removed[v])
            centroid_decomposition(v);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    va.resize(n);
    vb.resize(n);

    for (int& x : va)
        cin >> x;

    for (int& x : vb)
        cin >> x;

    g.assign(n, {});

    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;

        --u;
        --v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    sz.resize(n);
    parent_tmp.resize(n);

    removed.assign(n, 0);
    answer.assign(n, 0);

    if (n)
        centroid_decomposition(0);

    for (int d = 1; d < n; ++d) {
        if (d > 1)
            cout << ' ';

        cout << answer[d];
    }

    cout << '\n';

    return 0;
}
userId_undefined
去预览
0/2000

全部评论 1

  • userId_undefined
    Lin.Zikang
    禁言
    永恒钻石出题人

    只用了这么点时间和内存！！！

    3天前 来自 浙江

    0

热门讨论