QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#634057 | #5139. DFS Order 2 | 333zhan | WA | 1ms | 3872kb | C++20 | 2.9kb | 2024-10-12 16:38:39 | 2024-10-12 16:38:44 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod = 998244353;
void solve () {
int n;
cin >> n;
vector <int> fac (n + 1);
fac[0] = 1;
for (int i = 1; i <= n; i ++) {
fac[i] = fac[i - 1] * i % mod;
}
vector <vector <int>> e (n);
for (int i = 1; i < n; i ++) {
int x, y;
cin >> x >> y;
x --; y --;
e[x].push_back (y);
e[y].push_back (x);
}
vector <int> sz (n, 1);
vector <int> dp (n, 1);
auto dfs1 = [&] (auto &&self, int x, int fa) -> void {
int son = 0;
for (auto y : e[x]) {
if (y == fa) {
continue;
}
son ++;
self (self, y, x);
sz[x] += sz[y];
dp[x] *= dp[y];
dp[x] %= mod;
}
dp[x] = dp[x] * fac[son] % mod;
};
dfs1 (dfs1, 0, -1);
vector ans (n, vector <int> (n + 1));
ans[0][1] = dp[0];
auto dfs2 = [&] (auto &&self, int x, int fa) -> void {
vector <int> g (n + 1);
g[0] = 1;
for (auto y : e[x]) {
if (y == fa) {
continue;
}
auto ng = g;
for (int i = sz[y]; i <= n; i ++) {
ng[i] += g[i - sz[y]] * dp[y];
ng[i] %= mod;
}
g = move (ng);
}
// if (x + 1 == 3) {
// for (int i = 1; i <= n; i ++) {
// cerr << g[i] << " \n"[i == n];
// }
// }
for (auto y : e[x]) {
if (y == fa) {
continue;
}
auto f = g;
for (int i = sz[y]; i <= n; i ++) {
f[i] -= dp[y] * f[i - sz[y]];
f[i] = (f[i] % mod + mod) % mod;
}
// if (y + 1 == 2) {
// for (int i = 0; i <= n; i ++) {
// cerr << f[i] << " \n"[i == n];
// }
// }
for (int ax = 1; ax < n; ax ++) {
if (ans[x][ax]) {
for (int ay = ax + 1; ay <= n; ay ++) {
ans[y][ay] += f[ay - ax - 1] * f[sz[x] - 1 - (ay - ax - 1) - sz[y]] % mod * dp[y];
ans[y][ay] %= mod;
}
}
}
}
for (int y : e[x]) {
if (y == fa) {
continue;
}
self (self, y, x);
}
};
dfs2 (dfs2, 0, -1);
for (int i = 0; i < n; i ++) {
for (int j = 1; j <= n; j ++) {
cout << ans[i][j] << " \n"[j == n];
}
}
}
signed main () {
ios::sync_with_stdio (false);
cin.tie (nullptr);
int T = 1;
// cin >> T;
while (T --) {
solve ();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3572kb
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: 3872kb
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 1 1 1 2 1 1 1 0 0 0 1 4 1 1 4 1 0 0 0 0 0 1 1 1 1 1 1 0 12 0 0 0 0 0 12 0 0 0 12 0 0 12 0 0 0 0 0 0 0 0 1 1 1 2 1 1 1 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: '1'