QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#621434 | #5139. DFS Order 2 | yzj123 | WA | 0ms | 3668kb | C++20 | 2.8kb | 2024-10-08 14:30:08 | 2024-10-08 14:30:29 |
Judging History
answer
#include<bits/stdc++.h>
using i64 = long long;
#define int i64
const int mod = 998244353;
void solve() {
int n;
std::cin >> n;
std::vector<int> fac(n + 1);
fac[0] = 1;
for (int i = 1; i <= n; i ++) {
fac[i] = fac[i - 1] * i % mod;
}
std::vector<std::vector<int> > e(n + 1);
e[1].push_back(0);
for (int i = 1; i < n; i ++) {
int u, v;
std::cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
std::vector<int> siz(n + 1), inner(n + 1, 1);
auto dfs1 = [&](auto self, int u, int p) -> void {
siz[u] = 1;
for (auto v : e[u]) {
if (v == p) continue;
self(self, v, u);
siz[u] += siz[v];
inner[u] = inner[u] * inner[v] % mod;
}
inner[u] = inner[u] * fac[e[u].size() - 1] % mod;
};
dfs1(dfs1, 1, 0);
std::vector<std::vector<int> > ans(n + 1, std::vector<int>(n + 1));
std::vector<std::vector<int> > dp(n + 2, std::vector<int>(n + 2));
dp[0][1] = 1;
auto dfs = [&](auto self, int u, int p) -> void {
auto roback = dp;
for (int i = 0; i <= n; i ++) {
for (int j = n; j >= 1; j --) {
dp[i][j] = dp[i][j - 1];
}
}
int o = 1;
std::vector<int> son;
for (auto v : e[u]) {
if (v == p) continue;
o = o * inner[v] % mod;
}
for (auto v : e[u]) {
if (v == p) continue;
for (int i = n; i >= 1; i --) {
for (int j = n; j >= siz[v]; j --) {
if (dp[i - 1][j - siz[v]]) {
dp[i][j] += dp[i - 1][j - siz[v]] * i % mod;
dp[i][j] %= mod;
}
}
}
}
int opp = (int)e[u].size() - 2;
if (opp < 0) opp = 0;
o = o * fac[opp] % mod;
for (auto v : e[u]) {
if (v == p) continue;
for (int i = 1; i <= n; i ++) {
for (int j = n; j >= siz[v]; j --) {
if (dp[i - 1][j - siz[v]]) {
dp[i][j] -= dp[i - 1][j - siz[v]] * i % mod;
dp[i][j] = (dp[i][j] % mod + mod) % mod;
}
}
}
for (int i = 0; i <= n; i ++) {
for (int j = 0; j <= n; j ++) {
if (dp[j][i]) {
ans[v][i] = (ans[v][i] + dp[j][i] * o % mod) % mod;
}
}
}
auto op = dp;
for (int i = 1; i <= n; i ++) {
for (int j = 0; j <= n; j ++) {
dp[0][j] = (dp[0][j] + dp[i][j]) % mod;
dp[i][j] = 0;
}
}
self(self, v, u);
dp = op;
for (int i = n; i >= 1; i --) {
for (int j = n; j >= siz[v]; j --) {
if (dp[i - 1][j - siz[v]]) {
dp[i][j] += dp[i - 1][j - siz[v]] * i % mod;
dp[i][j] %= mod;
}
}
}
}
dp = roback;
};
dfs(dfs, 1, 0);
ans[1][1] = inner[1];
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
std::cout << (ans[i][j] + mod) % mod << ' ';
}
std::cout << '\n';
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t = 1;
// std::cin >> t;
while (t --) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3588kb
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: 3668kb
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 2 2 2 6 2 2 4 0 0 0 2 4 4 2 4 4 0 0 0 0 0 1 2 2 1 2 2 0 12 0 0 0 0 0 12 0 0 0 12 0 0 12 0 0 0 0 0 0 0 0 2 2 2 6 2 2 4 0 0 1 1 0 0 0 0 1 1 0 0 6 0 0 6 0 0 0 0 0 0 1 1 0 0 0 0 1 1
result:
wrong answer 14th numbers differ - expected: '4', found: '2'