QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#238771 | #5139. DFS Order 2 | tselmegkh# | WA | 0ms | 3608kb | C++17 | 3.3kb | 2023-11-04 17:29:39 | 2023-11-04 17:29:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T>
T power(T a, long long b) {
T s = 1;
for (; b; a *= a, b >>= 1) if (b & 1) s *= a;
return s;
}
template <int mod>
struct modular {
using mint = modular;
int v;
modular() : v(0) {}
modular(long long x) {if ((v = x % mod) < 0) v += mod;}
mint operator-() const {return -v;}
mint inv() const {return power(*this, mod - 2);}
mint &operator+=(const mint &a) {if ((v += a.v) >= mod) v -= mod; return *this;}
mint &operator-=(const mint &a) {if ((v -= a.v) < 0) v += mod; return *this;}
mint &operator*=(const mint &a) {v = (int)((long long)v * a.v % mod); return *this;}
mint &operator/=(const mint &a) {return *this *= a.inv();}
friend bool operator==(const mint &a, const mint &b){return a.v == b.v;}
friend bool operator!=(const mint &a, const mint &b){return a.v != b.v;}
friend mint operator+(const mint &a, const mint &b) {return mint(a) += b;}
friend mint operator-(const mint &a, const mint &b) {return mint(a) -= b;}
friend mint operator*(const mint &a, const mint &b) {return mint(a) *= b;}
friend mint operator/(const mint &a, const mint &b) {return mint(a) /= b;}
friend istream &operator>>(istream &is, mint &a) {return is >> a.v;}
friend ostream &operator<<(ostream &os, const mint &a) {return os << a.v;}
};
const int mod = 998244353;
using mint = modular<mod>;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<mint> fac(n + 1);
fac[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = fac[i - 1] * i;
}
vector<vector<int>> adj(n);
for (int i = 0; i < n - 1; i++) {
int x, y;
cin >> x >> y;
x--, y--;
adj[x].push_back(y);
adj[y].push_back(x);
}
vector<mint> s(n, 1);
vector<int> sz(n);
auto calc = [&](auto calc, int x, int p) -> void {
int ch = 0;
sz[x] = 1;
for (int y : adj[x]) {
if (y == p) continue;
ch++;
calc(calc, y, x);
s[x] *= s[y];
sz[x] += sz[y];
}
s[x] *= fac[ch];
};
calc(calc, 0, -1);
vector dp(n, vector<mint>(n));
auto dfs = [&](auto dfs, int x, int p) -> void {
for (int y : adj[x]) {
if (y == p) continue;
mint t = 1;
for (int z : adj[x]) {
if (z == y || z == p) continue;
t *= s[z];
}
vector<mint> a(sz[x]);
a[0] = 1;
for (int z : adj[x]) {
if (z == y || z == p) continue;
for (int i = sz[x] - 1; i >= sz[z]; i--) {
a[i] += a[i - sz[z]];
}
}
mint sum = accumulate(a.begin(), a.end(), mint(0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (i - j - 1 >= sz[x]) continue;
dp[y][i] += a[i - j - 1] * (dp[x][j] / sum);
}
}
dfs(dfs, y, x);
}
};
dp[0][0] = s[0];
dfs(dfs, 0, -1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << dp[i][j] << " \n"[j == n - 1];
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
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: 3600kb
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 3 3 3 6 3 3 3 0 0 0 3 6 3 3 6 3 0 0 0 0 0 3 6 3 3 6 3 0 12 0 0 0 0 0 12 0 0 0 12 0 0 12 0 0 0 0 0 0 0 0 3 3 3 6 3 3 3 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: '3'