数学口胡记录

cqbzlzh / 2023-08-17 / 原文

[ABC213G] Connectivity 2

\(tag\)：计数,\(dp\),容斥

\(n\)比较小，考虑状压。

设\(dp_s\)表示只有\(s\)中的点都联通的方案数。\(g_s\)表示\(s\)的所有子图个数，若\(s\)中有\(cnt\)条边，那么\(g_s=2^{cnt}\)。

考虑计算\(dp_s\),可以用总方案减去不合法方案，对于不合法方案数枚举\(s\)的子集\(t\),钦定\(t\)中节点联通，其余\(s-t\)中的点随意。

那么有\(dp_s=g_s-\sum\limits_{t \in s}{dp_t*g_{s \oplus t}}\)

但是发现这样实际上会算重，可能一个点集在枚举中是联通的，在任意连时也是联通的。

因此考虑在枚举\(s\)时强制将某个点选入，这样就一定不会重复。取任意点答案都是一样的，如取\(1\)即可。

那么有\(dp_s=g_s-\sum\limits_{1\in t \in s}{dp_t*g_{s \oplus t}}\)

设\(up\)为全集，答案就是\(ans_i=\sum\limits_{1\in s ,i \in s}dp_s*g_{up \oplus s}\)

点击查看代码

#include<bits/stdc++.h>

using namespace std;

const int MAXN=25;
const int MAXM=405;
const int MAXS=5e5+5;

int n,m;
vector <int> G[MAXN];

#define ll long long

const ll MOD=998244353;
ll g[MAXS],dp[MAXS];
ll mul2[MAXM],ans[MAXN];

int main(){
    mul2[0]=1;
    for (int i=1;i<MAXM;i++) mul2[i]=mul2[i-1]*2ll%MOD;
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        G[u].push_back(v);G[v].push_back(u);
    }
    int up=(1<<n)-1;
    for (int mask=0;mask<=up;mask++){
        int cnt=0;
        for (int i=1;i<=n;i++){
            if (!(mask&(1<<(i-1)))) continue;
            for (const auto &j:G[i]){
                if (mask&(1<<(j-1))) cnt++;
            }
        }
        cnt/=2;
        g[mask]=mul2[cnt];
    }
    dp[0]=1;
    for (int mask=1;mask<=up;mask++){
        dp[mask]=g[mask];
        for (int mask2=mask;mask2;mask2=(mask2-1)&mask){
            if (mask2==mask) continue;
            if (mask2&1){
                dp[mask]-=dp[mask2]*g[mask^mask2]%MOD;
                dp[mask]%=MOD;dp[mask]+=MOD;dp[mask]%=MOD;         
            }
        }
    }
    for (int mask=0;mask<=up;mask++){
        for (int i=2;i<=n;i++){
            if ((mask&1)&&(mask&(1<<(i-1)))) ans[i]+=dp[mask]*g[up^mask]%MOD,ans[i]%=MOD;
        }
    }
    for (int i=2;i<=n;i++) printf("%lld\n",ans[i]);
    return 0;
}