QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#951583 | #9572. Bingo | fractal | WA | 2ms | 102252kb | C++17 | 4.8kb | 2025-03-26 14:34:08 | 2025-03-26 14:34:09 |
Judging History
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'