P9036 「KDOI-04」挑战 NPC III
Alex_Wei
·
·
题解
忽略重边。
对于度数大于 $k$ 的点，若其没有被选择，则与其相连的所有点均被选择，与大小为 $k$ 矛盾。因此，度数大于 $k$ 的点一定被选择。
进一步地，因为接下来每次选择时，覆盖的边数均不超过 $k$，所以当未被覆盖的边数大于 $k ^ 2$ 时，无解。
因为 $k$ 很小，考虑爆搜。
$\mathcal{O}(k ^ 2)$ 找到任意一条未被覆盖的边，选择覆盖其左端点或右端点，至多进行 $k$ 次这样的操作。若当前所有边均被覆盖，设点覆盖集大小为 $c$，则答案加上 $\binom {n - c} {k - c}$。
看似很简单，但是这样会算重：在 $\binom {n - c} {k - c}$ 种方案中，选到我们关注的某条边的另一个端点时，可能与在该分支选择该端点的方案重复。
为避免这种情况，我们需要在找到一条边时，同时确定其两端是否在最终点覆盖集中，也就是除了被选进点覆盖集，一个点还有可能被钦定不可以选进覆盖集。
因为一条边的两端不可能同时不在点覆盖集中，所以只有以下情况：
- 两端均在点覆盖集，大小加 $2$；
- 一端在点覆盖集，另一端不在，两种情况大小均加 $1$。
复杂度递推式为 $\mathcal{T}(k) = 2\mathcal{T}(k - 1) + \mathcal{T}(k - 2)$，但是跑不满（找到一条边的某端钦定不在点覆盖集中时，另一端必须在点覆盖集中）。
时间复杂度 $\mathcal{O}(\mathcal{T}(k) k ^ 2 + m\log m)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 5;
constexpr int mod = 998244353;
int ksm(int a, int b) {
int s = 1;
while(b) {
if(b & 1) s = 1ll * s * a % mod;
a = 1ll * a * a % mod, b >>= 1;
}
return s;
}
int fc[N], ifc[N];
int bin(int n, int m) {return 1ll * fc[n] * ifc[m] % mod * ifc[n - m] % mod;}
int n, m, k, ans;
int u[N], v[N], ban[N];
set<int> e[N];
vector<int> buc;
void dfs(int rest, int cur) {
if(cur > k) return;
int e = -1;
for(auto it : buc)
if(ban[u[it]] != 1 && ban[v[it]] != 1) {
e = it;
break;
}
if(e == -1) {
ans = (ans + bin(rest, k - cur)) % mod;
return;
}
int &x = ban[u[e]], &y = ban[v[e]];
if(x == 2 && y == 2) return;
if(x == 2 && y == 0) y = 1, dfs(rest - 1, cur + 1), y = 0;
if(x == 0 && y == 2) x = 1, dfs(rest - 1, cur + 1), x = 0;
if(x == 0 && y == 0) {
x = 1, y = 1, dfs(rest - 2, cur + 2);
x = 1, y = 2, dfs(rest - 2, cur + 1);
x = 2, y = 1, dfs(rest - 2, cur + 1);
x = y = 0;
}
}
int solve() {
cin >> n >> m >> k, ans = 0;
for(int i = 1; i <= n; i++) e[i].clear(), ban[i] = 0;
for(int i = 1; i <= m; i++) {
cin >> u[i] >> v[i];
if(e[u[i]].find(v[i]) != e[u[i]].end()) i--, m--;
e[u[i]].insert(v[i]);
e[v[i]].insert(u[i]);
}
int cnt = 0;
for(int i = 1; i <= n && cnt <= k; i++)
if(e[i].size() > k - cnt) {
ban[i] = 1, cnt++;
for(int it : e[i]) e[it].erase(i);
}
if(cnt > k) return 0;
buc.clear();
for(int i = 1; i <= m; i++)
if(ban[u[i]] != 1 && ban[v[i]] != 1)
buc.push_back(i);
if(buc.size() > k * (k - cnt)) return 0;
dfs(n - cnt, cnt);
return ans;
}
int main() {
#ifdef ALEX_WEI
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
for(int i = fc[0] = 1; i < N; i++) fc[i] = 1ll * fc[i - 1] * i % mod;
ifc[N - 1] = ksm(fc[N - 1], mod - 2);
for(int i = N - 2; ~i; i--) ifc[i] = 1ll * ifc[i + 1] * (i + 1) % mod;
int T;
cin >> T;
while(T--) cout << solve() << "\n";
cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
```
每次选度数不为 $0$ 的点或其周围所有点可以做到 $\mathcal{T}(k) = 2 ^ k$。