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

· · 题解

给一个 n 个点 m 条边的简单有向图 G，n\le 15,m\le n(n-1)。

  1. DAG 子图计数

​ 直接定义 f_S 表示点集为 S 的DAG子图数量，考虑DAG的性质，即我们可以每次挑出入度为 0 的点删掉，于是就可以划分了，枚举子集 T 表示挑出来的入度为 0 的点，于是最后贡献应该是 2^{\mathrm{cross}(T,S\setminus T)}f_{T} 状物。但是我们发现这时入度为 0 的点集会被按照多种子集划分统计，于是需要容斥。考虑到我们求的是

\left|\bigcup_{i\in U}S_i\right|=\sum_{T\subseteq S,T\ne \empty} (-1)^{|T|-1}\left|\bigcap_{i\in T} S_i\right|

于是转移时乘上容斥系数即可，得到

f_{S}=\sum_{T\subseteq S,T\ne \empty} (-1)^{|T|-1}2^{\mathrm{cross}(T,S\setminus T)}f_{S\setminus T}

  1. 强连通子图计数（主旋律）

    首先【强连通子图 = 总子图 - 非强连通子图】。

    考虑这跟DAG计数的关系，有重要性质，就是所有非强连通子图在SCC缩点后构成点数大于 1 的DAG。

    那么直接定义 f_S 表示点集为 S 的强连通子图数量，并令 G_S 表示点集为 S 的子图总数。

    总子图有 G_S 个，对于非强连通子图，我们在其缩点后的DAG上进行刻画，根据套路找到所有入度为 0 的SCC，那么相当于要拎出来一个点集 T 让其构成一个个独立的SCC，定义这个方案数为 g_T，那么不难发现剩下的部分可以任意组合，都满足条件。

    根据之前的分析，此时需要进行容斥，即选出的SCC组成的集合 T^\prime 会被按照多种子集划分统计，仿照DAG计数，我们知道这个容斥系数应为 (-1)^{|T^\prime|-1}，不难发现这个要在 g 的计算中被完成。那么

    f_{S}=G_S-\sum_{T\subseteq S\wedge T\ne \empty}g_{T}2^{\mathrm{cross}(T,S\setminus T)}G_{S\setminus T}

    接下来考虑 g 的计算。

    先考虑整个 S 都是一个SCC，这种情况贡献是 f_S。

    对于多个独立的SCC，拎一个出来，记其点集为 T，那么其个数就是 f_{T}，剩下的就是 g_{S\setminus T}，并且每新增一个 SCC就要乘上 -1 来实现容斥系数，于是转移应该是 -f_{T}g_{S\setminus T} 状物。但是这样会有问题，就是你选择SCC的顺序会造成影响，于是进行钦定顺序，假设钦定一个点 x 表示选择的SCC T 包含 x，那么由于包含 x 的SCC是唯一的，于是就完成了顺序钦定，考虑定义一个SCC T 的代表为 \mathrm{lowbit}(T)，于是得到

    g_{S}=f_{S}-\sum_{T\subset S\wedge \mathrm{lowbit}(T)=\mathrm{lowbit}(S)}f_{T}g_{S\setminus T}

​ 还没完，对于 f 的计算，注意到当 T=S 时，要求 g 中包含的点数是大于 1 的，所以此时 g 中不能算上 f_S 的贡献，于是转移应该是

g_S=-\sum_{T\subset S\wedge \mathrm{lowbit}(T)=\mathrm{lowbit}(S)}f_{T}g_{S\setminus T} \\ f_{S}=G_S-\sum_{T\subseteq S\wedge T\ne \empty}g_{T}2^{\mathrm{cross}(T,S\setminus T)}G_{S\setminus T} \\ g_S\leftarrow g_S+f_S

​ 那么我们得到了 O(3^nn^2) 的做法，无法通过。

​ 我们算法的瓶颈在于计算 \mathrm{cross}(T,S\setminus T)，我们考虑递推计算，假设固定住 S 后 T 要加入一个点 u，那么变成 \mathrm{cross}(T\cup \set{u},S\setminus T\setminus \set{u}))，那么原来 T 中到 u 的都没掉，u 到 (S\setminus T) 中的都加上，于是

\mathrm{cross}(T\cup \set{u},S\setminus T\setminus \set{u}))=\mathrm{cross}(T,S\setminus T)-|\mathrm{in}(u)\cap T|+|\mathrm{out}(u)\cap (S\setminus T)| \\ \Rightarrow \mathrm{cross}(T,S\setminus T)=\mathrm{cross}(T\cup \set{u},S\setminus T\setminus \set{u}))+|\mathrm{in}(u)\cap T|-|\mathrm{out}(u)\cap (S\setminus T)|

于是可以在枚举子集时随便加一个 u 并计算，此处取 u=\mathrm{lowbit}(S\setminus T) 即可。

​ G_S 同理，加上一个点 u 则加入了 S 到 u 和 u 到 S，得到

G_{S\cup \set{u}}=G_S+|\mathrm{in}(u)\cup S|+|\mathrm{out}(u)\cup S| \\

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

代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=15,M=215,mod=1e9+7;
typedef long long ll;
inline int Mod(int x) { return x<0 ? x+mod : (x>=mod ? x-mod : x); }
inline void adm(int &x,int y) { x=Mod(x+y); }
inline void dec(int &x,int y) { x=Mod(x-y); }
inline int lowbit(int x) { return x & (-x); }

int n,m;
bool e[N][N];
int in[N],out[N];
int pw2[M],ppcnt[1<<N],bit[1<<N];
int G[1<<N];
int cross[1<<N];
int f[1<<N],g[1<<N];

inline void print(int S) { for (int i=0;i<n;i++) cout << ((S>>i)&1); }

int main()
{
    cin >> n >> m;
    for (int i=1;i<=m;i++)
    {
        int u,v;
        cin >> u >> v;
        u--,v--;
        e[u][v]=true;
        in[v]|=(1<<u);
        out[u]|=(1<<v);
    }

    pw2[0]=1;
    for (int i=1;i<=m;i++) pw2[i]=(ll)pw2[i-1]*2%mod;
    for (int i=1;i<(1<<n);i++) ppcnt[i]=ppcnt[i>>1]+(i&1);
    for (int i=0;i<n;i++) bit[1<<i]=i;

    for (int S=1;S<(1<<n);S++)
    {
        int u=bit[lowbit(S)];
        G[S]=G[S^(1<<u)]+ppcnt[in[u]&S]+ppcnt[out[u]&S];
    }

    g[0]=-1;
    for (int S=0;S<(1<<n);S++)
    {
        memset(cross,0,sizeof(cross));
        for (int T=S&(S-1);T;T=(T-1)&S)
        {
            int u=bit[lowbit(S-T)];
            cross[T]=cross[T|(1<<u)]+ppcnt[in[u]&T]-ppcnt[out[u]&(S-T)];
        }

        for (int T=S&(S-1);T;T=(T-1)&S) 
        {
            if (lowbit(T)==lowbit(S))
            {
                dec(g[S],(ll)f[T]*g[S-T]%mod);
            }
        }
        f[S]=pw2[G[S]];
        for (int T=S;T;T=(T-1)&S) dec(f[S],(ll)g[T]*pw2[cross[T]]%mod*pw2[G[S-T]]%mod);
        adm(g[S],f[S]);
    }
    cout << f[(1<<n)-1] << "\n";

    return 0;
}