QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#728388#9566. Topologyucup-team4938#WA 1ms22708kbC++142.3kb2024-11-09 15:04:352024-11-09 15:04:35

Judging History

你现在查看的是最新测评结果

  • [2024-11-09 15:04:35]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:22708kb
  • [2024-11-09 15:04:35]
  • 提交

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'