QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#72683 | #4811. Be Careful | yzc2005 | RE | 0ms | 0kb | C++17 | 4.8kb | 2023-01-17 21:41:40 | 2023-01-17 21:41:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int P = 998244353;
void add(int &x, int y) { (x += y) >= P && (x -= P); }
int Add(int x, int y) { return (x += y) >= P ? (x - P) : x; }
void sub(int &x, int y) { (x -= y) < 0 && (x += P); }
int Sub(int x, int y) { return (x -= y) < 0 ? (x + P) : x; }
void mul(int &x, int y) { x = 1ll * x * y % P; }
int Mul(int x, int y) { return 1ll * x * y % P; }
const int N = 205;
int n, dp[N][N], siz[N], pw[N][N], siz1[N];
vector<int> e[N];
void dfs(int u) {
if (!e[u].size()) {
siz1[u] = 1;
return;
}
int cnt_leaf = 0;
vector<int> sons;
for (auto v : e[u]) {
e[v].erase(find(e[v].begin(), e[v].end(), u));
dfs(v), cnt_leaf += !e[v].size();
siz1[u] += siz1[v];
if (e[v].size()) sons.push_back(v);
}
sort(sons.begin(), sons.end(), [&](int u, int v) {
return siz[u] < siz[v];
});
int mn = 1e9, B = -1;
for (int b = 1; b <= 18; ++b) {
int val = b;
for (auto v : sons) val += (siz[v] >= b);
if (val < mn) mn = val, B = b;
}
int lim = min((int) e[u].size(), (sons.empty() ? 0 : (siz[sons.back()] + 1)) + cnt_leaf);
vector<vector<int>> v1, v2;
vector<int> v3;
for (auto v : sons) {
if (siz[v] >= B) v2.push_back({dp[v], dp[v] + siz[v] + 1});
vector<int> sum(1 << B, 0);
for (int s = 1; s < 1 << B; ++s) {
int i = __builtin_ctz(s);
sum[s] = Add(sum[s ^ (1 << i)], dp[v][i]);
}
v1.push_back(sum);
v3.push_back(pw[n + 1][siz1[v]]);
}
for (int p = 0; p < B; ++p) {
for (int s = 0; s < 1 << p; ++s) {
int cnt = __builtin_popcount(s) + n - p + 1;
int coef = __builtin_parity(s) ? Sub(0, pw[cnt][cnt_leaf]) : pw[cnt][cnt_leaf];
for (int i = 0; i < (int) sons.size(); ++i) mul(coef, Add(v1[i][s], v3[i]));
add(dp[u][p], coef);
}
for (int i = 0; i < (int) sons.size(); ++i) sub(v3[i], dp[sons[i]][p]);
}
int cnt_large = v2.size(), cnt_small = v1.size() - cnt_large;
reverse(v1.begin() + cnt_small, v1.end());
reverse(v2.begin(), v2.end());
v3.erase(v3.begin(), v3.begin() + cnt_small);
reverse(v3.begin(), v3.end());
vector<vector<int>> f(lim + 1, vector<int>(1 << cnt_large, 0));
vector<int> vals(1 << cnt_large);
for (int s = 0; s < 1 << B; ++s) {
int coef = 1;
for (int i = 0; i < cnt_small; ++i) mul(coef, v1[i][s]);
for (int msk = 0; msk < 1 << cnt_large; ++msk) {
if (msk == 0) {
vals[msk] = coef;
} else {
int i = __builtin_ctz(msk);
vals[msk] = Mul(vals[msk ^ (1 << i)], v1[cnt_small + i][s]);
}
int c = __builtin_popcount(s);
add(f[c][msk ^ ((1 << cnt_large) - 1)], vals[msk]);
}
}
for (int p = B; p <= lim; ++p) {
vector<int> prd(1 << cnt_large, 1);
for (int s = 1; s < 1 << cnt_large; ++s) {
int i = __builtin_ctz(s);
prd[s] = Mul(prd[s ^ (1 << i)], v3[i]);
}
for (int c = 0; c <= p; ++c) {
for (int s = 0; s < 1 << cnt_large; ++s) {
int val = Mul(f[c][s], prd[s]);
if (c & 1) val = Sub(0, val);
add(dp[u][p], Mul(val, pw[c + n - p + 1][cnt_leaf]));
}
}
while (!v2.empty() && (int) v2.back().size() == p) {
v2.pop_back(), v3.pop_back(), --cnt_large;
for (auto &g : f) g.resize(1 << cnt_large);
}
for (int i = 0; i < cnt_large; ++i) sub(v3[i], v2[i][p]);
for (int c = p; ~c; --c) {
auto g = f[c];
for (int i = 0; i < cnt_large; ++i) {
int val = v2[i][p];
for (int k = 0; k < 1 << cnt_large; k += 2 << i) {
for (int j = 0; j < 1 << i; ++j) {
add(g[k | j], Mul(g[k | j | 1 << i], val));
}
}
}
for (int s = 0; s < 1 << cnt_large; ++s) add(f[c + 1][s], g[s]);
}
}
for (int i = 1; i <= n; i += 2) dp[u][i] = Sub(0, dp[u][i]);
for (int i = 0; i < n; ++i) sub(dp[u][i], dp[u][i + 1]);
siz[u] = n;
while (!dp[u][siz[u]]) --siz[u];
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
for (int x = 0; x < N; ++x) {
pw[x][0] = 1;
for (int y = 1; y < N; ++y) pw[x][y] = Mul(pw[x][y - 1], x);
}
cin >> n;
for (int i = 1; i < n; ++i) {
int x, y; cin >> x >> y;
e[x].push_back(y), e[y].push_back(x);
}
dfs(1);
for (int i = 0; i <= n; ++i) cout << dp[1][i] << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
5 1 2 1 3 2 4 2 5