QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#642136 | #4811. Be Careful | hhoppitree | WA | 1ms | 8220kb | C++17 | 4.1kb | 2024-10-15 10:45:37 | 2024-10-15 10:45:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 205, P = 998244353;
struct MOD {
int operator ()(long long x) {
return x - (((__int128)x * 18479187002) >> 64) * P;
}
} mod;
vector<int> G[N];
int n, dp[N][N], sdp[N][N], f[2][1 << 18], g[1 << 18][N], h[1 << 18], S[1 << 18], C[N][N];
void dfs(int x, int fa = -1) {
int deg = 0, cnt = 0;
for (auto v : G[x]) {
if (v != fa) {
dfs(v, x);
for (int i = n; i >= 0; --i) {
sdp[v][i] = mod(sdp[v][i + 1] + dp[v][i]);
}
cnt += (G[v].size() == 1), ++deg;
}
}
if (!deg) {
fill(dp[x], dp[x] + n + 1, 1);
return;
}
vector< pair<int, int> > o;
for (auto v : G[x]) {
if (v != fa && G[v].size() != 1) {
int L = n;
while (!dp[v][L]) --L;
o.push_back({L, v});
}
}
sort(o.begin(), o.end());
int mn = o.size() + 1, ps = -1;
for (int i = 0; i < (int)o.size(); ++i) {
if (o[i].first + ((int)o.size() - i) < mn) {
mn = o[i].first + ((int)o.size() - i), ps = i;
}
}
int tz = (!~ps ? 0 : o[ps].first + 1);
for (int i = 0; i < 1 << tz; ++i) f[0][i] = !i;
for (int i = 0; i <= ps; ++i) {
for (int j = 0; j < 1 << tz; ++j) f[1][j] = f[0][j], f[0][j] = 0;
for (int j = (1 << (o[i].first + 1)) - 1; ~j; --j) {
for (int k = 0; k <= o[i].first; ++k) {
f[0][j | (1 << k)] = mod(f[0][j | (1 << k)] + 1ll * f[1][j] * dp[o[i].second][k]);
}
}
}
for (int i = 0; i < 1 << tz; ++i) if (f[0][i]) {
int z = o.size() - 1 - ps;
for (int j = 0; j < (1 << z); ++j) {
for (int k = 0; k <= cnt; ++k) g[j][k] = 0;
}
g[(1 << z) - 1][cnt] = f[0][i];
for (int j = 0; ; ++j) {
int ok = 0;
for (int k = 0; k < (1 << z); ++k) {
for (int l = 0; l <= cnt; ++l) {
if (g[k][l] %= P) ok = 1;
}
}
if (!ok) break;
int now = 1;
for (int l = 0; l <= cnt; ++l) {
if (l) now = mod(1ll * now * (n - j));
vector< pair<int*, int> > del;
for (int k = 0; k < (1 << z); ++k) {
h[k] = g[k][l];
del.push_back({&g[k][l], g[k][l]});
if (g[k][l] && (j >= 30 || !((i >> j) & 1))) {
del.push_back({&g[k][l], g[k][l]});
int mul = mod(1ll * g[k][l] * now);
if (!k) S[k] = 1;
else {
int pos = __builtin_ctz(k);
S[k] = mod(1ll * S[k ^ (1 << pos)] * sdp[o[ps + 1 + pos].second][j + 1]);
}
dp[x][j] = mod(dp[x][j] + 1ll * mul * S[k]);
}
}
for (int len = 2; len <= (1 << z); len <<= 1) {
int pos = o[ps + __builtin_ctz(len)].second;
for (int k = 0; k < (1 << z); k += len) {
for (int p = k; p < k + (len >> 1); ++p) {
h[p] = mod(h[p] + 1ll * h[p + (len >> 1)] * dp[pos][j]);
}
}
}
for (int k = 0; k < (1 << z); ++k) {
for (int L = 0; L <= l; ++L) {
g[k][L] = mod(g[k][L] + 1ll * h[k] * C[l][L]);
}
}
for (auto [x, y] : del) *x = mod(*x - y);
}
}
}
}
signed main() {
scanf("%d", &n);
for (int i = C[0][0] = 1; i <= n; ++i) {
for (int j = C[i][0] = 1; j <= i; ++j) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
}
}
for (int i = 1, x, y; i < n; ++i) {
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1);
for (int i = 0; i <= n; ++i) printf("%d\n", (dp[1][i] % P + P) % P);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 8204kb
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: 0ms
memory: 8200kb
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: 1ms
memory: 7904kb
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: 1ms
memory: 7912kb
input:
2 1 2
output:
2 1 0
result:
ok 3 number(s): "2 1 0"
Test #5:
score: 0
Accepted
time: 0ms
memory: 7968kb
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: 8220kb
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: 7936kb
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: 1ms
memory: 8008kb
input:
10 3 6 2 4 4 9 8 4 2 5 10 5 3 7 2 1 1 3
output:
2620 29000 102000 0 0 0 0 0 0 0 0
result:
wrong answer 1st numbers differ - expected: '27510', found: '2620'