图计数学习笔记

ini2015_____ · 2026-01-15 08:03:20 · 算法·理论

突然发现自己不会图计数，这也太倒闭了。

这里简单讲一些 n\le 15,m\le \frac {n(n-1)}2 的图计数的题目，不会涉及哈集幂科技。

无向图计数

例题 1

P10982 修改版

给你一个 n 个点 m 条边的无向图，求边集 E'\subseteq E 的个数，满足 (V,E') 是连通图。

n\le 17,m\le \frac {n(n-1)}{2}

::::info[solution] 连通性感觉是难以处理的，我们考虑单步容斥，求出来不连通的方案数。

记 f_S 为 S 导出子图连通的方案数，g_S 为 S 导出子图不连通的方案数。

我们记 E(S,T) 为 S\to T 的边数，那么显然有

f_S=2^{E(S,S)}-g_S

统计 g_S，我们不妨任意选一个点 u\in S，然后钦定集合 T 是 u 所在的联通块，于是有

g_S=\sum_{\{u\}\subseteq T\subset S}f_T2^{E(S/T,S/T)}

然后 O(3^n) 随便做了。 ::::

例题 2

ARC105F

给你一个 n 个点 m 条边的无向图，求边集 E'\subseteq E 的个数，满足 (V,E') 是连通二分图。

n\le 17,m\le \frac {n(n-1)}{2}

::::info[solution] 直接计数很困难，我们考虑保证图是一个二分图，然后容斥计算出连通的情况数。

记 S 导出子图是一个连通二分图的方案数为 f_S，是一个二分图的方案数是 g_S。

那么和上面一样，显然有

f_S=g_S-\sum_{\{u\}\subseteq T\subset S}f_Tg_{S/T}

计算 g_S，我们考虑对于一个染色方案求出所有合法方案，直接枚举左部和右部 T,S/T，那么贡献就是 2^{E(T,S/T)}。

这个时候，对于每个 k 个连通块的二分图 G，其在 g_S 中会被计算 2^k 次，那么我们最后求出来的答案需要除以 2。 :::: ::::info[code]

const int N=19,M=(1<<18)+5,mod=998244353,iv2=(mod+1)>>1;
int n,m,T;
int f[M],g[M];
int to[N],pw[M];
#define popc(x) __builtin_popcount(x)
#define lowbit(x) (x&(-x))
inline void upd(int& x){if(x>=mod)x-=mod;}
inline int E(int S,int T){
    int res=0;
    for(int i=0;i<n;i++)if(S>>i&1)res+=popc(to[i]&T);
    return res;
}
int main(){
    n=read(),m=read();
    pw[0]=1; for(int i=1;i<M;i++)upd(pw[i]=pw[i-1]*2);
    while(m--){
        int a=read()-1,b=read()-1;
        to[a]|=1<<b,to[b]|=1<<a;
    }
    for(int s=0;s<(1<<n);s++)for(int t=s;~t;t=t?((t-1)&s):(-1))upd(g[s]+=pw[E(t,s^t)]);
    for(int s=0;s<(1<<n);s++){
        f[s]=g[s]; int u=lowbit(s);
        for(int t=(s-1)&s;t;t=(t-1)&s)if((t|u)==t)
            upd(f[s]+=mod-1ll*f[t]*g[s^t]%mod);
    }
    printf("%lld\n",1ll*f[(1<<n)-1]*iv2%mod);
    return 0;
}
//  Think twice,code once

::::

有向图计数

例题 3

P6846

给你一个 n 个点 m 条边的无向图，求把所有边定向的方案数，使得定向后是一个 DAG。

n\le 17,m\le \frac {n(n-1)}{2}

::::info[solution] 考虑记 f_S 为对 S 这个点集的导出子图 G_S 定向的方案数，假如我 T(G_S) 是 S 的导出子图中度数为 1 的点的集合，显然 T(G_S) 是一个独立集，那么我们有 f_S=f_{S/T(G_S)}。

