QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#239026 | #5139. DFS Order 2 | tselmegkh# | WA | 1ms | 3476kb | C++17 | 4.0kb | 2023-11-04 18:09:11 | 2023-11-04 18:09:12 |
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 C(n + 1, vector<mint>(n + 1));
for (int i = 0; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) {
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
}
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), q(n, 1);
vector<int> sz(n), ch(n);
auto calc = [&](auto calc, int x, int p) -> void {
sz[x] = 1;
for (int y : adj[x]) {
if (y == p) continue;
ch[x]++;
calc(calc, y, x);
s[x] *= s[y];
sz[x] += sz[y];
}
for (int y : adj[x]) {
for (int z : adj[x]) {
if (z == y || z == p) continue;
q[y] *= s[z];
}
}
s[x] *= fac[ch[x]];
};
calc(calc, 0, -1);
vector dp(n, vector<mint>(n));
mint t = 1;
auto dfs = [&](auto dfs, int x, int p) -> void {
for (int y : adj[x]) {
if (y == p) continue;
int m = adj[x].size();
vector a(ch[x] + 1, vector<mint>(sz[x]));
a[0][0] = 1;
for (int z : adj[x]) {
if (z == y || z == p) continue;
for (int i = 0; i < ch[x]; i++) {
for (int j = sz[z]; j < sz[x]; j++) {
a[i + 1][j] += a[i][j - sz[z]];
}
}
}
vector<mint> b(sz[x]);
for (int i = 0; i <= ch[x]; i++) {
for (int j = 0; j < sz[x]; j++) {
b[j] += a[i][j] * C[ch[x] - 1][i];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (i - j - 1 >= sz[x]) continue;
dp[y][i] += dp[x][j] * b[i - j - 1];
}
}
t *= q[y];
dfs(dfs, y, x);
t /= q[y];
}
for (int i = 0; i < n; i++) {
dp[x][i] *= t * s[x];
}
};
dp[0][0] = 1;
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: 1ms
memory: 3424kb
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: 3476kb
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 4 6 4 6 6 2 0 0 0 2 8 6 2 8 6 0 0 0 0 0 2 8 6 2 8 6 0 12 0 0 0 0 0 12 0 0 0 12 0 0 12 0 0 0 0 0 0 0 0 2 4 6 4 6 6 2 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: '2'