QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#727142#5139. DFS Order 2sslwcrWA 2ms7116kbC++142.5kb2024-11-09 11:40:372024-11-09 11:40:38

Judging History

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

  • [2024-11-09 11:40:38]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7116kb
  • [2024-11-09 11:40:37]
  • 提交

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][505],V[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][0]=1;
	int fv=1,cnt=0;
	for (int to:ed[x])
	{
		if (to==fa) continue;
		fv=fv*g[to]%mod;
		++cnt;
		for (int i=cnt;i>=1;--i) for (int j=n;j>=sz[to];--j)
		{
			w[j][i]+=w[j-sz[to]][i-1]*i%mod;
			w[j][i]>=mod?w[j][i]-=mod:0;
		}
	}
	for (int to:ed[x])
	{
		if (to==fa) continue;
		for (int i=1;i<=cnt;++i) for (int j=sz[to];j<=n;++j)
		{
			w[j][i]-=w[j-sz[to]][i-1]*i%mod;
			w[j][i]<0?w[j][i]+=mod:0;
		}
		for (int j=0;j<=n;++j) V[j]=0;
		for (int j=0;j<=n;++j) for (int i=0;i<=cnt;++i) V[j]=V[j]+w[j][i]>=mod?V[j]+w[j][i]-mod:V[j]+w[j][i];
		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]*V[k]%mod*fv%mod*V[sz[x]-1-sz[to]-k]%mod;
			if (f[to][j]>=mod) f[to][j]-=mod;
		}
		for (int i=cnt;i>=1;--i) for (int j=n;j>=sz[to];--j)
		{
			w[j][i]+=w[j-sz[to]][i-1]*i%mod;
			w[j][i]>=mod?w[j][i]-=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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 7116kb

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: 2ms
memory: 5900kb

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 4 2 2 8 2 2 4 
0 0 0 4 8 4 4 8 4 0 
0 0 0 0 4 8 4 4 8 4 
0 12 0 0 0 0 0 12 0 0 
0 12 0 0 12 0 0 0 0 0 
0 0 0 4 2 2 8 2 2 4 
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 25th numbers differ - expected: '4', found: '8'