枚举 T，直接算会算重，考虑容斥，经典结论是容斥系数是 (-1)^{|T|-1}，这个证明其实非常简单啊。 :::info[证明] 假设 |T(G_S)|=k，我们计算 G 被计算到的次数。

这个其实是

\sum_{\text{\O} \subset T'\subseteq T(G_S)}(-1)^{|T'|-1}

经典二项式定理，答案为 1。

也就是每个图都只会被算一次，不会算重。 ::: 那么有

f_S=\sum_{T\subseteq S} (-1)^{|T|-1}[T \text{是独立集}]f_{S/T}

那么我们提前预处理哪些集合是独立集，然后就随便 DP 了。

时间复杂度 O(3^n)。

然后原题要多乘一个 \frac m 2。 :::: ::::info[code]

const int N=19,M=(1<<18)+5,mod=998244353,iv2=(mod+1)/2;
int n,m,T;
bool h[M]; int f[M];
#define popc(x) __builtin_popcount(x)
inline void upd(int& x){if(x>=mod)x-=mod;}
int main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int u=read()-1,v=read()-1;
        h[(1<<u)|(1<<v)]=1;
    }
    for(int i=0;i<n;i++)for(int j=0;j<(1<<n);j++)if(j>>i&1)h[j]|=h[j^(1<<i)];
    f[0]=1;
    for(int S=0;S<(1<<n);S++){
        for(int T=S;T;T=(T-1)&S)if(!h[T]){
            if(popc(T)&1)
                upd(f[S]+=f[S^T]);
            else
                upd(f[S]+=mod-f[S^T]);
        }
    }
    printf("%lld\n",1ll*f[(1<<n)-1]*m%mod*iv2%mod);
    return 0;
}
//  Think twice,code once

::::

例题 4

主旋律

给你一个 n 个点 m 条边的有向图，求边集 E'\subseteq E 的个数，满足 (V,E') 是强连通图。

n\le 15,m\le n(n-1)

::::info[solution] 考虑把图进行缩点，那么合法当且仅当缩完之后是一个单点。

我们记 f_S 为 S 的导出子图强连通的方案数，g_S 为 S 的导出子图不强连通的方案数，依旧

f_S=2^{E(S,S)}-g_S

考虑不强连通等价于缩点之后存在多个点，我们拆掉那些不是全集，且入度为 0 的点。

我们记 G 缩点后的图为 G'，那么我们需要枚举 G' 中入度为 0 的点集 T'，有容斥系数 (-1)^{|T'|-1}。

我们对于一个 T，|T'| 是不定的，于是我们把 (-1)^{|T'|-1} 放到状态里面，我们记 h_S 是把 S 缩成 k 个单点，系数为 (-1)^{k-1} 时，所有方案的系数之和。

那么有

g_S=\sum_{\text{\O} \subset T\subset S}h_T2^{E(S,S/T)}\\ h_S=f_S-\sum_{\{u\}\subseteq T\subset S}f_Th_{S/T}

然后 O(3^n) 随便做。 :::: ::::info[code]

const int mod=1e9+7;
const int N=15,M=1<<N,inf=1e9+7;
int n,m;
int f[M],g[M],h[M];
int to[N];
int pw[M];
#define popc(x) __builtin_popcount(x) 
#define lowbit(x) (x&(-x))
inline void upd(int& x){if(x>=mod)x-=mod;}
int E(int S,int T){
    int res=0;
    for(int i=0;i<n;i++)if(S>>i&1)res+=popc(to[i]&T);
    return res;
}
int main(){
    n=read(),m=read();
    pw[0]=1; for(int i=1;i<M;i++)pw[i]=pw[i-1]*2%mod; 
    while(m--){
        int u=read()-1,v=read()-1;
        to[u]|=(1<<v);
    }
    for(int s=1;s<(1<<n);s++){
        int u=lowbit(s);
        for(int t=(s-1)&s;t;t=(t-1)&s)if(t&u)
            upd(h[s]+=mod-1ll*f[t]*h[s^t]%mod);
        for(int t=s;t;t=(t-1)&s)
            upd(g[s]+=1ll*h[t]*pw[E(s,s^t)]%mod);
        upd(f[s]=pw[E(s,s)]-g[s]+mod),upd(h[s]+=f[s]); 
    }
    printf("%d\n",f[(1<<n)-1]);
    return 0;
}

