QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#951583#9572. BingofractalWA 2ms102252kbC++174.8kb2025-03-26 14:34:082025-03-26 14:34:09

Judging History

This is the latest submission verdict.

  • [2025-03-26 14:34:09]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 102252kb
  • [2025-03-26 14:34:08]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second 
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define make_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 Rng(chrono::steady_clock::now().time_since_epoch().count());

template<int mod>
class Modular {
public:
    int val;
    Modular() : val(0) {}
    Modular(int new_val) : val(new_val) {}
    // Modular(long long new_val) : val(new_val % mod) {}  // AFFECTS OPERATOR* (because it has one more %)
    friend Modular operator+(const Modular& a, const Modular& b) {
        if (a.val + b.val >= mod) return a.val + b.val - mod;
        else return a.val + b.val;
    }
    friend Modular operator-(const Modular& a, const Modular& b) {
        if (a.val - b.val < 0) return a.val - b.val + mod;
        else return a.val - b.val;
    }
    friend Modular operator*(const Modular& a, const Modular& b) {
        return 1ll * a.val * b.val % mod;
    }
    friend Modular binpow(Modular a, long long n) {
        Modular res = 1;
        for (; n; n >>= 1) {
            if (n & 1) res *= a;
            a *= a;
        }
        return res;
    }
    /*
    friend Modular inv(const Modular& a) {
        Modular x, y;
        gcd(a.val, mod, x, y);
        return x;
    }
    */
    friend Modular inv(const Modular& a) {
        return binpow(a, mod - 2);
    }
    friend Modular operator^(const Modular& a, const long long& b) {
        if (b >= 0)
            return binpow(a, b % (mod - 1));
        return binpow(inv(a), (-b) % (mod - 1));
    }
    /* ALTERNATIVE INVERSE FUNCTION USING EXTENDED EUCLIDEAN ALGORITHM
    friend void gcd(int a, int b, Modular& x, Modular& y) {
        if (a == 0) {
            x = Modular(0);
            y = Modular(1);
            return;
        }
        Modular x1, y1;
        gcd(b % a, a, x1, y1);
        x = y1 - (b / a) * x1;
        y = x1;
    }
    */
    Modular operator/(const Modular& ot) const {
        return *this * inv(ot);
    }
    Modular& operator++() {
        if (val + 1 == mod) val = 0;
        else ++val;
        return *this;
    }
    Modular operator++(int) {
        Modular tmp = *this;
        ++(*this);
        return tmp;
    }
    Modular operator+() const {
        return *this;
    }
    Modular operator-() const {
        return 0 - *this;
    }
    Modular& operator+=(const Modular& ot) {
        return *this = *this + ot;
    }
    Modular& operator-=(const Modular& ot) {
        return *this = *this - ot;
    }
    Modular& operator*=(const Modular& ot) {
        return *this = *this * ot;
    }
    Modular& operator/=(const Modular& ot) {
        return *this = *this / ot;
    }
    bool operator==(const Modular& ot) const {
        return val == ot.val;
    }
    bool operator!=(const Modular& ot) const {
        return val != ot.val;
    }
    bool operator<(const Modular& ot) const {
        return val < ot.val;
    }
    bool operator>(const Modular& ot) const {
        return val > ot.val;
    }
    explicit operator int() const {
        return val;
    }
};
 
template<int mod>
istream& operator>>(istream& istr, Modular<mod>& x) {
    return istr >> x.val;
}
 
template<int mod>
ostream& operator<<(ostream& ostr, const Modular<mod>& x) {
    return ostr << x.val;
}
 
const int mod = 998244353;
using Mint = Modular<mod>;


const int N = 5e3 + 20;
const int M = 5e3;

int n, sz[N];
Mint fact[N], invf[N];
Mint ans[N], dp[N][N];
Mint s[N];
vector<int> g[N];

Mint C(int n, int k) {
    if (k < 0 || k > n) return Mint(0);
    return fact[n] * invf[n-k] * invf[k];
}

void prec(int v) {
    sz[v] = 1;
    s[v] = 1;
    for (int u : g[v]) {
        prec(u);
        sz[v] += sz[u];
        s[v] *= s[u] * C(sz[v] - 1, sz[u]);
    }
}


void dfs(int v, int p, Mint S = 1) {
    ans[v] = dp[p][v - 1] * C(n - v, sz[v] - 1);
    ans[v] *= S * s[v];
    for (int u : g[v]) {
        for (int i = 1; i <= n; ++i) {
            dp[v][i] = dp[p][i - 1] * C(n - sz[u] - i, sz[v] - sz[u] - 1);
        }
        for (int i = 1; i <= n; ++i) {
            dp[v][i] += dp[v][i - 1];
        }
        s[v] /= s[u] * C(sz[v] - 1, sz[u]);
        dfs(u, v, S * s[v]);
        s[v] *= s[u] * C(sz[v] - 1, sz[u]);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    fact[0] = 1;
    for (int i = 1; i <= M; ++i) fact[i] = fact[i - 1] * i;
    invf[M] = Mint(1) / fact[M];
    for (int i = M; i >= 1; --i) invf[i - 1] = invf[i] * i;
    cin >> n;
    for (int i = 2, f; i <= n; ++i) {
        cin >> f;
        g[f].push_back(i);
    }
    prec(1);
    dp[0][0] = 1;
    dfs(1, 0);
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << " \n"[i == n];
    }
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 102252kb

input:

4
2 2
1 3 2 4
3 1
10 10 10
1 3
20 10 30
3 4
1 1 4 5 1 4 1 9 1 9 8 10

output:

3 0 0 1

result:

wrong answer 1st numbers differ - expected: '56', found: '3'