QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#662799#5139. DFS Order 2YurilyWA 3ms22272kbC++202.6kb2024-10-21 10:37:062024-10-21 10:37:07

Judging History

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

  • [2024-10-21 10:37:07]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:22272kb
  • [2024-10-21 10:37:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAX=505;
const long long MOD=998244353;
long long f[MAX][MAX],g[MAX],pred[MAX][MAX][MAX],d[MAX][MAX],A[MAX];
struct edge{
	int nxt,to;
};
int h[MAX],tot,son[MAX];
edge e[MAX*2];
int n,tmp[MAX];
void pre(int u,int fa){
	son[u]=1;
	g[u]=1; 
	int cnt=0;
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa)
			continue;
		pre(v,u);
		cnt++;
		son[u]+=son[v];
		g[u]=g[u]*g[v]%MOD;
	}
	g[u]=g[u]*A[cnt]%MOD;
}
long long quick_pow(long long x,long long y){
	long long res=1;
	while(y){
		if(y&1)
			res=res*x%MOD;
		x=x*x%MOD;
		y>>=1;
	}
	return res;
}
void pre_dp(int u,int fa){
	int cnt=0;
	long long s=1;
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa)
			continue;
		tmp[++cnt]=v;
		s=s*g[v]%MOD;
	}
	for(int i=1;i<=cnt;++i){
		pred[tmp[i]][0][0]=1;
		for(int j=1;j<=cnt;++j){
			if(j==i)
				continue;
			for(int k=1;k<=son[u]-son[tmp[i]]-1;++k){
				for(int l=j-(j>=i?1:0);l>=1;--l){
					if(k-son[tmp[j]]>=0)
						pred[tmp[i]][k][l]=(pred[tmp[i]][k][l]+pred[tmp[i]][k-son[tmp[j]]][l-1])%MOD;
				}
			}
		}
		for(int k=0;k<=son[u]-son[tmp[i]]-1;++k){
			for(int l=0;l<=cnt-1;++l){
			//	cout<<tmp[i]<<" "<<k<<" "<<l<<" "<<pred[tmp[i]][k][l]<<endl;
				d[tmp[i]][k]=(d[tmp[i]][k]+(__int128)pred[tmp[i]][k][l]*A[l]*A[cnt-1-l]*s*quick_pow(g[tmp[i]],MOD-2)%MOD)%MOD;
			}
		}		
	}
	
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa)
			continue;
		pre_dp(v,u);
	}	
}
void dp(int u,int k,int fa){
	int cnt=0;
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa)
			continue;
		tmp[++cnt]=v;
	}
	for(int i=1;i<=cnt;++i){
		for(int j=1;j<=son[u]-son[tmp[i]];++j){
			if(k-j>=0)
				f[tmp[i]][k]=(f[tmp[i]][k]+f[u][k-j]*d[tmp[i]][j-1]%MOD)%MOD;
		}
	//	cout<<"*"<<tmp[i]<<" "<<k<<" "<<f[tmp[i]][k]<<endl;
	}
	
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa)
			continue;
		dp(v,k,u);
	}
}
// ¿ì¶Á 
int read(){
	int x = 0, f = 1;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-'){
			f = -1;
		}
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = x*10+c-'0';
		c = getchar();
	}
	return x*f;
}
void addedge(int u,int v){
	e[++tot].to=v;
	e[tot].nxt=h[u];
	h[u]=tot;
} 
int main(){
	cin>>n;
	A[0]=1;
	for(int i=1;i<=n;++i)
		A[i]=A[i-1]*i%MOD;
	
	for(int i=1;i<=n-1;++i){
		int u=read(),v=read();
		addedge(u,v);
		addedge(v,u);
	}
	
	pre(1,0);
	
	d[1][0]=1;
	pre_dp(1,0);
	
	f[0][0]=1;
	f[1][1]=1;
	for(int i=1;i<=n;++i)
		dp(1,i,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");
	}
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 13972kb

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: 22272kb

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