::::

习题

习题 1

ABC306H

给你 m 个二元组 (x,y)，以及 n 个变量 a_i，你要给每一个二元组选择 a_x<a_y 或 a_x=a_y 或 a_x>a_y，使得存在一组解，求合法方案数。

n\le 17,m\le \frac {n(n-1)}{2}

::::info[solution] 典完了，相信大家在学会主旋律的基础上都随便秒掉这个题。

考虑题意就是无向边缩点之后是一个 DAG，我们依旧钦定独立集，记 f_S 为 S 的导出子图的定向方案，h_S 为 S 被缩成独立集后的 (-1)^{size-1}。

那么依旧

f_S=\sum_{T\subseteq S} h_Tf_{S/T}

预处理 h，然后 O(3^n) 随便做。 :::: ::::info[code]

const int N=17,M=1<<17,mod=998244353;
int n,m,T;
int to[N];
int h[M],f[M];
inline void upd(int& x){if(x>=mod)x-=mod;}
int fa[N];
int find(int x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
void merge(int x,int y){
    x=find(x),y=find(y);
    fa[x]=y;
}
int main(){
    n=read(),m=read();
    while(m--){
        int a=read()-1,b=read()-1;
        to[a]|=1<<b,to[b]|=1<<a;
    }
    for(int s=1;s<(1<<n);s++){
        for(int i=0;i<n;i++)fa[i]=i;
        for(int i=0;i<n;i++)if(s>>i&1)
            for(int j=0;j<n;j++)if(to[i]>>j&1)if(s>>j&1)
                merge(i,j);
        h[s]=mod-1;
        for(int i=0;i<n;i++)if(s>>i&1)if(fa[i]==i)h[s]=mod-h[s];
    }
    f[0]=1;
    for(int s=1;s<(1<<n);s++)
        for(int t=s;t;t=(t-1)&s)
            upd(f[s]+=1ll*h[t]*f[s^t]%mod);
    printf("%d\n",f[(1<<n)-1]);
}

::::

习题 2

重塑时光

给你一个 n 个点 m 条边的有向图 G，你有一个随机排列 p，你会在 p 上随机切 k 刀，求能够将 k+1 个连续段重排列成 p' 后，使得 p' 是 G 的一个拓扑序。

n\le 15,m\le \frac {n(n-1)}2

::::info[solution] 不难发现一个切割方案能插板法对应到序列上放了 k 个隔板，于是总的方案数就是 \binom{n+k}kn!。

不妨认为我们在给 n 个点染成 k+1 种颜色，那么对于一个染色方案，其合法当且仅当把所有同颜色的点缩成一个点之后，图是一个 DAG。

对于一个合法的染色方案，我们还可以给每个集合选择一个拓扑序，那么会有一个所有导出子图拓扑序个数之积的系数，我们要求的就是所有合法方案的系数之和。

首先可以预处理一个 h_S 表示 G_S 的拓扑序个数，可以随便 O(2^nn) DP 处理。

我们记 f_{S,k} 为把点集 S 染成 k 种颜色的方案数，g_{S,k} 为把点集 S 染成 k 种颜色且每个颜色是独立集的方案数，带有 (-1)^{k-1} 的系数。那么显然有

f_{S,k}=\sum_{\text{\O}\subset T\subseteq S,a+b=k}g_{T,a}f_{S/T,b}[E(S/T,T)=0]\\ g_{S,k}=-\sum_{\{u\}\subseteq T\subset S}h_Tg_{S/T,k-1}[E(T,S/T)=E(S/T,T)=0]

直接 DP 可以做到 O(3^nn^2)。

然后你发现瓶颈在于 f 的处理，发现 f 的转移是一个多项式卷积的形式，那么我们直接拉插处理即可，需要做 n 遍原来的问题，时间复杂度 O(3^nn)。 :::: ::::info[code]

const int N=17,M=1<<15,mod=1e9+7;
int to[N];
int h[M],g[M][N];
int fv[M],gv[M],a[N],b[N],fx[N];
int st[M];
int fac[N<<1],ifac[N<<1];
int n,m,k;
inline void upd(int& x){if(x>=mod)x-=mod;}
inline int fpow(int a,int b){
    int res=1;
    for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)res=1ll*a*res%mod;
    return res;
}
inline void initfac(){
    fac[0]=1; for(int i=1;i<(N<<1);i++)fac[i]=1ll*fac[i-1]*i%mod;
    for(int i=0;i<(N<<1);i++)ifac[i]=fpow(fac[i],mod-2);
}
inline bool E(int S,int T){return (st[S]&T);}
void Langrange(){
    for(int i=0;i<=n+1;i++){
        int v=1;
        for(int j=0;j<=n+1;j++)if(j!=i)
            v=1ll*v*(i-j+mod)%mod;
        v=1ll*fpow(v,mod-2)*fx[i]%mod;
        memset(b,0,sizeof b); b[0]=1;
        for(int j=0;j<=n+1;j++)if(j!=i){
            for(int w=n;~w;w--)
                upd(b[w+1]+=b[w]),
                b[w]=1ll*b[w]*(mod-j)%mod;
        }
        for(int j=0;j<=n+1;j++)
            upd(a[j]+=1ll*v*b[j]%mod);
    }
}
int main(){
    n=read(),m=read(),k=read();
    initfac();
    while(m--){
        int a=read()-1,b=read()-1;
        to[a]|=1<<b;
    }
    for(int s=0;s<(1<<n);s++)
        for(int i=0;i<n;i++)if(s>>i&1)
            st[s]|=to[i];
    h[0]=1;
    for(int s=1;s<(1<<n);s++)
        for(int i=0;i<n;i++)if(s>>i&1)
            if(!(to[i]&s))upd(h[s]+=h[s^(1<<i)]);
    g[0][0]=mod-1;
    for(int s=0;s<(1<<n);s++){
        int u=__lg(s&(-s));
        for(int t=s;t;t=(t-1)&s)if(t>>u&1)if(!E(t,s^t) && !E(s^t,t))
            for(int i=1;i<=n+1;i++)
                upd(g[s][i]+=mod-1ll*h[t]*g[s^t][i-1]%mod);
    }
    for(int x=0;x<=n+1;x++){
        for(int s=0;s<(1<<n);s++){
            gv[s]=0;
            for(int i=n+1;~i;i--)
                gv[s]=(1ll*gv[s]*x+g[s][i])%mod;
        }
        fv[0]=1;
        for(int s=1;s<(1<<n);s++){
            fv[s]=0;
            for(int t=s;t;t=(t-1)&s)if(!E(s^t,t))
                upd(fv[s]+=1ll*fv[s^t]*gv[t]%mod);  
        }
        fx[x]=fv[(1<<n)-1];
    }
    Langrange();
    int ans=0;
    for(int i=1;i<=k+1;i++)
        upd(ans+=1ll*a[i]*fac[k+1]%mod*ifac[k+1-i]%mod);
    ans=1ll*ans*ifac[n+k]%mod*fac[k]%mod;
    printf("%d\n",ans);
}

