QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#728721 | #9566. Topology | ucup-team5657# | WA | 54ms | 109936kb | C++14 | 2.0kb | 2024-11-09 15:46:13 | 2024-11-09 15:46:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> Pr;
#define fi first
#define se second
#define mkp make_pair
#define pb emplace_back
// #define mid ((l+r)>>1)
#define popcnt __builtin_popcountll
const ll mod = 998244353;
inline ll read(){
ll x=0, f=1; char ch=getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
return x*f;
}
inline ll lg2(ll x){ return 63^__builtin_clzll(x); }
inline ll qpow(ll a,ll b){
ll ans=1, base=a;
while(b){
if(b&1) ans=ans*base%mod;
base=base*base%mod; b>>=1;
}
return ans;
}
int f[5005][5005], n, fa[5005], C[5005][5005], dp[5005], fac[5005], inv[5005];
int idp[5005], sz[5005], d[5005][5005];
vector<int>E[5005];
void addmod(int &x){ if(x >= mod) x-=mod; }
void init(){
C[0][0]=fac[0]=1;
for(int i=1;i<=5000;i++){
C[i][0]=1; fac[i]=fac[i-1]*i%mod; inv[i]=qpow(fac[i], mod-2);
for(int j=1;j<=i;j++){
addmod(C[i][j]=C[i-1][j]+C[i-1][j-1]);
}
}
}
void procedure(){
n=read();
for(int i=2;i<=n;i++) fa[i]=read(), E[fa[i]].pb(i);
for(int i=n;i>=1;i--){
sz[i]++;
sz[fa[i]]+=sz[i];
}
for(int i=n;i>=1;i--){
dp[i]=qpow(sz[i], mod-2); idp[i]=sz[i];
for(auto j: E[i]) dp[i]=1ull*dp[i]*dp[j]%mod, idp[i]=1ull*idp[i]*idp[j]%mod;
}
f[1][1] = 1;
for(int i=1;i<=n;i++){
for(int x=1;x<=n;x++){
addmod(d[x][i] += d[x][i-1]);
addmod(f[x][i] += d[x][i]);
if(!f[x][i] || !E[x].size()) continue;
for(auto y: E[x]){
int coef = 1ull*dp[x]*idp[y]%mod*fac[sz[x]-sz[y]-1]%mod*sz[x]%mod*C[n-i-sz[y]][sz[x]-sz[y]-1]%mod*f[x][i]%mod;
addmod(d[y][i+1] += coef);
}
}
}
for(int i=1;i<=n;i++) printf("%lld ", 1ll*f[i][i]*C[n-i][sz[i]-1]%mod*dp[i]%mod*fac[sz[i]]%mod);
}
int main(){
#ifdef LOCAL
assert(freopen("input.txt","r",stdin));
assert(freopen("output.txt","w",stdout));
#endif
ll T=1;
init();
while(T--) procedure();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 39ms
memory: 104304kb
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: 47ms
memory: 104256kb
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: 39ms
memory: 104308kb
input:
2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #4:
score: -100
Wrong Answer
time: 54ms
memory: 109936kb
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:
-27027422 767629718 -100118594 258585726 194118354 -229042051 752811066 -860358596 -810819542 -928436184 354526129 -992274277 997254907 -430756397 87392872 -20076256 -610774246 88513729 886979434 301072442 539721050 -683419541 440415471 271539670 -284679602 -379547363 -432447167 77821530 -861892255 ...
result:
wrong answer 1st numbers differ - expected: '331058271', found: '-27027422'