题解：P11714 [清华集训 2014] 主旋律

· · 题解

前言

高妙，学习。

题意

给定一 n 点的简单有向图，求其强连通的生成子图数量。

n\le 15

题解

设 f_S 为以 S 为点集的强连通子图数量，所求即 f_{[n]}。

强连通是不好刻画的，不过强连通缩点之后我们得到了一个 DAG。

考虑在 DAG 计数的时候我们干了什么：枚举零度点集，得到一个恒等式。我们这里也可以这样干。设 I(S) 表示 S 内部的边数，I(S,T) 表示 S 到 T 的边数（其中 S\cap T=\varnothing）。对于一个非空的 S，枚举缩点后的图中零度点对应原图中的点集 T，对于每个划分 T=T_1\sqcup T_2\sqcup\cdots\sqcup T_k（其中 \{T_i\} 无序），其贡献为 (-1)^{k-1}\prod f(T_i)2^{\operatorname{in}(S\backslash T)+I(T,S\backslash T)}。而我们知道总共选的方案数是 2^{\operatorname{in}(S)}。因此，令 g_T 为所有的划分的 (-1)^{k}\prod f(T_i) 之和，则对于任意非空的 S 有

-2^{\operatorname{in}(S)}=\sum_{T\subseteq S,T\neq \varnothing}g_T2^{\operatorname{in}(S\backslash T)+I(T,S\backslash T)}

因为这个式子里 S 的系数是 1，容易递推求出所有 g_S。注意 I(T,S\backslash T) 可以考虑固定 T 对 S\backslash T 递推。

然后作为集合幂级数，-f=\ln g。本题中可以暴力计算。总时间复杂度 O(3^n)。

代码

cin>>n>>m;
rep(i,m)
{
    cin>>u>>v;
    --u;--v;
    ++in[1<<u|1<<v];
    ++qaq[1<<u][v];
}
rep(i,n) lg[1<<i]=i;
rep(i,n) rep(j,1<<n) if((j>>i)&1) in[j]+=in[j&~(1<<i)];
rep(i,n) rep(j,1<<n) qaq[j][i]=qaq[j&-j][i]+qaq[j&(j-1)][i];
pw2[0]=1;
rep1(i,1000) pw2[i]=pw2[i-1]*2%mod2;
rep(i,1<<n) g[i]=-pw2[in[i]];
g[0]=1;
rep(i,1<<n) if(i)
{
    if(g[i]<0) g[i]+=mod2;
    for(int j=(i+1)|i;j<(1<<n);j=(j+1)|i)
    {
        int k=j^i;
        if(k&(k-1)) qvq[k]=qvq[k&-k]+qvq[k&(k-1)];
        else qvq[k]=qaq[i][lg[k]];
        g[j]=(g[j]-g[i]*pw2[in[k]+qvq[k]])%mod2;
    }
}
rep(i,1<<n) if(i)
{
    f[i]=-g[i];
    for(int j=i&(i-1);j;j=(j-1)&i) if(j&(i&-i))
    {
        f[i]=(f[i]-f[j]*g[i^j])%mod2;
    }
    if(f[i]<0)f[i]+=mod2;
}
cout<<f[(1<<n)-1]<<'\n';