QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#378334#5139. DFS Order 2osky123456WA 1ms5668kbC++142.4kb2024-04-06 11:27:562024-04-06 11:27:58

Judging History

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

  • [2024-04-06 11:27:58]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5668kb
  • [2024-04-06 11:27:56]
  • 提交

answer

// Problem: P9669 [ICPC2022 Jinan R] DFS Order 2
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9669
// Memory Limit: 512 MB
// Time Limit: 1500 ms
// start time: 2024-04-05 18:28:42

#include <bits/stdc++.h>
using ll = long long ;
const int maxn = 510; 
const int mod = 998244353 ;
int n ; 
ll fac[maxn] , dp[maxn][maxn], ans[maxn][maxn];
std::vector<int> g[maxn] ;
ll qpow(ll a,ll b) {
	ll ans = 1;
	while(b) {
		if(b&1) ans = 1ll * ans * a % mod ;
		a = 1ll * a * a % mod; 
		b >>= 1ll ;
	}
	return ans ;
}
ll inv(int x) {
	return qpow(x,mod-2) ;
}
int son[maxn] ,F[maxn] , sz[maxn] , h[maxn];
void dfs1(int u,int fa) {
	F[u] = fa , sz[u] = 1 , h[u] = 1  ;
	for(int v : g[u]) {
		if(v == fa) continue ;
		++son[u] ; 
		dfs1(v,u) ; 
		h[u] = (1ll * h[u] * h[v]) % mod ;
		sz[u] += sz[v] ;
	} 
	h[u] = (h[u] * fac[son[u]]) % mod ;
}
void dfs2(int u) {
	int m = son[u] ;
	std::vector<std::vector<int> > f(m+1,std::vector<int>(sz[u] + 1 , 0)) ;
	f[0][0] = 1 ; 
	for(int v : g[u]) {
		if(v == F[u]) continue ; 
		for(int j = m ; j ; -- j) {
			for(int k = sz[u] ; k >= sz[v] ; -- k) {
				f[j][k] = (f[j][k] + f[j - 1][k - sz[v]]) % mod ;
			}
		}
	}
	for(int v : g[u]) {
		if(v == F[u]) continue ;
		ll hx = (1ll * h[u] * inv(h[v])) % mod * inv(m)  ; 
		for(int j = 1 ; j <= m ; ++ j ) {
			for(int k = sz[v] ; k <= sz[u] ; ++k ) {
				f[j][k] = ((f[j][k] - f[j-1][k-sz[v]]) %mod  + mod) % mod ;
			}
		}
		std::vector<int> G(n+1,0) ;
		for(int j = 0 ; j < m ; ++j) 
			for(int k = 0 ; k < sz[u] ; ++k) 
				G[k+1] = (G[k+1] +1ll *  f[j][k] * hx % mod * fac[j] % mod * fac[m-j-1]) % mod ; 
		for(int j = 1 ; j <= n ; ++j) {
			for(int k = 1 ; k <= sz[u] ; ++k) {
				dp[v][j + k] = (dp[v][j+k] +1ll * dp[u][j] * G[k] % mod) % mod ; 
			}
		}
		for(int j = m ; j >= 1 ; -- j) {
			for(int k = sz[u] ; k >= sz[v] ; -- k) {
				f[j][k] = (f[j][k] + f[j-1][k-sz[v]]) % mod ;
			}
		}
		dfs2(v) ;
	}
}
signed main() {
	std::ios::sync_with_stdio(false) ;
	std::cin.tie(nullptr); 
	std::cin >> n ;
	fac[0] = 1 ;  
	for(int i=1;i<=n;++i) fac[i] = (1ll * fac[i-1] * i) % mod  ;
 	for(int i=1;i < n ; ++ i) {
 		int u,v;std::cin >> u >> v ;
 		g[u].push_back(v) ;
 		g[v].push_back(u) ; 
 	}
 	dfs1(1,0) ;
 	dp[1][1] = 1 ;
 	dfs2(1) ;
 	for(int i=1;i<=n;++i,std::cout << '\n') 
 		for(int j=1;j<=n;++j) {
 			ans[i][j] = (1ll * dp[i][j] * h[i]) % mod ;
 			std::cout << ans[i][j] << ' ' ;
 		}
 	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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