QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#425954#6102. Query on a TreeHKOI0#WA 0ms6680kbC++207.1kb2024-05-30 19:34:182024-05-30 19:34:19

Judging History

This is the latest submission verdict.

  • [2024-05-30 19:34:19]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 6680kb
  • [2024-05-30 19:34:18]
  • Submitted

answer

#include <bits/stdc++.h>
#define int long long
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int MOD = 998244353, root = 62;
typedef vector<ll> vl;

int pm(int a, int b){
    if (b == 0) return 1;
    return pm(a * a % MOD, b / 2) * (b % 2 ? a : 1) % MOD;
}
int mi(int a){
    return pm(a, MOD - 2);
}

void ntt(vl & a) {
    int n = a.size(), L = 63 - __builtin_clzll(n);
    static vl rt(2, 1);
    for (static int k = 2, s = 2; k < n; k *= 2, s++) {
        rt.resize(n);
        ll z[] = {1, pm(root, MOD >> s)};
        for (int i = k; i < k * 2; i++) rt[i] = rt[i / 2] * z[i & 1] % MOD;
    }
    vi rev(n);
    for (int i = 0; i < n; i++)
        rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
    for (int i = 0; i < n; i++)
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int k = 1; k < n; k *= 2)
        for (int i = 0; i < n; i += 2 * k) for (int j = 0; j < k; j++) {
            int z = rt[j + k] * a[i + j + k] % MOD, &ai = a[i + j];
            a[i + j + k] = ai - z + (z > ai ? MOD : 0);
            ai += (ai + z >= MOD ? z - MOD : z);
        }
}
vl conv(const vl& a, const vl& b) {
    if (a.empty() || b.empty()) return {};
    int s = a.size() + b.size() - 1, B = 64 - __builtin_clzll(s), n = 1 << B;
    int inv = mi(n);
    vl L(a), R(b), out(n);
    L.resize(n), R.resize(n); ntt(L); ntt(R);
    for (int i = 0; i < n; i++) {
        out[-i & (n - 1)] = L[i] * R[i] % MOD * inv % MOD;
    }
    ntt(out);
    return {out.begin(), out.begin() + s};
}

const int N = 2e5 + 11;
int fa[N], fi[N];
int binom(int n, int r){
    return fa[n] * fi[n - r] % MOD * fi[r] % MOD;
}

struct poly{
    vector<int> a;

    void normalise() { while (!a.empty() && a.back() == 0) a.pop_back(); }
    poly(int v) { a.push_back(v); normalise(); }
    poly(vector<int> a) : a(a) { normalise(); }
    bool is_zero() const { return a.empty(); }
    int size() const { return a.size(); }
    int deg() const { return (int) a.size() - 1; }
    void resize(int n) { a.resize(n); }
    int operator[] (int idx) const { return 0 <= idx && idx < a.size() ? a[idx] : 0; }
    int& at(int idx) { assert(0 <= idx && idx < a.size()); return a[idx]; }
    void print() const { for (auto x : a) cout << x << ' '; cout << endl; }

    poly operator* (const poly& o) const {
        return conv(a, o.a);
    }
    friend poly operator+ (const poly& a, const poly& b){
        vector<int> res(max(a.size(), b.size()));
        for (int i = 0; i < res.size(); i++) {
            res[i] = a[i] + b[i] >= MOD ? a[i] + b[i] - MOD : a[i] + b[i];
        }
        return res;
    }
    friend poly operator- (const poly& a, const poly& b){
        vector<int> res(max(a.size(), b.size()));
        for (int i = 0; i < res.size(); i++) {
            res[i] = a[i] - b[i] < 0 ? a[i] - b[i] + MOD : a[i] - b[i];
        }
        return res;
    }
    void operator-= (const poly& o) { *this = *this - o; }

