QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
| ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
|---|---|---|---|---|---|---|---|
| #1204 | #314856 | #7864. Random Tree Parking | xcx0902 | one_god_and_two_dogs | Success! | 2024-11-20 07:55:18 | 2024-11-20 07:55:19 |
Details
Extra Test:
Wrong Answer
time: 6ms
memory: 12068kb
input:
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
output:
811480310
result:
wrong answer 1st numbers differ - expected: '214465651', found: '811480310'
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #314856 | #7864. Random Tree Parking | one_god_and_two_dogs# | AC ✓ | 634ms | 55988kb | C++14 | 939b | 2024-01-26 13:08:58 | 2024-11-20 10:03:55 |
answer
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll=long long;
constexpr ll M=2e5+10,mod=998244353;
vector<int>G[M];
ll fac[M],ifac[M],sz[M];
ll f[M][50];
ll binom(ll n,ll m){
return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
void dfs(ll x){
for(auto y:G[x])dfs(y);
for(ll i=0;i<50;++i)f[x][i]=1;
static ll g[50];
for(auto y:G[x]){
for(ll i=0;i<50;++i)
for(ll j=1;i+j<50;++j)
g[i+j-1]=(g[i+j-1]+1ll*binom(sz[x]+sz[y]+i+j-1,sz[y]+j-1)*f[x][i]%mod*f[y][j])%mod;
memcpy(f[x],g,sizeof g);
memset(g,0,sizeof g);
sz[x]+=sz[y];
}
sz[x]++;
}
void init(){
for(ll i=fac[0]=1;i<M;++i)fac[i]=fac[i-1]*i%mod;
ifac[0]=ifac[1]=1;
for(ll i=2;i<M;++i)ifac[i]=(mod-mod/i)*ifac[mod%i]%mod;
for(ll i=2;i<M;++i)ifac[i]=ifac[i]*ifac[i-1]%mod;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
init();
ll n;
cin>>n;
for(ll i=1;i<n;++i){
ll x;
cin>>x;
G[x-1].push_back(i);
}
dfs(0);
cout<<f[0][1]<<endl;
}