::::

习题 3

岁月

给你一个 n 个点 m 条边的边带权无向图 G，每条边被拆成两条有向边后得到 G'，G' 的每条边有 \frac 1 2 的概率消失，问 G' 的最小外向生成树的权值与 G 的最小生成树的权值相等的概率。

n\le15,m\le \frac{n(n-1)}2

::::info[solution] 首先考虑 C 性质，每条边的边权都相等。那么我们需要求存在一个外向生成树的概率。

不妨枚举可以成为根的集合 R，记以 R 集合可能成为根的概率为 ans_R。

考虑 R 成为根的条件：

第一个条件就是主旋律了。

第三个条件考虑所有 U/R\to R 的边必然不存在，需要乘上一个系数 2^{-E(U/R,R)}。

第二个条件考虑 DP 处理，我们记 f_S 为从 R 出发，考虑 G_S 时，可以到达 S 集合的概率，转移就是容斥，枚举一个不能到达的集合 T，有

f_S=1-\sum_{T\cap R=\text{\O},T\subseteq S}f_{S/T}2^{-E(S/T,T)}

第二个条件满足的概率就是 f_U。

不难发现三个条件相互独立，把三个概率乘在一起就是 ans_R。

直接做是 O(4^n) 的，瓶颈在于第二个条件。

