题解 ABC294Ex【K-Coloring】

有时候我们应当对自己有信心，10^9 也可能可以过。

考虑一个显而易见的容斥：枚举边集的一个大小为 m(0 \leq m \leq M) 的子集，原图中只保留该子集内的边，若有 c 个连通块，那么对答案的贡献为 K^c\times(-1)^m，时间复杂度为 O(2^M(N+M))，无法通过此题。

考虑使用 dfs，若前 i-1 条边的存在与否已经确定，那么直接枚举第 i 条边存在与否，再分别搜索。不使用路径压缩，方便删边。

考虑一个剪枝：如果一条边加入以后连通性完全没有改变，那么直接返回 0。因为如果继续搜索下去的话，对应项一定恰好抵消。

理论时间复杂度 O(2^M\log N)，实际时间复杂度 O(\frac{2^M}{\texttt{玄学}}-\texttt{玄学})，可以通过此题。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int n, m, k, p[40], u[40], v[40], f[40];
int find(int x) {
    if (x == f[x]) return x;
    return find(f[x]);
}
int dfs(int i, int c) {
    if (i == m+1) return p[c];
    int x = find(u[i]);
    int y = find(v[i]);
    if (x == y) return 0;
    int f1 = dfs(i+1, c);
    f[y] = x;
    int f2 = dfs(i+1, c-1);
    f[y] = y;
    return (f1 - f2 + 998244353) % 998244353;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    mt19937 rng;
    uniform_int_distribution<int> randombool(0, 1);
    cin >> n >> m >> k;
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = (long long) p[i-1] * k % 998244353;
    }
    for (int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i];
        if (randombool(rng) & 1) swap(u[i], v[i]);
    }
    for (int i = 1; i <= n; i++) {
        f[i] = i;
    }
    cout << dfs(1, n) << endl;
    return 0;
}

后记：赛时最大运行时间大约是 7.7s。

这次 \texttt{rank}=8，是历史最高。