QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#658720#5139. DFS Order 2juan_123RE 0ms0kbC++142.1kb2024-10-19 17:28:132024-10-19 17:28:13

Judging History

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

  • [2024-10-19 17:28:13]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-19 17:28:13]
  • 提交

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 = i+1;j>=1;j--){
			for(int k = s[i];j<=sz[now];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<=sz[now];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<=sz[now];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 = s[l];k<=sz[now];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
1 3
3 4
3 5
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

5
1 2
1 3
3 4
3 5

output:


result: