QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#642075 | #4811. Be Careful | hhoppitree | Compile Error | / | / | C++17 | 3.7kb | 2024-10-15 09:44:48 | 2024-10-15 09:44:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 205, P = 998244353;
vector<int> G[N];
int n, dp[N][N], sdp[N][N], f[2][1 << 21], g[2][1 << 21][N], 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] = (sdp[v][i + 1] + dp[v][i]) % P;
}
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)] = (f[0][j | (1 << k)] + 1ll * f[1][j] * dp[o[i].second][k]) % P;
}
}
}
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[0][j][k] = 0;
}
g[0][(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[0][k][l]) ok = 1;
g[1][k][l] = g[0][k][l], g[0][k][l] = 0;
}
}
if (!ok) break;
for (int k = 0; k < (1 << z); ++k) {
for (int l = 0; l <= cnt; ++l) if (g[1][k][l]) {
for (int K = k, tk = -1; tk; tk = K, K = (K - 1) & k) {
for (int L = 0; L <= l; ++L) {
if (!K && !L && !((i >> j) & 1)) continue;
int mul = 1ll * g[1][k][l] * C[l][L] % P;
for (int p = 0; p < z; ++p) {
if ((K >> p) & 1) {
mul = 1ll * mul * dp[o[ps + 1 + p].second][j] % P;
}
}
g[0][k ^ K][l - L] = (g[0][k ^ K][l - L] + mul) % P;
}
}
if ((i >> j) & 1) continue;
int mul = g[1][k][l];
for (int t = 1; t <= l; ++t) mul = 1ll * mul * (n - j) % P;
for (int p = 0; p < z; ++p) {
if ((k >> p) & 1) {
mul = 1ll * mul * sdp[o[ps + 1 + p].second][j + 1] % P;
}
}
dp[x][j] = (dp[x][j] + mul) % P;
}
}
}
}
}
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]);
return 0;
}
详细
answer.code: In function ‘int main()’: answer.code:95:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 95 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ answer.code:102:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 102 | scanf("%d%d", &x, &y); | ~~~~~^~~~~~~~~~~~~~~~ /tmp/ccCHCFT8.o: in function `__tcf_0': answer.code:(.text+0x189): relocation truncated to fit: R_X86_64_PC32 against symbol `G' defined in .bss section in /tmp/ccCHCFT8.o /tmp/ccCHCFT8.o: in function `dfs(int, int)': answer.code:(.text+0x560): relocation truncated to fit: R_X86_64_PC32 against symbol `G' defined in .bss section in /tmp/ccCHCFT8.o answer.code:(.text+0x606): relocation truncated to fit: R_X86_64_PC32 against symbol `dp' defined in .bss section in /tmp/ccCHCFT8.o answer.code:(.text+0x63e): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccCHCFT8.o answer.code:(.text+0x7ae): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccCHCFT8.o answer.code:(.text+0x7b5): relocation truncated to fit: R_X86_64_PC32 against symbol `sdp' defined in .bss section in /tmp/ccCHCFT8.o answer.code:(.text+0x7c9): relocation truncated to fit: R_X86_64_PC32 against symbol `dp' defined in .bss section in /tmp/ccCHCFT8.o answer.code:(.text+0x7ea): relocation truncated to fit: R_X86_64_PC32 against symbol `sdp' defined in .bss section in /tmp/ccCHCFT8.o answer.code:(.text+0x856): relocation truncated to fit: R_X86_64_PC32 against symbol `dp' defined in .bss section in /tmp/ccCHCFT8.o answer.code:(.text+0x860): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccCHCFT8.o answer.code:(.text+0x968): additional relocation overflows omitted from the output collect2: error: ld returned 1 exit status