QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#728721#9566. Topologyucup-team5657#WA 54ms109936kbC++142.0kb2024-11-09 15:46:132024-11-09 15:46:17

Judging History

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

  • [2024-11-09 15:46:17]
  • 评测
  • 测评结果:WA
  • 用时:54ms
  • 内存:109936kb
  • [2024-11-09 15:46:13]
  • 提交

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'