QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#318895#5139. DFS Order 2trsinsWA 1ms6084kbC++142.1kb2024-02-01 09:37:522024-02-01 09:37:53

Judging History

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

  • [2024-02-01 09:37:53]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6084kb
  • [2024-02-01 09:37:52]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=520;
const int mod=998244353;

int n,tot,head[N],fac[N],ifac[N],sz[N],ways[N],f[N][N],g[N],ans[N][N],son[N];

struct edge{int to,nxt;}e[N<<1];

void addedge(int u,int v){
	e[++tot].to=v;
	e[tot].nxt=head[u];
	head[u]=tot;
	return;
}

int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod,b>>=1;
	}
	return res;
}

void init(int n){
	fac[0]=ifac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
	ifac[n]=qpow(fac[n],mod-2);
	for(int i=n-1;i;i--)ifac[i]=ifac[i+1]*(i+1)%mod;
	return;
}

void dfs(int u,int fa){
	sz[u]=1,ways[u]=1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa)continue;
		dfs(v,u),son[u]++;
		sz[u]+=sz[v],ways[u]=ways[u]*ways[v]%mod;
	}ways[u]=ways[u]*fac[son[u]]%mod;
	return;
}

void dp(int u,int fa){
	for(int i=0;i<=son[u];i++)for(int j=0;j<=sz[u];j++)f[i][j]=0;
	f[0][0]=1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa)continue;
		for(int i=son[u];i;i--)for(int j=sz[v];j<=sz[u];j++)
			f[i][j]=(f[i][j]+f[i-1][j-sz[v]])%mod;
	}
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa)continue;
		for(int i=1;i<=son[u];i++)for(int j=sz[v];j<=sz[u];j++)
			f[i][j]=(f[i][j]-f[i-1][j-sz[v]]+mod)%mod;
		for(int i=0;i<=sz[u];i++)g[i]=0;
		int coef=ways[u]*qpow(ways[v],mod-2)%mod*ifac[son[u]]%mod;
		for(int i=0;i<son[u];i++)for(int j=0;j<sz[u];j++)
			g[j+1]=(g[j+1]+f[i][j]*fac[i]%mod*fac[son[u]-i-1]%mod*coef%mod)%mod;
		for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)ans[v][j]=(ans[v][j]+ans[u][i]*g[j-i]%mod)%mod;
		for(int i=son[u];i;i--)for(int j=sz[v];j<=sz[u];j++)
			f[i][j]=(f[i][j]+f[i-1][j-sz[v]])%mod;
	}
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa)continue;
		dp(v,u);
	}
	return;
}

signed main(){
	scanf("%lld",&n),init(n);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%lld%lld",&u,&v);
		addedge(u,v),addedge(v,u);
	}
	dfs(1,0),ans[1][1]=1,dp(1,0);
	for(int i=1;i<=n;i++,puts(""))for(int j=1;j<=n;j++)printf("%lld ",ans[i][j]*ways[i]%mod);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 6024kb

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: 1ms
memory: 6084kb

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 40 
0 0 0 4 4 4 4 4 4 36 
0 0 0 0 4 4 8 16 16 16 
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 40 
0 0 6 6 0 12 0 0 42 6 
0 0 12 0 0 12 0 0 72 0 
0 0 6 6 0 12 0 0 42 6 

result:

wrong answer 20th numbers differ - expected: '4', found: '40'