QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#378334 | #5139. DFS Order 2 | osky123456 | WA | 1ms | 5668kb | C++14 | 2.4kb | 2024-04-06 11:27:56 | 2024-04-06 11:27:58 |
Judging History
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'