专栏文章

哈集幂 题解

YYour_Name
题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@min63l9n
此快照首次捕获于
2025/12/01 21:10
3 个月前
此快照最后确认于
2025/12/01 21:10
3 个月前
查看原文

题解

设 E(S)E(S) 为这个点集中的边数，f(S)f(S) 为只考虑 SS 内部的点和边，使得 11 可以到达 SS 中所有点的方案，特别的，当 11 不属于SS，f(S)=0f(S)=0
然后计算这个考虑单步容斥，枚举最大到达的集合，然后钦定他到不了 S−TS-T，那么所有连接 TT 和 S−TS-T 的边就已经被确定了方向，剩下的，在 S−TS-T 中的边就任意方向了。因此：
f(S)=2E(S)−∑T⊊Sf(T)∗2E(S−T)f(S)=2^{E(S)}-\sum_{T\subsetneq S}f(T)*2^{E(S-T)}
设 g(S)g(S) 为 11 能且仅能到达 SS 的方案数，那么链接 U−SU-S 和 SS 的边就已经确定了方向，剩下的，不被 SS 包含的边直接任意方向即可。
g(S)=f(S)∗2E(U−S)g(S)=f(S)*2^{E(U-S)}
然后那么答案即为 ∑1,n∈Sg(S)\sum_{1,n\in S}g(S)。
至此，我们获得了 O(3n)O(3^n) 的算法。考虑优化。
首先，我们发现下式是好算的，直接由 f(S)f(S) 即可导出。那么优化的重点就放在了上式。容易发现，后面的和式是一个卷积的形式。
于是，我们把 2E(S)2^{E(S)} 设为 h(S)h(S)，那么就变成了经典半在线卷积的形式：
f(S)=−∑T⊊Sf(T)h(S−T)+h(S)f(S) = -\sum_{T\subsetneq S}f(T)h(S-T)+h(S)
直接套上模板即可。

AC_Code

CPP
#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;
}
完结撒花。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...