QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#758170 | #9566. Topology | piaoyun# | WA | 1ms | 30396kb | C++14 | 2.1kb | 2024-11-17 16:24:15 | 2024-11-17 16:24:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 5e3 + 10;
const int MOD = 998244353;
vector<int> p[MAXN];
int a[MAXN];
int dp[MAXN][MAXN];
int g[MAXN][MAXN];
int fac[MAXN];
int inv[MAXN];
int f[MAXN];
int sz[MAXN];
int fac_of_child[MAXN];
int ans[MAXN];
int N;
int quick_pow(int x, int k){
int ret = 1;
while(k){
if(k & 1) ret = ret * x % MOD;
x = x * x % MOD;
k >>= 1;
}
return ret;
}
int Comb(int n,int m){
return fac[n] * inv[m] % MOD * inv[n-m] % MOD;
}
void dfs(int u){
sz[u] = 0; f[u] = 1; fac_of_child[u] = 1;
for(auto v : p[u]){
dfs(v);
f[u] = f[u] * Comb(sz[u] + sz[v],sz[v]) % MOD * f[v] % MOD;
fac_of_child[u] = fac_of_child[u] * f[v] % MOD;
sz[u] += sz[v];
}
sz[u]++;
// cout << u << " " << f[u] << endl;
}
int getInv(int x){
return quick_pow(x, MOD - 2);
}
void calc(int u){
ans[u] = dp[u][u] * Comb(N - u, sz[u] - 1) % MOD * f[u];
int tot = N - sz[u] + 1;
for(auto v : p[u]){
int t = fac_of_child[u] * getInv(f[v]);
int other_child_sz = sz[u] - sz[v] - 1;
for(int k = 1; k <= tot; k++){
g[u][k] = dp[u][k] * t % MOD * Comb(tot - k + other_child_sz, other_child_sz) % MOD;
g[u][k] = (g[u][k] + g[u][k-1]) % MOD;
}
for(int k = tot + 1; k <= N - sz[v] + 1; k++){
g[u][k] = g[u][k-1];
}
for(int k = 1; k <= N - sz[v] + 1; k++){
dp[v][k] = g[u][k-1];
//cout << v << " " << k << " " << dp[v][k] << endl;
}
calc(v);
}
}
signed main(){
cin >> N;
for(int i = 2; i <= N; i++){
cin >> a[i];
p[a[i]].push_back(i);
}
fac[0] = inv[0] = 1;
for(int i = 1; i < MAXN; i++){
fac[i] = fac[i-1] * i % MOD;
}
inv[MAXN - 1] = quick_pow(fac[MAXN - 1], MOD - 2);
for(int i = MAXN - 2; i >= 1; i--){
inv[i] = inv[i + 1] * (i + 1) % MOD;
}
dfs(1);
dp[1][1] = 1;
calc(1);
for(int i = 1; i <= N; i++){
cout << ans[i] << " ";
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 8008kb
input:
4 1 1 2
output:
3 2 1 2
result:
ok 4 number(s): "3 2 1 2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 5856kb
input:
9 1 1 2 2 3 3 4 5
output:
672 420 180 160 152 108 120 170 210
result:
ok 9 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 5888kb
input:
2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 30396kb
input:
500 1 2 3 4 5 6 7 7 8 10 8 10 11 4 11 12 12 17 15 13 21 21 22 5 16 9 24 28 28 19 29 27 17 33 23 3 33 27 30 9 25 34 16 26 30 34 46 45 41 14 43 49 43 35 39 37 26 48 52 58 51 56 51 55 19 48 63 36 67 69 54 60 71 61 29 40 32 77 73 55 66 42 77 72 71 69 62 83 46 64 88 39 83 36 89 94 47 98 57 61 38 80 78 88...
output:
331058271 331058271 110913016431 5423731297305318 155909709328975828 163438188701960677 -63795594211897548 -55296215449673184 -9076521123480330 70656806633320842 -18356607363379210 561340974200794704 672165661611032137 777847101970246812 125064283680 -106861598066476526 -10163868541893697 -108767573...
result:
wrong answer 3rd numbers differ - expected: '107893248', found: '110913016431'