    poly mod_xk(size_t k) const {
        return vector<int>{a.begin(), a.begin() + min(a.size(), k)};
    }
    poly mul_xk(size_t k) const {
        vector<int> b(k, 0); for (auto x : a) b.push_back(x);
        return b;
    }
    poly div_xk(size_t k) const {
        return size() < k ? vector<int>{} : vector<int>{a.begin() + k, a.end()};
    }
    poly substr(size_t l, size_t r) const {
        return div_xk(l).mod_xk(r - l);
    }
    poly deriv () const {
        if (size() <= 1) return {0};
        vector<int> res(size() - 1);
        for (int i = 1; i <= deg(); i++) {
            res[i - 1] = a[i] * i % MOD;
        }
        return res;
    }
    poly integr () const {
        vector<int> res(size() + 1);
        for (int i = 0; i <= deg(); i++) {
            res[i + 1] = a[i] * mi(i + 1) % MOD;
        }
        return res;
    }
    poly negx () const {
        vector<int> res(size());
        for (int i = 0; i < size(); i++) {
            res[i] = i %  2? (MOD - a[i]) % MOD : a[i];
        }
        return res;
    }
    poly x2 () const {
        if (size() == 0) return {0};
        vector<int> res(size() * 2 - 1);
        for (int i = 0; i < size(); i++) {
            res[i * 2] = a[i];
        }
        return res;
    }
    pair<poly, poly> bisect() const {
        vector<int> q0, q1;
        for (int i = 0; i < size(); i++) {
            (i % 2 ? q1 : q0).push_back(a[i]);
        }
        return {q0, q1};
    }
    poly recp(size_t k) const {
        auto q = mod_xk(k);
        if (k == 1) return vector<int>{mi(a[0])};
        auto [q0, q1] = q.negx().bisect();
        poly t = (q0 * q0 - (q1 * q1).mul_xk(1));
        poly it = t.recp((k + 1) / 2);
        return ((q0 * it).x2() + (q1 * it).x2().mul_xk(1)).mod_xk(k);
    }
    poly log(size_t n) const {
        assert(a[0] == 1);
        return (deriv().mod_xk(n) * recp(n)).integr().mod_xk(n);
    }
    poly exp(size_t n) const {
        if (is_zero()) return 1;
        assert(a[0] == 0);
        poly ans = 1;
        size_t a = 1;
        while (a < n) {
            poly C = ans.log(a * 2).div_xk(a) - substr(a, a * 2);
            ans -= (ans * C).mod_xk(a).mul_xk(a);
            a *= 2;
        }
        return ans.mod_xk(n);
    }
    poly egf() const {
        vector<int> res(size());
        for (int i = 0; i <= deg(); i++) {
            res[i] = a[i] * fi[i] % MOD;
        }
        return res;
    }
    poly ops() const {
        vector<int> res(size());
        for (int i = 0; i <= deg(); i++) {
            res[i] = a[i] * fa[i] % MOD;
        }
        return res;
    }
    poly mul_x2(int x) const {
        vector<int> res(size());
        int m2 = 1, m1 = 1;
        for (int i = 1; i <= deg(); i++) {
            m2 = m2 * m1 % MOD;
            res[i] = a[i] * m2 % MOD;
            m1 = m1 * x % MOD;
        }
        return res;
    }
};

int a[4];
void solve() {
    int m, k; cin >> m >> k;
    for (int i = 0; i <= k; i++) cin >> a[i];
    vector<int> t(m + 1);
    t[1] = 1; for (int i = 2; i <= m; i++) t[i] = pm(i, i - 2);

    a[1] = a[1] * mi(a[0]) % MOD;
    a[2] = a[2] * mi(a[0]) % MOD;

    poly S1 = poly(t).egf().mul_x2(a[1]);
    poly T = poly(t).egf().mul_x2(a[1] * mi(a[2]) % MOD);
    T = T.deriv().mul_xk(1);
    // poly T = vector<int>{0, 1};
    // (((1 - T).log(m + 1) * (-1) - T - T * T * mi(2)) * mi(2)).ops().print();
    poly S2 = (T * T * T * mi(6) + T * T * T * T * mi(8)).mod_xk(m + 1).mul_x2(a[2]);
    // poly S2 = (((1 - T).log(m + 1) * (-1) - T - T * T * mi(2)) * mi(2)).mul_x2(a[2]);
    T.print(); (S2.ops() * 2).print();
    poly S = S1 + S2;
    poly ans = S.exp(m + 1).mul_x2(a[0]).ops();
    for (int i = 2; i <= m; i++) {
        cout << ans[i] << ' ';
    }
    cout << '\n';
}

signed main() {
    fa[0] = 1; for (int i = 1; i < N; i++) fa[i] = fa[i - 1] * i % MOD;
    fi[N - 1] = mi(fa[N - 1]); for (int i = N - 2; i >= 0; i--) fi[i] = fi[i + 1] * (i + 1) % MOD;
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 6680kb

input:

7
1 2
1 3
1 5
2 7
4 6
4 7
6
1 1
2 1 2
4 1 2 3 4
5 1 2 4 6 7
6 1 2 3 4 5 6
7 1 2 3 4 5 6 7

output:

0 1 

3 23 416 17149 1578704 319498663 

result:

wrong answer 4th numbers differ - expected: '10', found: '23'