题解：P11734 [集训队互测 2015] 胡策的统计

· · 题解

Solution

设 [x^S]F(x) 表示 S 的生成子图个数，定义 [x^{\emptyset}]F(x)=1。求出 c_S 表示两端都在 S 中的边的个数，可以发现 [x^S]F(x)=2^{c_S}。

设 [x^S]G(x) 表示 S 的连通生成子图个数，定义 [x^{\emptyset}]G(x)=0。可以发现 \exp G=F，即 G=\ln F，做一遍 ln 即可求出 G。

设 [x^S]H(x) 表示 S 的生成子图连通值之和，可以发现

H(x)=\sum_{n\ge 0}\frac{G^n}{n!}\times n!=\sum_{n\ge 0}G^n=\frac{1}{1-G}

做一遍求逆即可求出 H。

求 ln 和求逆复杂度都是 \mathcal O(n^22^n)，故总复杂度也是这个。

Code

直接贺两个板子上去会被卡常，见 https://uoj.ac/submission/743330。

需要把两个写到一起，能够省 2n 次 FWT，就可以通过啦。

#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()
using namespace std;
namespace math { ... }
namespace Milkcat {
    using namespace math;
    typedef long long LL;
    typedef pair<LL, LL> pii;
    const int N = 20, mod = 998244353;
    typedef mint<mod> MI;
    int n, k, x, y; MI f[1 << N], g[1 << N], A[N + 1][1 << N], B[N + 1][1 << N];
    void fwt(MI* f, int n, int o) {
        REP(i, 0, n - 1) REP(j, 0, (1 << n) - 1)
            if (j >> i & 1) f[j] += f[j ^ 1 << i] * o;
    }
    int ppc(int x) { return __builtin_popcount(x); }
    int main() {
        cin >> n >> k;
        REP(i, 1, k) {
            cin >> x >> y, x --, y --;
            f[1 << x | 1 << y] += 1;
        }
        fwt(f, n, 1);
        REP(i, 0, (1 << n) - 1)
            f[i] = qpow((MI)2, f[i].val());
        int m = (1 << n);
        REP(i, 0, m - 1) A[ppc(i)][i] = f[i];
        REP(i, 0, n) fwt(A[i], n, 1);
        REP(i, 1, n) {
            REP(j, 1, i - 1) REP(S, 0, m - 1)
                B[i][S] += B[j][S] * A[i - j][S] * j;
            MI iv = (MI)1 / i;
            REP(S, 0, m - 1) B[i][S] = A[i][S] - B[i][S] * iv;
        }
        REP(i, 0, n) REP(j, 0, m - 1)
            A[i][j] = -B[i][j] + 1, B[i][j] = 0;
        REP(S, 0, m - 1) B[0][S] = A[0][S].inv();
        REP(i, 1, n) REP(j, 1, i) REP(S, 0, m - 1)
            B[i][S] -= A[j][S] * B[i - j][S] * B[0][S];
        fwt(B[n], n, -1);
        cout << B[n][m - 1] << '\n';
        return 0;
    }
}