QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#658668#5139. DFS Order 2juan_123WA 1ms5888kbC++142.1kb2024-10-19 17:18:022024-10-19 17:18:02

Judging History

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

  • [2024-10-19 17:18:02]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5888kb
  • [2024-10-19 17:18:02]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int qp(int p,int q){
	int ans = 1,pro = p;
	while(q){
		if(q&1)ans = ans*pro%mod;
		pro = pro*pro%mod;q>>=1;
	}
	return ans;
}
int dp[505][505],sz[505];
vector<int>p[505];
int jie[505];
int f[505][505],g[505];
int n;
void dfs1(int now,int fa){
	g[now] = 1;
	sz[now]=1;
	int tt =0 ;
	for(auto x:p[now])if(x!=fa){
		dfs1(x,now);
		sz[now]+=sz[x];
		++tt;
		g[now] = g[now]*g[x]%mod;
	}
	g[now] = g[now]*jie[tt]%mod;
}

void dfs(int now,int fa){
	vector<int>s;//s.push_back(0);
	int pro = 1;
	for(auto x:p[now]){
		if(x!=fa)s.push_back(sz[x]),pro = pro*g[x]%mod;
	}
	for(int i =0;i<s.size();i++)for(int j =0;j<=sz[now];j++)f[i][j]=0;
	f[0][0] = 1;
	for(int i =0;i<s.size();i++){
		for(int j = s.size();j>=1;j--){
			for(int k = n;k>=s[i];k--){
				f[j][k] = (f[j][k]+f[j-1][k-s[i]])%mod;
			}
		}
	}

	int l =0;
	
	for(auto x:p[now]){
		if(x==fa)continue;
		for(int j = 1;j<=s.size();j++){
			for(int k = s[l];k<=n;k++){
				f[j][k] = (f[j][k]-f[j-1][k-s[l]]+mod)%mod;
			}
		}
		int p = pro*qp(g[x],mod-2)%mod;
		for(int i = 1;i<=n;i++){
			for(int j = 0;j<s.size();j++){
				for(int k = 0;k<=n;k++){
			//		cout <<" " << i+k+1 << " " << f[j][k] <<" " << dp[now][i] << " " << jie[j]*jie[s.size()-j-1]*p%mod << endl;
					dp[x][i+k+1] = (dp[x][i+k+1]+f[j][k]*dp[now][i]%mod*jie[j]%mod*jie[s.size()-j-1]*p%mod)%mod;
				}
			}
		}
		for(int j = s.size();j>=1;j--){
			for(int k = n;k>=s[l];k--){
				f[j][k] = (f[j][k]+f[j-1][k-s[l]])%mod;
			}
		}
		++l;
	}
	for(auto x:p[now])if(x!=fa)dfs(x,now);
}
signed main(){
	cin >> n;
	jie[0]=1;for(int i = 1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
	for(int i = 1;i<n;i++){
		int a,b;cin >>a  >> b;
		p[a].push_back(b),p[b].push_back(a);
	}
	dp[1][1] = 1;
	dfs1(1,1);
//	for(int i = 1;i<=n;i++)cout << " "  << g[i];cout << endl;
	dfs(1,1);
	for(int i =1;i<=n;i++){
		for(int j = 1;j<=n;j++)dp[i][j]=dp[i][j]*g[i]%mod;
	}
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=n;j++)cout << dp[i][j] << " ";
		cout << endl;
	}
	return 0;
}/*
5
1 2
2 3
3 4
4 5
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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 6 
0 0 0 4 4 4 4 4 4 2 
0 0 0 0 4 4 4 4 4 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 6 
0 0 6 6 0 0 0 0 12 6 
0 0 12 0 0 12 0 0 0 0 
0 0 6 6 0 0 0 0 12 6 

result:

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