自动搬运

查看原文

来自洛谷，原作者为

	Linge_Zzzz Yeah, life's not out to get you!

搬运于2025-08-24 23:09:42，当前版本为作者最后更新于2025-04-19 16:56:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

其实是整合了多篇题解的长处，这有人看不懂我直接吃。

Sol

发现强连通很难刻画，不妨使用单步容斥，转化成算非强连通方案数。

考虑刻画一下非强连通，发现缩点之后一定是一个点数大于 $1$ 的 DAG。

于是，呃，考虑一种比较劣的做法，就是先暴力枚举这个图缩点之后每个点属于的 SCC 是哪个，然后对着这个算方案数。

于是现在需要算 DAG 生成子图。

考虑刻画 DAG，发现其一定存在一些点入度为 $0$。把这些点删了之后剩下的点还是 DAG，于是找到了一个子结构，可以对着这个 DP。

设 $dp_S$ 表示 $S$ 的答案，$E_{S,T}$ 表示 $S$ 到 $T$ 的边数，则有：

$$dp_S=\sum_{T\subseteq S,T\neq \emptyset}dp_{S-T}2^{E_{T,S-T}} $$

但是这对吗？这不对。因为 $S-T$ 里面可能还有入度为 $0$ 的点，会导致算重。

考虑一下子集反演，当前全集为 $S$，设 $f_T$ 表示 $T$ 内点恰为所有入度为 $0$ 的点的方案数，$g_T$ 表示钦定 $T$ 内点入度为 $0$ 的方案数。显然 $g_T=dp_{S-T}2^{E_{T,S-T}}$。有关系式：

$$g_T=\sum_{T\subseteq R}f_R$$

反演得到：

$$f_T=\sum_{T\subseteq R}(-1)^{|R|-|T|}g_R$$

重写一下转移式，进行一些式子的推导：

$$\begin{aligned} dp_S&=\sum_{T\subseteq S,T\neq \emptyset}f_T\\ &=\sum_{T\subseteq S,T\neq \emptyset}\sum_{T\subseteq R}(-1)^{|R|-|T|}g_R\\ &=\sum_{R\subseteq S,R\neq \emptyset}(-1)^{|R|}g_R\sum_{T\subseteq R,T\neq \emptyset}(-1)^{|T|}\\ &=\sum_{R\subseteq S,R\neq \emptyset}(-1)^{|R|}g_R([R=\emptyset]-1)\\ &=\sum_{R\subseteq S,R\neq \emptyset}(-1)^{|R|+1}g_R\\ &=\sum_{T\subseteq S,T\neq \emptyset}(-1)^{|T|+1}dp_{S-T}2^{E_{T,S-T}} \end{aligned}$$

于是得到了一个 $O(3^n)$ 算一次的做法，但是乘上暴力枚举缩点方案数之后复杂度爆炸。

考虑拓展这个东西到非强连通图计数上。

设 $dp_S$ 表示 $S$ 的答案，即 $S$ 缩成一个点的方案数。仿照上面的方法，设 $g_T$ 表示 $T$ 内的点缩成若干个入度为 $0$ 的点的方案数，转移的时候枚举 $T$，钦定 $T$ 内点缩成了若干入度为 $0$ 的点：

$$dp_{S}=2^{E_{S,S}}-\sum_{T\subseteq S,T\neq \emptyset}(-1)^{?}g_T2^{E_{T,S-T}+E_{S-T,S-T}} $$

但是发现容斥系数是不确定的，因为并不知道 $T$ 内的点到底缩成了多少个点。于是考虑修改 $g_T$ 的定义，令其包含上容斥系数，即缩成奇数个点的方案数减去缩成偶数个点的方案数，再写：

$$dp_{S}=2^{E_{S,S}}-\sum_{T\subseteq S,T\neq \emptyset}g_T2^{E_{T,S-T}+E_{S-T,S-T}} $$

这个式子可以 $O(3^n)$ 做了。但是还没做完，还需要算 $g_S$。

