QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #736842 | #7895. Graph Partitioning 2 | Cu_OH_2 | WA | 622ms | 8224kb | C++20 | 3.0kb | 2024-11-12 13:38:58 | 2024-11-12 13:38:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
void solve()
{
int n, k;
cin >> n >> k;
vector<vector<int>> node(n + 1);
for (int i = 1; i <= n - 1; ++i)
{
int u, v;
cin >> u >> v;
node[u].push_back(v);
node[v].push_back(u);
}
int sq = 500;
if (k <= sq)
{
vector<vector<ll>> dp(n + 1, vector<ll>(k + 2));
vector<int> sz(n + 1);
function<void(int, int)> dfs = [&](int x, int f)
{
dp[x][1] = 1;
sz[x] = 1;
for (auto e : node[x])
{
if (e == f) continue;
vector<ll> ndp(k + 2);
dfs(e, x);
sz[x] += sz[e];
for (int i = 0; i <= min(k + 1, sz[e]); ++i)
{
for (int j = 0; j + i <= min(k + 1, sz[x]); ++j)
{
ndp[i + j] += dp[e][i] * dp[x][j] % MOD;
ndp[i + j] %= MOD;
}
}
swap(dp[x], ndp);
}
dp[x][0] = (dp[x][k] + dp[x][k + 1]) % MOD;
};
dfs(1, 0);
cout << dp[1][0] << '\n';
}
else
{
vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(n / k + 1, vector<ll>(2)));
vector<int> sz(n + 1);
function<void(int, int)> dfs = [&](int x, int f)
{
sz[x] = 1;
dp[x][0][0] = 1;
for (auto e : node[x])
{
if (e == f) continue;
vector<vector<ll>> ndp(n / k + 1, vector<ll>(2));
dfs(e, x);
for (int i = 0; i <= sz[e] / k; ++i)
{
for (int j = 0; j <= sz[x] / k; ++j)
{
for (int b1 = 0; b1 < 2; ++b1)
{
for (int b2 = 0; b2 < 2; ++b2)
{
int rem = (sz[e] - i * k) % (k + 1) + (sz[x] - j * k) % (k + 1);
rem += (b1 + b2) * (k + 1);
if (rem > k + 1) continue;
ndp[i + j][rem == k + 1] += dp[e][i][b1] * dp[x][j][b2] % MOD;
ndp[i + j][rem == k + 1] %= MOD;
}
}
}
}
sz[x] += sz[e];
swap(dp[x], ndp);
}
for (int i = 0; i <= n / k; ++i) (dp[x][i][0] += dp[x][i][1]) %= MOD;
};
dfs(1, 0);
ll ans = 0;
for (int i = 0; i <= n / k; ++i)
{
if ((n - i * k) % (k + 1) == 0) (ans += dp[1][i][0]) %= MOD;
}
cout << ans << '\n';
}
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3556kb
input:
2 8 2 1 2 3 1 4 6 3 5 2 4 8 5 5 7 4 3 1 2 1 3 2 4
output:
2 1
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 622ms
memory: 8224kb
input:
5550 13 4 10 3 9 1 10 8 3 11 8 5 10 7 9 6 13 5 9 7 2 7 5 12 4 8 8 2 4 1 3 4 7 8 2 5 6 7 4 8 2 3 11 1 11 10 1 4 9 10 8 4 3 6 5 7 6 1 10 2 11 7 11 1 17 2 14 16 13 15 17 3 15 11 1 6 13 2 13 17 4 8 14 10 8 14 14 5 9 12 14 2 12 17 17 6 15 7 14 6 2 14 2 13 2 4 8 4 3 11 7 3 14 1 11 9 13 3 5 10 6 8 3 10 14 ...
output:
0 3 112 0 1 0 1 0 0 0 1 0 1 0 0 1 0 140 0 0 0 814 1 6 1 1 2 2 0 612 0 1 0 0 0 1 1 0 0 121 4536 0 0 1718 0 0 1 0 444 1 1908 1813 3 74 0 1 0 46 0 0 0 0 0 0 0 0 0 1 0 1 1 1 239 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 1 0 0 0 48 0 2 0 0 0 1 364 0 206 0 0 76 0 1 0 0 2 0 1 2 0 0 1 0 0 4 0 1 1 0 0 1 1 1 0 0 1 1 ...
result:
wrong answer 5510th lines differ - expected: '1', found: '0'