给定一个连通图，问你对于每个点 k 有多少删去 0 条边及以上的新图满足 1 和 k 连通，n \le 17。
令 f(S) 表示 S 令 S 这个点集连通的方案数，那么一个包含了 1 和 k 的 S，其 f(S) 就可以对 ans_k 作出贡献。
直接计算 f(S) 无疑是困难的，考虑容斥。令 g(S) 表示点集 S 能形成的图的数量，这个很好算，就等于 2^{cnt_S}，其中 cnt_S 为 S 内部的边的条数。
我们说列式子就是从两个不同的角度描述同一个东西，再令他们相等。前面我们已经用 2^{cnt_S} 来描述了 g(S)，现在我们考虑再用其他角度，倘若固定了 S 中的一个点 v 的话，令 v \in T，则 g(S) = \sum_{v \in T \subseteq S}f(T)\times g(S/T)，就是一部分连通，另一部分随意连的方案数。
还是考虑容斥，f(S) 表示点集 S 形成连通二分图的方案数，g(S) 表示形成二分图的方案数。先考虑 g(S) 怎么算，如果是二分图，不难想到把 S 分成两个子集 U 和 S/U，令 U 内为黑点，S/U 内为白点，相同子集内不能连边，就只考虑两个子集之间的连边，设 E(U,S/U) 表示这两子集之间的边数，则 g(S) = \sum_{U \subseteq S} 2^{E(U,S/U)}，注意 U 可以是 S 本身。
然后还是还个角度考虑 $g(S)$，还是从连通性的角度出发来和 $f(S)$ 挂钩，固定一个点 $v$，把 $S$ 分成包含 $v$ 的连通块和其他不在意的部分，则 $g(S)=\sum_{v \in T \subseteq S} 2
\times f(T)\times g(S/T)$，为什么是 $2\times f(T)$ 呢，因为我们的答案 $f(S)$ 是不考虑左部和右部谁是黑点谁是白点的，但是我们算 $g(S)$ 的时候却考虑了，因为前面的计算过程中同一个子集既会作为一次 $U$ 也会作为一次 $S/U$。
老样子把 $f(S)$ 移出来，则 $2f(S) = g(S)-\sum_{v\in T \subset S}2f(T)\times g(S/T)$，我们最后输出的时候再除以二就好了。
时间复杂度 $O(3^n)$，瓶颈在枚举子集。
:::success[代码]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define _int __int128
#define ull unsigned long long
#define pii pair<int,int>
#define fst first
#define scd second
#define pq priority_queue
#define mkp make_pair
#define popcount(x) __builtin_popcount(x)
#define endl '\n'
int n,m;
const int N = 25,V=(1<<18),mod=998244353;
int u[N*N],v[N*N];
vector<int>e[N];
int qpow(int a,int b){
int res=1;
while(b){
if(b&1)res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
int f[V],g[V],ans[N],cnt[V];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>u[i]>>v[i];
e[u[i]].push_back(v[i]);
e[v[i]].push_back(u[i]);
}
for(int i=0;i<(1<<n);i++){
for(int j=1;j<=m;j++){
cnt[i]+=(((i>>(u[j]-1))&1)&((i>>(v[j]-1))&1));
}
}
for(int s=0;s<(1<<n);s++){
for(int u=s;u>=0;u=(u-1)&s){
int cm=cnt[s]-cnt[u]-cnt[s^u];
g[s]+=qpow(2,cm);
if(!u)break;
}
}
for(int s=0;s<(1<<n);s++){
int v=(s&(-s));
int mk=s^v,x=0;
f[s]=g[s];
for(int j=(mk-1)&mk;j>=0;j=(j-1)&mk){
if(j!=mk){
int t=j|v;
x=(x+f[t]%mod*g[s^t]%mod)%mod;
}
if(!j)break;
}
f[s]=(f[s]-x+mod)%mod;
}
int ans=f[(1<<n)-1];
ans=(ans%mod*qpow(2,mod-2)%mod)%mod;
cout<<ans;
}
```
:::
## 有向图容斥计数
### DAG 生成子图计数
问一个有向图有几个生成子图是有向无环图，考虑 DAG 的性质，那就是会有入度为 $0$ 的点。
定义 $f(S)$ 为点集 $S$ 形成有向无环图的方案数，我们可以考虑枚举哪些点是源点来转移。令 $T \subseteq S$ 为源点点集，那么乍一看就有转移 $f(S)=\sum_{\emptyset \neq T \subseteq S}2^{E(T,S/T)}f(S/T)$。这个式子表示选出的源点集合向其余的点集 $S/T$ 连边，$S/T$ 也要是 DAG，而 $T$ 向 $S/T$ 的边随便连不连。
但这是错误的，因为即使源点集合不一样，他们所形成的图结构可能相同，所以就算重了。
考虑容斥，一个经典的想法就是奇数加偶数减，即 $f(S)=\sum_{\emptyset \neq T \subseteq S}(-1)^{|T|+1}2^{E(T,S/T)}f(S/T)$，考虑证明这是对的。
对于一个有 $k$ 个源点的特定 DAG 结构来说，只要枚举的 $T$ 是 $k$ 个点的子集就会把这个图计算一次，对于大小为 $i$ 的 $T$ 来说，有 $\binom{k}{i}$ 种 $T$，那就计入这个图 $\binom{k}{i}(-1)^{i+1}$ 次。
总次数为 $\sum_{i=1}^k \binom{k}{i} (-1)^{i+1}$，由二项式定理可知，$(1-1)^k=\sum_{i=0}^k\binom{k}{i}(-1)^i$，所以 $\binom{k}{0}-\binom{k}{1}+\binom{k}{2}-...+\binom{k}{k}(-1)^k = 0$，移项得 $\binom{k}{1}-\binom{k}{2}+...+\binom{k}{k}(-1)^{k+1} = \binom{k}{0} = 1$，发现这个式子就是我们刚才写出的总次数，所以每个生成子图只会被计入一次，证明完毕。
这其实就是一个子集反演，具体推导可以去主旋律那个题的题解区看。
写了一个 $O(3^nn)$ 的做法，在算 $E(S,S/T)$ 的时候多了一个 $n$，因为没题所以没测，有锅的话踢我。
:::success[代码]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define _int __int128
#define ull unsigned long long
#define pii pair<int,int>
#define fst first
#define scd second
#define pq priority_queue
#define mkp make_pair
#define popcount(x) __builtin_popcount(x)
#define endl '\n'
int n,m;
const int N = 25,V=(1<<18),mod=998244353;
int arv[N],f[V],pw[N*N],cnt[N][V];
int qpow(int a,int b){
int res=1;
while(b){
if(b&1)res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
pw[0]=1;
for(int i=1;i<=n*n;i++){
pw[i]=(pw[i-1]*2)%mod;
}
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
arv[u-1]|=(1<<(v-1));
}
for(int i=0;i<n;i++){
for(int s=0;s<(1<<n);s++){
cnt[i][s]=popcount(arv[i]&s);
}
}
f[0]=1;
for(int s=0;s<(1<<n);s++){
for(int t=s;t;t=(t-1)&s){
int e=0,tmp=t;
while(tmp){
int v=__builtin_ctz(tmp);
e+=cnt[v][s^t];
tmp&=(tmp-1);
}
int typ=((popcount(t))&1)?1:mod-1;
f[s]=(f[s]+typ*pw[e]%mod*f[s^t]%mod)%mod;
}
}
cout<<f[(1<<n)-1];
}
```
:::
### [P11714 [清华集训 2014] 主旋律](https://www.luogu.com.cn/problem/P11714)
这题是在上一个题的基础上得来的，询问你一个给定的有向图有几个生成子图是强连通的。
设 $f(S)$ 为 $S$ 的生成子图为强连通的方案数，$g(S)$ 为所有生成子图个数。显然 $g(S) = 2^{cnt_S}$。
既然要列式子还是从不同角度考虑，还有什么方法可以表示 $g(S)$ 呢？我们知道，任何一个有向图缩点之后都会变成 DAG，既然是 DAG，就可以和我们刚才练的 DAG 计数联系起来。
上一题所说 DAG 的源点，此刻变成了所有入度为 $0$ 的 SCC，那我们就枚举子集 $T$ 作为构成这些 SCC 的点，类比 DAG 计数可以得到一个容斥式子。$g(S)=\sum_{\emptyset \neq T \subseteq S}H(T)\times2^{E(T,S/T)}\times g(S/T)$，其中 $H(T)$ 应该包含容斥系数，我们来考虑它是什么。
设 $T$ 一共构成了 $k$ 个 SCC，那么系数应该是 $(-1)^{k+1}$，但是 $H(T)$ 还应该乘上怎么划分成 $k$ 个 SCC 的方案数。所以总结一下 $H(S)$ 的定义为 $S$ 作为源点 SCC 点集时，划分出奇数个 SCC 的方案数减去划分出偶数个 SCC 的方案数。
既然提到了划分 SCC，那我们就把 $H(S)$ 和我们一直没管了的 $f(S)$ 挂上了钩。考虑写出这两个的关系式，当所有点在同一个 SCC 里时，方案数为 $f(S)$，否则我们就考虑固定一个点 $v$，枚举一个包含 $v$ 的子集 $T$ 为一个 SCC，这是我们为了不算重的老套路了。此时方案数为 $\sum_{v \in T \subset S}f(T)\times (-H(S/T))$，因为多了一个 SCC，奇偶性翻转了，原来的 $H(S/T)$ 的系数都要反过来。总式就是 $H(S)=f(S)-\sum_{v \in T \subset S}f(T)\times H(S/T)$。
那我们现在就可以做了呀，已知 $g(S)$ 的话，就先把 $H(S)$ 算出来，由前面那个式子移项得 $H(S)=g(S)-\sum_{\emptyset \neq T \subset S}H(T)\times 2^{E(T,S/T)} g(S/T)$。
知道了 $H(S)$ 就可以算 $f(S)$ 了，还是变一下式子，得到 $f(S)=H(S)+\sum_{v \in T \subset S}f(T)\times H(S/T)$。
代码是简单的，复杂度 $O(n3^n)$，已经可以过了。
:::success[代码]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define _int __int128
#define ull unsigned long long
#define pii pair<int,int>
#define fst first
#define scd second
#define pq priority_queue
#define mkp make_pair
#define popcount(x) __builtin_popcount(x)
#define endl '\n'
int n,m;
const int N = 25,V=(1<<18),mod=1e9+7;
int arv[N],f[V],h[V],g[V],pw[N*N],e[N][V],cnt[V];
int qpow(int a,int b){
int res=1;
while(b){
if(b&1)res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
pw[0]=1;
for(int i=1;i<=n*n;i++){
pw[i]=(pw[i-1]*2)%mod;
}
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
arv[u-1]|=(1<<(v-1));
for(int s=0;s<(1<<n);s++){
cnt[s]+=((s>>(u-1)&1)&(s>>(v-1)&1));
}
}
for(int i=0;i<n;i++){
for(int s=0;s<(1<<n);s++){
e[i][s]=popcount(arv[i]&s);
}
}
for(int s=0;s<(1<<n);s++){
g[s]=pw[cnt[s]];
}
for(int s=0;s<(1<<n);s++){
h[s]=g[s];
int x=0;
for(int t=(s-1)&s;t;t=(t-1)&s){
int E=0,tmp=t;
while(tmp){
int v=__builtin_ctz(tmp);
E+=e[v][s^t];
tmp&=(tmp-1);
}
x=(x+h[t]%mod*pw[E]%mod*g[s^t]%mod)%mod;
}
h[s]=(h[s]-x+mod)%mod;
int v=(s&(-s)),mk=s^v;x=0;
for(int j=(mk-1)&mk;j>=0;j=(j-1)&mk){
int t=j|v;
x=(x+f[t]%mod*h[s^t]%mod)%mod;
if(!j)break;
}
f[s]=(h[s]+x)%mod;
}
cout<<f[(1<<n)-1];
}
```
:::
其实优化到 $O(3^n)$ 也不算难事，这个 $n$ 是计算 $E(T,S/T)$ 时带上的，考虑令 $e_T$ 表示在全集为 $S$ 时，$T$ 连向 $S/T$ 的边数。这个可以用增量更新。每一次 $T$ 将一个点 $x$ 丢给 $S/T$ 的时候，$e_T$ 都减去 $x$ 到原来 $S/T$ 的边数，加上原来 $T$ 到 $x$ 的边数即可。
:::success[代码]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define _int __int128
#define ull unsigned long long
#define pii pair<int,int>
#define fst first
#define scd second
#define pq priority_queue
#define mkp make_pair
#define popcount(x) __builtin_popcount(x)
#define endl '\n'
int n,m;
const int N = 25,V=(1<<18),mod=1e9+7;
int arv[N],f[V],h[V],g[V],pw[N*N],e[V],cnt[V],in[N],out[N],id[V];
int qpow(int a,int b){
int res=1;
while(b){
if(b&1)res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
int lowbit(int x){
return x&(-x);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
pw[0]=1;
for(int i=1;i<=n*n;i++){
pw[i]=(pw[i-1]*2)%mod;
}
for(int i=0;i<n;i++)id[1<<i]=i+1;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
in[v]|=(1<<(u-1));
out[u]|=(1<<(v-1));
for(int s=0;s<(1<<n);s++){
cnt[s]+=((s>>(u-1)&1)&(s>>(v-1)&1));
}
}
for(int s=0;s<(1<<n);s++){
g[s]=pw[cnt[s]];
}
for(int s=0;s<(1<<n);s++){
h[s]=g[s];
int x=0;
e[s]=0;
for(int t=(s-1)&s;t;t=(t-1)&s){
int x=lowbit(s-t);
int v=id[x];
e[t]=e[t+x]-popcount(out[v]&(s-t-x))+popcount(in[v]&t);
}
for(int t=(s-1)&s;t;t=(t-1)&s){
int E=e[t];
x=(x+h[t]%mod*pw[E]%mod*g[s^t]%mod)%mod;
}
h[s]=(h[s]-x+mod)%mod;
int v=(s&(-s)),mk=s^v;x=0;
for(int j=(mk-1)&mk;j>=0;j=(j-1)&mk){
int t=j|v;
x=(x+f[t]%mod*h[s^t]%mod)%mod;
if(!j)break;
}
f[s]=(h[s]+x)%mod;
}
cout<<f[(1<<n)-1];
}
```
:::
### 竞赛图
任意两点之间有且只有一条边的有向图称为竞赛图，询问有几个 $n$ 个点的竞赛图是强连通的。
这里我们倒不用状压了，设 $g(i)$ 表示 $i$ 个点的竞赛图的个数，$f(i)$ 表示 $i$ 个点的强连通竞赛图的个数。$g(i) = 2^{\frac{i\times (i-1)}{2}}$，因为共 $\frac{i\times (i-1)}{2}$ 条边，每条边有正向反向两种选择。
首先 $g(i)$ 加上图直接强连通的方案数 $f(i)$，如果不是强连通的话，还是考虑把图拆分成两部分，强连通的部分和非强连通的部分，则 $g(i)=f(i)+\sum_{j=1}^{i-1}f(j)\times g(i-j) \times \binom{i}{j}$，则 $f(i) = g(i)-\sum_{j=1}^{i-1} f(j)\times g(i-j) \times \binom{i}{j}$。
可以做到 $O(n^2)$，随手写的代码，有锅踢我。
:::success[代码]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define _int __int128
#define ull unsigned long long
#define pii pair<int,int>
#define fst first
#define scd second
#define pq priority_queue
#define mkp make_pair
#define popcount(x) __builtin_popcount(x)
#define endl '\n'
int n,m;
const int N = 5005,mod=998244353;
int f[N],g[N],fac[N],inv[N];
int qpow(int a,int b){
int res=1;
while(b){
if(b&1)res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
int C(int n,int m){
if(n<m)return 0;
return fac[n]%mod*inv[m]%mod*inv[n-m]%mod;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
fac[0]=inv[0]=1;
for(int i=1;i<=n;i++){
fac[i]=(fac[i-1]*i)%mod;
}
inv[n]=qpow(fac[n],mod-2);
for(int i=n-1;i>=0;i--){
inv[i]=(inv[i+1]*(i+1))%mod;
}
for(int i=1;i<=n;i++){
int e=i*(i-1)/2;
g[i]=qpow(2,e);
}
for(int i=1;i<=n;i++){
f[i]=g[i];
int x=0;
for(int j=1;j<i;j++){
x=(x+f[j]%mod*g[i-j]%mod*C(i,j)%mod)%mod;
}
f[i]=(f[i]-x+mod)%mod;
}
cout<<f[n];
return 0;
}
```
:::
大概就是这样子，容斥说到底还是要列式子，可以多考虑一些角度，比如说总数减去不合法数，或者从对图的划分出发，还要注意考虑算重的问题。