QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#727099#5139. DFS Order 2sslwcrWA 0ms3856kbC++142.2kb2024-11-09 11:28:422024-11-09 11:28:43

Judging History

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

  • [2024-11-09 11:28:43]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3856kb
  • [2024-11-09 11:28:42]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<string>
#include<queue>
#include<array>
#include<bits/stdc++.h>
#define mod 998244353
#define int long long
using namespace std;
//char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
	int ret,c,f=1;
	while (((c=getchar())> '9'||c< '0')&&c!='-');
	if (c=='-') f=-1,ret=0;
	else ret=c-'0';
	while ((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
	return ret*f;
}
int n,f[505][505],sz[505],fac[505],inv[505],g[505],w[505];
vector<int> ed[505];
int ksm(int x,int y)
{
	int v=1;
	while (y)
	{
		if (y&1) v=v*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return v;
}
void dfs(int x,int fa)
{
	g[x]=1;
	sz[x]=1;
	int cnt=0;
	for (int to:ed[x])
	{
		if (to==fa) continue;
		dfs(to,x);
		g[x]=g[x]*g[to]%mod;
		sz[x]+=sz[to];
		++cnt;
	}
	g[x]=g[x]*fac[cnt]%mod;
	return;
}
void dfs2(int x,int fa)
{
	memset(w,0,sizeof(w));
	w[0]=1;
	int fv=1;
	for (int to:ed[x])
	{
		if (to==fa) continue;
		fv=fv*g[to]%mod;
		for (int j=n;j>=sz[to];--j)
		{
			w[j]+=w[j-sz[to]];
			w[j]>=mod?w[j]-=mod:0;
		}
	}
	for (int to:ed[x])
	{
		if (to==fa) continue;
		for (int j=sz[to];j<=n;++j)
		{
			w[j]-=w[j-sz[to]];
			w[j]<0?w[j]+=mod:0;
		}
		fv=fv*ksm(g[to],mod-2)%mod;
		for (int j=1;j<=n;++j) for (int k=0;k<j;++k)
		{
			f[to][j]+=f[x][j-k-1]*w[k]%mod*fv%mod;
			if (f[to][j]>=mod) f[to][j]-=mod;
		}
		for (int j=n;j>=sz[to];--j)
		{
			w[j]+=w[j-sz[to]];
			w[j]>=mod?w[j]-=mod:0;
		}
		fv=fv*g[to]%mod;
	}
	for (int to:ed[x])
	{
		if (to==fa) continue;
		dfs2(to,x);
	}
	return;
}
signed main()
{
	n=read();
	for (int i=1;i<n;i++)
	{
		int x=read(),y=read();
		ed[x].emplace_back(y);
		ed[y].emplace_back(x);
	}
	fac[0]=1;
	inv[0]=1;
	for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	inv[n]=ksm(fac[n],mod-2);
	for (int i=n;i>=1;i--) inv[i-1]=inv[i]*i%mod;
	f[1][1]=1;
	dfs(1,0);
	dfs2(1,0);
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++) printf("%lld ",f[i][j]*g[i]%mod);
		printf("\n");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3856kb

input:

5
1 2
1 3
3 4
3 5

output:

4 0 0 0 0 
0 2 0 0 2 
0 2 2 0 0 
0 0 1 2 1 
0 0 1 2 1 

result:

ok 25 numbers

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3800kb

input:

10
9 2
9 6
10 5
1 5
1 6
9 3
5 8
4 3
7 9

output:

24 0 0 0 0 0 0 0 0 0 
0 0 0 2 2 2 4 2 2 2 
0 0 0 2 4 2 2 4 2 0 
0 0 0 0 2 4 2 2 4 2 
0 12 0 0 0 0 0 12 0 0 
0 12 0 0 12 0 0 0 0 0 
0 0 0 2 2 2 4 2 2 2 
0 0 6 6 0 0 0 0 6 6 
0 0 12 0 0 12 0 0 0 0 
0 0 6 6 0 0 0 0 6 6 

result:

wrong answer 14th numbers differ - expected: '4', found: '2'