哈集幂 题解

· · 题解

题解

设 E(S) 为这个点集中的边数，f(S) 为只考虑 S 内部的点和边，使得 1 可以到达 S 中所有点的方案，特别的，当 1 不属于S，f(S)=0

然后计算这个考虑单步容斥，枚举最大到达的集合，然后钦定他到不了 S-T，那么所有连接 T 和 S-T 的边就已经被确定了方向，剩下的，在 S-T 中的边就任意方向了。因此：

f(S)=2^{E(S)}-\sum_{T\subsetneq S}f(T)*2^{E(S-T)}

设 g(S) 为 1 能且仅能到达 S 的方案数，那么链接 U-S 和 S 的边就已经确定了方向，剩下的，不被 S 包含的边直接任意方向即可。

g(S)=f(S)*2^{E(U-S)}

然后那么答案即为 \sum_{1,n\in S}g(S)。

至此，我们获得了 O(3^n) 的算法。考虑优化。

首先，我们发现下式是好算的，直接由 f(S) 即可导出。那么优化的重点就放在了上式。容易发现，后面的和式是一个卷积的形式。

于是，我们把 2^{E(S)} 设为 h(S)，那么就变成了经典半在线卷积的形式：

f(S) = -\sum_{T\subsetneq S}f(T)h(S-T)+h(S)

直接套上模板即可。

AC_Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, l, r) for(int i = (l); i <= (r); i ++)
#define per(i, r, l) for(int i = (r); i >= (l); i --)
const int N = 21, M = (1 << N), E = 500, mod = 998244353;
int n, m, e[M], v, dp[N][M], f[N][M], g[M], res[M], ans, p2[E];
void add(int &x, int y){x += y;if(x >= mod)x -= mod;}
int p(int x){return __builtin_popcount(x);}
void FWT(int *a, int op){
    for(int k = 1; (k << 1) <= v; k <<= 1)
        for(int i = 0; i < v; i += (k << 1))
            for(int j = 0; j < k; j ++){
                a[i + j + k] += (a[i + j] * op + mod) % mod;
                a[i + j + k] %= mod;
            }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    v = 1 << n;
    p2[0] = 1;
    rep(i, 1, m){
        p2[i] = p2[i - 1] * 2 % mod;
        int u, v;
        cin >> u >> v;
        u --, v --;
        e[(1 << u) | (1 << v)] ++;
    }
    FWT(e, 1);
    rep(i, 0, v - 1)f[p(i)][i] = p2[e[i]];
    rep(i, 0, n)FWT(f[i], 1);
    rep(i, 1, n){
        rep(j, 0, v - 1)g[j] = dp[i][j];
        FWT(g, -1);
        rep(j, 0, v - 1){
            if(p(j) != i)g[j] = 0;
            else g[j] = res[j] = (p2[e[j]] * (j & 1) - g[j] + mod) % mod;
        }
        FWT(g, 1);
        rep(j, 1, n){
            if(i + j > n)continue;
            rep(k, 0, v - 1)add(dp[i + j][k], f[j][k] * g[k] % mod);
        }
    }
    rep(i, (1 << n - 1) + 1, v - 1)if(i & 1)add(ans, res[i] * p2[e[(v - 1) ^ i]] % mod);
    cout << ans;
    return 0;
}

完结撒花。