题解：P6789 寒妖王

喵仔牛奶 · 2025-06-17 15:53:52 · 题解

Solution

定义 U=\{1,2,3,\cdots,n\}。

首先如果边确定的话有一个贪心：每次取出最大的边，可以加入就加入。

考虑不能加入边的情况：

• 在同一个连通块内，且连通块内已有环。
• 不同一个连通块内，且两个连通块内均已有环。

从大到小枚举边，求出 (x,y) 不能加入的方案数。下文的图都指已经加入的边构成的图。

处理出 g_S 表示 S 连通导出子图个数，h_S 表示 S 生成树个数，c_S 表示两段都在 S 内的边数。前两者使用集合幂级数 exp 和 ln 即可求出。

考虑第一种情况，枚举所在的连通块 S，例题图有环相当于不是树，故方案为 (g_S-h_S)\cdot2^{c_{U\backslash S}}。

考虑第二种情况，这种情况对每个连通块都有一下限制：

• 不能同时包含 x,y。
• 如果包含了 x 或 y，不能是树。

因此求出 f_S 表示 S 满足条件的连通导出子图数，exp 回去即可。

这样就求出不能加入的方案数，加入的概率乘边权求和即为答案。复杂度 \mathcal O(mn^22^n)。

应该有点卡常（虽然我的板子有点快，没卡常就过了）。

Code

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define ppc(x) __builtin_popcount(x)
using namespace std;
namespace math { ... }
namespace Milkcat {
    using namespace math;
    typedef long long LL;
    typedef pair<LL, LL> pii;
    const int N = 15, M = 1 << N, mod = 998244353;
    typedef mint<mod> MI;
    namespace SET {
        void exp(MI* f, MI* g, int n) { ... } // g=exp(f)
        void ln(MI* f, MI* g, int n) { ... } // g=ln(f)
    } // SPS
    int n, m, x, y, z, e[N], ct[M]; MI rs, pw[M], f[M], g[M], h[M];
    vector<tuple<int, int, int>> E;
    int main() {
        cin >> n >> m, pw[0] = 1;
        REP(i, 1, m) {
            cin >> x >> y >> z, E.pb(z, x - 1, y - 1);
            pw[i] = pw[i - 1] * 2;
        }
        fill_n(f, 1 << n, 1), m = (1 << n) - 1;
        sort(ALL(E), greater<>());
        for (auto [z, x, y] : E) {
            SET::ln(f, g, n), h[0] = 1;
            REP(i, 0, n - 1) {
                REP(S, 0, (1 << i) - 1)
                    h[S | 1 << i] = h[S] * ppc(e[i] & S);  
                SET::exp(h + (1 << i), h + (1 << i), i);
            }
            MI sm = 0;
            REP(S, 0, m) {
                if (!(S >> x & 1) || !(S >> y & 1)) continue;
                sm += (g[S] - h[S]) * pw[ct[S ^ m]], ct[S] ++, f[S] *= 2; 
            }
            REP(S, 0, m) {
                int p = (S >> x & 1), q = (S >> y & 1);
                if (p && q) { g[S] = 0; continue; }
                if (p || q) g[S] -= h[S];
            }
            SET::exp(g, g, n);
            rs += (pw[ct[m] - 1] - sm - g[m]) * z / pw[ct[m]];
            e[x] |= 1 << y, e[y] |= 1 << x;
        }
        cout << rs << '\n';
        return 0;
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    while (T --) Milkcat::main();
    return 0;
}