考虑找子结构，发现这些缩完之后的点互不相干，于是可以钦定 $\operatorname{lowbit}(S)$ 所属的 SCC 是新加入的：

$$g_S=dp_S-\sum_{T\subset S,\operatorname{lowbit}(S)=\operatorname{lowbit}(T)}dp_Tg_{S-T} $$

第一项是考虑 $S$ 单独为一个 SCC，$1$ 是奇数，所以要加上。后面一串是增加一个 SCC，奇偶性改变，所以要减去。

但是又出现了新问题，$g_S$ 和 $dp_S$ 好像互相依赖。真的互相依赖吗？$dp_S$ 的转移式中只有 $S=T$ 时会用到 $g_S$。重申一遍 $dp_S$ 是 $S$ 强连通的方案数，那么在 $dp_S$ 中减去 $g_S$ 中的 $dp_S$ 时，减去的这个 $dp_S$ 是合法的方案数，其不应该被减掉。

所以先算出 $g_S$，不加上 $dp_S$，再算出来 $dp_S$，把 $dp_S$ 加到 $g_S$ 上，是正确的。

于是现在只剩下最后一个问题了，怎么算 $E_{S,T}$。

看起来这个状态数是 $4^n$ 的，但是观察发现对于每个 $S$，只需要用到形如 $E_{T,S-T}$ 或者 $E_{S,S}$ 形式的 $E$。$T\subseteq S$，所以状态数是 $3^n$。但是空间复杂度还是 $O(4^n)$，所以考虑每枚举一个 $S$ 就重新计算 $E_{T,S-T}$，对于 $E_{T,T}$ 另外开一个计算。

先预处理出 $out_u$ 表示 $u$ 连向的点集，$in_u$ 表示连向 $u$ 的点集，这样就有递推式：

$$E_{T,S-T}=E_{T+x,S-T-x}-\operatorname{popcount}(out_x\operatorname{and} (S-T))+\operatorname{popcount}(in_x\operatorname{and} T)\\ E_{S,S}=E_{S-x,S-x}+\operatorname{popcount}(in_x\operatorname{and}S)+\operatorname{popcount}(out_x\operatorname{and}S)$$

这样，整个问题就能做到 $O(3^n)$ 了，非常厉害。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
const int N=18,INF=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
int n,m,dp[1<<N],g[1<<N],in[N],out[N],e1[1<<N],e2[1<<N],p2[1145],pos[1<<N];
inline int lowbit(int x){return x&(-x);}
inline int popcnt(int x){return __builtin_popcount(x);}
vector<int> G[N];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	p2[0]=1;
	for(int i=1;i<=1000;i++)p2[i]=p2[i-1]*2%mod;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		out[u]|=(1<<(v-1));
		in[v]|=(1<<(u-1)); 
	}
	for(int i=0;i<n;i++)pos[1<<i]=i+1;
	for(int S=1;S<(1<<n);S++){
		int x=lowbit(S);
		e2[S]=e2[S-x]+popcnt(in[pos[x]]&S)+popcnt(out[pos[x]]&S);
	}
	for(int S=1;S<(1<<n);S++){
		e1[S]=0;
		for(int T=(S-1)&S;T;T=(T-1)&S){
			int x=lowbit(S-T);
			e1[T]=e1[T+x]-popcnt((S-T)&out[pos[x]])+popcnt(T&in[pos[x]]);
		}
		for(int T=(S-1)&S;T;T=(T-1)&S){
			if(lowbit(S)!=lowbit(T))continue;
			g[S]=(g[S]-dp[T]*g[S-T]%mod+mod)%mod;
		}
		dp[S]=p2[e2[S]];
		for(int T=S;T;T=(T-1)&S){
			dp[S]=(dp[S]-g[T]*p2[e1[T]+e2[S-T]]%mod+mod)%mod;
		}
		g[S]=(g[S]+dp[S])%mod;
	}
	cout<<dp[(1<<n)-1]<<endl;
	return 0;
}