QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#728388 | #9566. Topology | ucup-team4938# | WA | 1ms | 22708kb | C++14 | 2.3kb | 2024-11-09 15:04:35 | 2024-11-09 15:04:35 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define mod 998244353ll
#define pii pair<int,int>
#define fi first
#define se second
#define mems(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define db double
using namespace std;
const int maxn=5010;
const int inf=1e18;
inline int read(){
int 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<<3)+(x<<1)+(ch-48);ch=getchar();}
return x*f;
}
bool Mbe;
int n;
vector<int> e[maxn];
int fac[maxn],inv[maxn];
inline int ksm(int a,int b=mod-2){
int ans=1;
while(b){
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
int C(int m,int n){
if(n>m||n<0||m<0)return 0;
return fac[m]*inv[n]%mod*inv[m-n]%mod;}
int f[maxn],siz[maxn];
int pre[maxn],suf[maxn],s1[maxn],s2[maxn];
void dfs(int u){
f[u]=1;siz[u]=1;
for(int v:e[u]){
dfs(v);f[u]=f[u]*f[v]%mod*C(siz[u]+siz[v]-1,siz[v]);
siz[u]+=siz[v];
}
int mul=1,ss=0;
for(int v:e[u]){
pre[v]=mul,s1[v]=ss;
mul=mul*f[v]%mod*C(ss+siz[v],siz[v])%mod;
ss+=siz[v];
}
mul=1,ss=0;
for(int i=e[u].size()-1;~i;i--){
int v=e[u][i];
suf[v]=mul,s2[v]=ss;
mul=mul*f[v]%mod*C(ss+siz[v],siz[v])%mod;
ss+=siz[v];
}
// cout<<u<<" "<<f[u]<<"\n";
}
int dp[maxn][maxn],sum[maxn];
int ans[maxn];
void dfs1(int u){
ans[u]=dp[u][u]*f[u]%mod*C(n-u,siz[u]-1)%mod;
// cout<<u<<" "<<f[u]<<" "<<siz[u]<<" "<<dp[u][u]<<" "<<C(n-u,siz[u]-1)<<"\n";
for(int v:e[u]){
int val=pre[v]*suf[v]%mod*C(s1[v]+s2[v],s1[v])%mod;
for(int i=1;i<=n-siz[u]+1;i++){
sum[i]=(sum[i-1]+dp[u][i]*val%mod*C(n-i-siz[v],s1[v]+s2[v]))%mod;
}
for(int i=n-siz[u]+2;i<=n-siz[v]+1;i++)sum[i]=sum[i-1];
for(int i=1;i<=n-siz[v]+1;i++){
dp[v][i]=sum[i-1];
// cout<<u<<" "<<v<<" "<<i<<" "<<dp[v][i]<<"\n";
}
dfs1(v);
}
}
void work(){
n=read();
for(int i=2;i<=n;i++){
int u=read();
e[u].pb(i);
}
fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
inv[n]=ksm(fac[n]);for(int i=n-1;~i;i--)inv[i]=inv[i+1]*(i+1)%mod;
dfs(1);
dp[1][1]=1;
dfs1(1);
for(int i=1;i<=n;i++)printf("%lld ",ans[i]);
}
// \
444
bool Med;
int T;
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// cerr<<(&Mbe-&Med)/1048576.0<<" MB\n";
T=1;
while(T--)work();
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 6024kb
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: 4032kb
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: 0ms
memory: 4000kb
input:
2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 22708kb
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:
282297556 282297556 802902444 52003944 -645651243 99949392 379698918 -217973846 -605334196 187948027 -185143466 350523614 -930342735 3767113 341745768 -789956820 -890411616 -251847673 -755573495 8091665 413627025 -255504700 242763345 -597750709 -583664540 -472155289 736738892 477966098 378846875 833...
result:
wrong answer 1st numbers differ - expected: '331058271', found: '282297556'