QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#829995 | #9576. Ordainer of Inexorable Judgment | DiaoTianhao | WA | 0ms | 3888kb | C++17 | 1.6kb | 2024-12-24 15:22:07 | 2024-12-24 15:22:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
int n;
vector<int>g[5010], f(5010), cnt(5010);
vector<long long>fac(5010), inv(5010), mul(5010);
long long dp[5010][5010];
long long fastpower(long long a, long long b) {
long long ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b /= 2;
}
return ans;
}
long long C(int n, int m) {
if(n < m) return 0;
return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
void dfs(int now) {
cnt[now] = 1;
for(auto v : g[now]) {
dfs(v);
cnt[now] += cnt[v];
}
f[now] = fac[cnt[now]];
mul[now] = cnt[now];
for(auto v : g[now]) {
mul[now] = mul[now] * mul[v] % mod;
}
f[now] = f[now] * fastpower(mul[now], mod - 2) % mod;
}
void dfs1(int now) {
for(auto v : g[now]) {
long long tmp = f[now] * mul[v] % mod * fac[cnt[now] - cnt[v] - 1] % mod * inv[cnt[now] - 1] % mod;
for(int i = 1; i <= n; i++) {
dp[v][i] = dp[now][i - 1] * tmp % mod * C(n - i + 1 - cnt[v], cnt[now] - cnt[v] - 1) % mod;
dp[v][i] = (dp[v][i] + dp[v][i - 1]) % mod;
}
dfs1(v);
}
}
int main() {
fac[0] = 1;
inv[0] = inv[1] = 1;
for(int i = 1; i <= 5000; i++) fac[i] = fac[i - 1] * i % mod;
for(int i = 2; i <= 5000; i++) inv[i] = inv[mod % i] * (mod - mod / i) % mod;
for(int i = 2; i <= 5000; i++) inv[i] = inv[i] * inv[i - 1] % mod;
cin >> n;
for(int i = 2; i <= n; i++) {
int v;
cin >> v;
g[v].push_back(i);
}
dp[1][1] = 1;
dfs(1);
dfs1(1);
for(int i = 1; i <= n; i++) {
cout << dp[i][i]*f[i] % mod *C(n - i, cnt[i] - 1) % mod << " ";
}
cout << "\n";
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3888kb
input:
3 1 0 1 1 1 2 2 1 2 2
output:
2 1 0
result:
wrong answer 1st numbers differ - expected: '1.0000000', found: '2.0000000', error = '1.0000000'