QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#72678 | #4811. Be Careful | yzc2005 | WA | 2ms | 3656kb | C++17 | 4.7kb | 2023-01-17 21:05:11 | 2023-01-17 21:05:14 |
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_parity(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;
vector<vector<int>> f(lim + 2, 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]);
}
}
reverse(v2.begin(), v2.end());
v3.erase(v3.begin(), v3.begin() + cnt_small);
reverse(v3.begin(), v3.end());
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(), --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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3656kb
input:
5 1 2 1 3 2 4 2 5
output:
55 127 34 0 0 0
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 2ms
memory: 3532kb
input:
8 1 2 1 3 1 4 1 5 1 6 6 7 6 8
output:
69632 265534 133905 47790 12636 1944 0 0 0
result:
ok 9 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 3516kb
input:
3 1 2 2 3
output:
1 3 0 0
result:
ok 4 number(s): "1 3 0 0"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
2 1 2
output:
2 1 0
result:
ok 3 number(s): "2 1 0"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
10 1 8 1 9 6 1 2 1 1 4 1 10 1 5 7 1 3 1
output:
1755647 612579511 359376750 200038110 104287680 49974120 21379680 7771680 2177280 362880 0
result:
ok 11 numbers
Test #6:
score: 0
Accepted
time: 1ms
memory: 3520kb
input:
10 2 8 2 9 6 2 2 1 2 4 2 10 2 5 7 2 3 2
output:
114358881 100000000 0 0 0 0 0 0 0 0 0
result:
ok 11 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
10 7 8 8 9 6 5 2 1 3 4 9 10 4 5 7 6 3 2
output:
10 1 0 0 0 0 0 0 0 0 0
result:
ok 11 numbers
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 3556kb
input:
10 3 6 2 4 4 9 8 4 2 5 10 5 3 7 2 1 1 3
output:
5869541 994668763 996111453 0 0 0 0 0 0 0 0
result:
wrong answer 1st numbers differ - expected: '27510', found: '5869541'