考虑 DP 式子的组合意义，我们相当于初始在集合 R 的一个超集 R'，对于一个集合 T，我们可以走到 T 的超集 S，路径权值为 -2^{-E(T,S/T)}，问你走到 U 的路径权值之和。

我们把这个问题反过来，对于每个集合求出 U 到其的路径权值之和，显然可以做到 O(2^n\text{poly}(n))，然后我们只需要求一个超集和即可。

这样我们可以把 C 性质做到 O(3^n)，可以获得 64 pts，估计场上拿到 64 就很足够了。

我们把这个做法扩展到一般情况。

考虑如何判断 G' 是否合法。

分析 Kruskal 的过程，我们按照边权 w 分层考虑，对于每一层 w，我们都需要 G' 满足其每个弱连通块和 G 相同，并且每个弱连通块都需要存在外向生成树。不难发现这个条件是充要的。

我们记 ans_S 为 S 在其弱连通块内部成为根的集合的概率，按层维护，最后 \sum ans_S 即为答案。

先仿照上面 O(4^n) 的解法，对于当前的弱连通块 U 每次枚举根集合 R，计算 ans_R，然后依旧分三个 part。

这里的条件 3 依旧容易处理。

条件 1 是一个主旋律状物，记 sc_S 为点集 S 所在的弱连通块的集合。我们一次转移一个连通块，我们认为每个连通块内部是强连通的，转移是容易的。

对于条件 2，记 be_S 为 S 成为 sc_S 的根集合的概率，记 f_S 为从 R 出发，考虑 G_S 时，可以到达的根的集合为 S 的概率，转移是

f_S=[S\cap sc_R=R](be_S-\sum_{T\subset S,sc_T\cap sc_{S/T}=\text{\O}}2^{-E(sc_{S/T},T)}f_{S/T}be_T)

然后 f 对于 ans_S 的贡献就是包含了所有连通块的 S 的 f_S 之和。

那么可以做到 O(4^n)。

同理可以通过反向 DP 做到 O(3^n)。

你发现我们单层是 O(3^n) 的，全局是一个等比数列求和，还是 O(3^n)，可以通过。 :::: ::::info[code]

