UOJ37 【清华集训2014】主旋律（SCC/DAG 状态压缩）

题意

求一个有向图 \(G\) 删掉一些边后原图仍强连通的方案数。模数 \(10^9+7\)。

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

分析

SCC 状压有一个非常经典的“耳分解”：以 SCC 内两个点（可以相同）为起点、终点，找一条除两端外不在 SCC 内的链，然后加进去。但是这里要求方案数，耳分解失效，考虑别的方法。

我们知道，DAG 计数的经典方法是枚举点集的一个非空子集 \(T\)，并钦定 \(T\) 是入度为 0 的点的集合。但是实际情况中 \(T\) 不一定是所有入度为 0 的点，所以考虑容斥，有结论是：\(T\) 的容斥系数为 \((-1)^{|T|-1}\)。设 \(f_S\) 表示 \(S\) 点集形成 DAG 的方案数，有转移 \(f_S\leftarrow (-1)^{|T|-1}2^{cnt_{T\rightarrow S/T}}f_{S/T}\)，\(cnt_{S\rightarrow T}\) 表示起点在 \(S\) 终点在 \(T\) 的边数。

回到原问题，设 \(f_S\) 表示 \(S\) 点集形成 SCC 的方案数。正着做有点困难，设 \(edge_S\) 表示 \(S\) 内部的边数，考虑用 \(2^{edge_S}\) 减去不为 SCC 的方案数，后者相当于求缩点后形成 DAG 且点数 \(\ge 2\) 的方案数。套用 DAG 计数的经典做法，枚举入度为 \(0\) 的子集 \(T\)（\(T\) 可以等于 \(S\)，但此时 \(T\) 内部必须形成 \(\ge 2\) 个 SCC），那么 \(S/T\) 内部的以及 \(T\rightarrow S/T\) 的边任意连，\(S/T\rightarrow T\) 的边不能连，此时若 \(T\) 中 SCC 个数为 \(t\)，那么容斥系数就是 \((-1)^{t-1}\)，考虑设 \(g_S\) 表示 \(S\) 内形成若干个 SCC 的带容斥系数方案数，转移就是 \(g_S=-\sum_{T\subset S}g_{S-T}f_{T}\)，为了避免算重，\(T\) 必须包含 \(S\) 的最低位。最终 DP 式子就是

最后别忘了把 \(g_S=g_S+f_S\)。

const int maxn=16,maxm=1<<15,maxk=14348907,mod=1e9+7;
int n,m;
bool vis[maxn][maxn];
int e[maxn][maxm];
int edge[maxm];
int pw[maxn*maxn];
int f[maxm],g[maxm],h[maxk];
int to[maxm];
inline bool in(int S,int x){return (S>>(x-1))&1;}
inline void adder(int &x,int y){x+=y,x=x>=mod?x-mod:x;}
inline void suber(int &x,int y){x-=y,x=x<0?x+mod:x;}
inline void solve_the_problem(){
	n=rd(),m=rd();
	rep(i,1,m){
		int x=rd(),y=rd();
		vis[x][y]=1;
	}
	pw[0]=1;rep(i,1,m)pw[i]=pw[i-1]*2%mod;
	const int U=(1<<n)-1;
	rep(S,0,U)rep(i,1,n)if(in(S,i))rep(j,1,n)if(in(S,j))edge[S]+=vis[i][j];
	rep(i,1,n)rep(S,0,U)rep(j,1,n)if(in(S,j))e[i][S]+=vis[i][j];
	rep(S,0,U)rep(i,1,n)to[S]=to[S]*3+in(S,i);
	rep(S,1,U){
		int p=__builtin_ctz(S),S0=S^(1<<p),S1=U^S;
		for(int T=S1;T;T=(T-1)&S1){
			h[to[S|T]+to[S]]=h[to[S0|T]+to[S0]]+e[p+1][T];
		}
	}
	rep(S,0,U)f[S]=pw[edge[S]];
	rep(S,1,U){
		int p=__builtin_ctz(S);
		for(int T=(S-1)&S;T;T=(T-1)&S)if((T>>p)&1){
			suber(g[S],g[S^T]*f[T]%mod);
		}
		for(int T=S;T;T=(T-1)&S){
			suber(f[S],pw[edge[S^T]+h[to[S]+to[T]]]*g[T]%mod);
		}
		adder(g[S],f[S]);
	}
	write(f[U]);
}

复杂度 \(O(3^n+2^nn^2)\)。