const int N=15,M=1<<N,K=555,mod=1e9+7,iv2=(mod+1)/2;
int n,m,T;
int to[N],cnt[M],bl[N],_bl[N],sc[M],_sc[M],ans[M];
int f[M],g[M],h[M],pw[K],dp[M],be[M];
bool fl[M],vs[M];
#define popc(x) __builtin_popcount(x) 
#define lowbit(x) (x&(-x))
#define mem(x) memset(x,0,sizeof(x))
inline void upd(int& x){if(x>=mod)x-=mod;}
void init(){pw[0]=1; for(int i=1;i<K;i++)pw[i]=1ll*pw[i-1]*iv2%mod;}
int sE(int S,int T){int res=0; for(int i=0;i<n;i++)if(S>>i&1)res+=popc(to[i]&T); return res;}
int E(int S,int T){return (cnt[S|T]-cnt[S]-cnt[T])>>1;}
struct Edge{
    int a,b,c;
    bool operator<(Edge t)const{return c<t.c;}
}e[K];
int fa[N],bel[N];
int find(int x){if(x==fa[x])return x;return fa[x]=find(fa[x]);}
void merge(int x,int y){x=find(x),y=find(y); if(x==y)return ; assert(x<n); assert(y<n);bl[y]|=bl[x]; fa[x]=y;}
void Memset(){mem(fa),mem(bel),mem(to),mem(cnt),mem(bl),mem(_bl),mem(sc),mem(_sc),mem(ans),mem(f),mem(g),mem(h),mem(fl),mem(vs),mem(dp),mem(be);}
void solve(){
    Memset();
    n=read(),m=read(); int U=(1<<n)-1;
    for(int i=1;i<=m;i++)e[i].a=read()-1,e[i].b=read()-1,e[i].c=read();
    sort(e+1,e+1+m);
    for(int i=0;i< n;i++)bl[i]=1<<i;
    for(int i=0;i< n;i++)ans[1<<i]=1,fa[i]=i;
    for(int L=1,R=0;L<=m;L=R+1){
        while(R!=m && e[R+1].c==e[L].c)++R;
        for(int i=0;i<n;i++)bel[i]=find(i);
        mem(to),mem(fl),mem(be),mem(dp),mem(f),mem(g),mem(h),mem(dp);
        for(int i=0;i<n;i++)_bl[i]=bl[i];
        for(int s=0;s<=U;s++)
            for(int i=0;i<n;i++)if(s>>i&1)
                _sc[s]|=_bl[bel[i]];
        for(int i=L;i<=R;i++)if(bel[e[i].a]!=bel[e[i].b]){
            merge(e[i].a,e[i].b);
            to[e[i].a]|=1<<e[i].b,to[e[i].b]|=1<<e[i].a;
            fl[bl[find(e[i].b)]]=1;
        }
        for(int s=0;s<=U;s++)
            cnt[s]=sE(s,s);
        for(int s=0;s<=U;s++)if(fl[s])
            for(int t=s;t;t=(t-1)&s)fl[t]=1;
        be[0]=1;
        for(int s=1;s<=U;s++)if(fl[s]){
            int u=__lg(lowbit(s)),su=_bl[bel[u]],st=s&(U^su);
            be[s]=1ll*be[st]*ans[su&s]%mod; sc[s]=0;
            for(int i=0;i<n;i++)if(s>>i&1)sc[s]|=bl[find(i)];
        }
        for(int s=1;s<=U;s++)if(fl[s]){
            int u=lowbit(s);
            for(int t=s;t;t=(t-1)&s)if((t&u)&&(_sc[s^t]&_sc[t])==0)
                upd(h[s]+=mod-1ll*f[t]*h[s^t]%mod*pw[E(_sc[s^t],t)+E(s^t,_sc[t])]%mod);
            for(int t=s;t;t=(t-1)&s)if((_sc[s^t]&_sc[t])==0)
                upd(g[s]+=1ll*h[t]*pw[E(_sc[s^t],t)]%mod);
            upd(f[s]=1-g[s]+mod); upd(h[s]+=f[s]);
        }
        for(int s=0;s<=U;s++)if(fl[s])
            if(_sc[s]==sc[s])dp[s]=1;
        for(int s=U;s;s--)if(fl[s])
            for(int t=(s-1)&s;t;t=(t-1)&s)
                if((_sc[t]&_sc[s^t])==0)
                    upd(dp[s^t]+=mod-1ll*dp[s]*pw[E(_sc[s^t],t)]%mod*be[t]%mod);
        for(int s=U;s;s--)if(fl[s])
            dp[s]=1ll*dp[s]*be[s]%mod;
        for(int s=U;s;s--)if(fl[s]){
            ans[s]=0; int qs=s^sc[s];
            for(int t=qs;~t;t=t?((t-1)&qs):-1)
                if((_sc[s]&_sc[qs^t])==0)
                    upd(ans[s]+=dp[sc[s]^t]);
            ans[s]=1ll*ans[s]*pw[E(sc[s]^_sc[s],s)]%mod*f[s]%mod%mod;
        }
    }
    int res=0; for(int i=0;i<=U;i++)upd(res+=ans[i]);
    printf("%d\n",res);
}
signed main(){
    init();
    int Testid=read(); T=read();
    while(T--)solve();
}

::::

图计数 学习笔记

无向图计数

例题 1

例题 2

有向图计数

例题 3

例题 4

习题

习题 1

习题 2

习题 3

图计数学习笔记