DAG 容斥
yinianxingkong
·
·
算法·理论
二轮复习了 DAG 容斥理论，复习了一整个下午。记录一下。
本题解从原初的那一位开天辟地讲起。
无向图定向 DAG 计数
最基础的 DAG 容斥。
枚举入度为 0 的点集，通过子集反演将恰好转成钦定。设 f_S 表示 S 定向为 DAG 的方案数，g_S 表示 S 分成几个独立集的方案数，有：
\begin{aligned}
f_S&=\sum_{T\subseteq S}\sum_{T\subseteq H\subseteq S} (-1)^{|H|-|T|}f_{S-H}g_H
\\
&=\sum_{H\subseteq S}f_{S-H}g_{H}(-1)^{|H|}\sum_{T\subseteq H} (-1)^{|T|}
\\
&=\sum_{H\subseteq S}f_{S-H}g_{H}(-1)^{|H|+1}
\end{aligned}
本题中 g_S 就是 S 中有无边。记住这个容斥系数 (-1)^{|H|+1}，事实上我们可以推导出当 H 被分成 k 个连通块的时候系数是 (-1)^{k+1}，这个是类似的。
另外上面的柿子也可以用二项式反演推。将 g_{S,i} 表示为 i 个连通块方案后求和即可。
有向图生成 DAG 计数
设 f_S 表示 S 生成 DAG 计数。省略相同的容斥过程：
f_S=\sum_{T\subseteq S} (-1)^{|T|+1}g_Tf_{S-T}2^{edge(T,S-T)}
但实际上一共只有 $3^n$ 个不同 $edge$ 查询，对每个 $S$ dp 预处理所有 $T$ 的查询就可以 $O(3^n)$。
# [重塑时光](https://www.luogu.com.cn/problem/P10221)
感觉比主旋律简单一些就放这了。
主要是一个嵌套的思想。转换后你会发现问题相当于内部是个 DAG，每个 DAG 缩点以后外部关系也是个 DAG，对这个计数。
在这道题里内层 DAG 只需要先预处理 topo 序计数即可，再对外层用 DAG 容斥。$O(3^nn^2)$ 可以通过。
其余部分和 DAG 容斥关系不是很大就不讲了。
# [生成 SCC 计数](https://www.luogu.com.cn/problem/P11714)
进行单步容斥，考虑不是 SCC 的方案，即缩点后点数超过 $1$ 的生成 DAG 计数。
设 $f_S$ 为是 SCC 计数，$g_{S,i}$ 为形成 $i$ 个连通块计数：
$$
\begin{aligned}
f_S&=2^{edge(S,S)}-\sum_{i}(-1)^{i+1}\sum_{T\subseteq S,T\ne\varnothing}g_{T,i}2^{edge(T,T)+edge(S-T,T)}
\end{aligned}
$$
之前的 $f$（就是其余部分）在这里的方案是 $2^{edge(T,T)}$。
注意上述柿子是有问题的。当 $T=S$ 且 $i=1$ 时是单点，不该减去。不过你很快就会发现我们正好可以这么做。
值得一提的是这里的 $i$ 没必要设为一维，把它带到值域里一起计算更好。换句话说，令 $g_{S}=\sum (-1)^{i+1}g_{S,i}$，直接转移新的 $g$。
考虑 $g$ 的转移，首先会有一个 $f$ 做 $1$ 的贡献，其余的考虑新增一个连通块。由标志物定序思想，不妨钦定 $\text{lowbit}$ 所在连通块是新插入的连通块。
$$
\begin{aligned}
g_S&=f_S-\sum_{T\subseteq S,\text{lowbit}(T)=\text{lowbit}(S)}f_{T}g_{S-T}
\end{aligned}
$$
由于我们之前所说，有一个 $f_S$ 多做了贡献，所以计算时先不把 $f_S$ 加上，等用 $g_S$ 算完正确的 $f_S$ 后再加回来就是对的。
用之前的技巧可以做到 $O(3^n)$。
# [岁月](https://www.luogu.com.cn/problem/P11834)
借鉴了 @[_Eriri_](https://www.luogu.com.cn/user/1008068) 的题解。
直接将图视为有向图，记方案数后除以总方案。
先考虑 C 性质。即存在大小为 $n$ 的外向生成树，即存在一个点可达其它所有点，即缩点后入度为 $0$ 的点只有一个。
枚举入度为 $0$ 的点对应的点集，此时外部点恰好形成 $0$ 个方案，对这个反演，系数是二项式反演的系数：
$$
f_S=\sum_{i}(-1)^i\sum_{S\subseteq T} g_{T-S,i}2^{edge(T,U-T)+edge(U-T,U-T)}
$$
用前面的套路把 $g$ 缩了。注意这和主旋律的刚好相反。
然后结合主旋律的那个 SCC 计数就可以算出每个集合的方案了。
关于正解，考虑最小生成树选边的过程，发现不管怎么选边，连通性是不会变的。
同时枚举所有连通块原来的根点集，我们只研究最终根点集是什么。
发现只保留指向根集的边以后，将上一层连通块缩点去做 C 性质即可。上一层选指定根集的方案作为系数即可。
具体实现可以枚举一个 $R$，它与每个连通块点集的交就是这个连通块的根点集。
缩点以后执行上述过程可以得出哪些连通块的根集会继续作为根集。转移到这些根点集的并即可。
应用上述精细实现可以 $O(3^n)$。
给一份经过翻译运动的完整注释代码：
```cpp
const int mod=1000000007;
il int add(int a,int b){return (a+=b)>=mod&&(a-=mod),a;}
il int del(int a,int b){return (a-=b)<0&&(a+=mod),a;}
il int qpow(int a,int b){int r=1;for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)r=1ll*r*a%mod;return r;}
int n,m,t,qpow2[M],c[M],fa[N],bel[N],con[N],vis[N],h[M],H[M],ans;vector<pii >E[N*N];
/*
bel：上一层所属连通块标志
con：连通块内部的点集
*/
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
vd merge(int x,int y){if((x=find(x))^(y=find(y)))fa[x]=y;}
#define F(VAL) for(int TMP=VAL,x=I[TMP&-TMP];TMP;TMP^=TMP&-TMP,x=I[TMP&-TMP])
/*这个东西就是枚举每个二进制位的意思*/
int J[N],I[M];
/*
j = J[i] = i 对应的二进制位
i = I[j] = j 对应的下标值
*/
int D[M],B[M],OP,e[N][N],sum[N][M],Se[M];
/*
D：连通块标志 -> 连通块编号
B：连通块编号 -> 连通块标志
*/
int f[M],g[M];
int Edge(int S,int T){int res=0;F(S)res+=sum[x][T];return res;}
vd MakeRt(int P,int R,vector<pii >&E,int RT){//当前连通块枚举的 P，R 是其中原来的根集并，RT 是并查集的根
/*
首先明确：
我们合并了几个连通块的树，并且钦定了根集并。
*/
int C=1;
for(int i=1;i<=OP;i++)C=1ll*C*h[R&con[D[i]]]%mod;
if(!C)return;
for(auto[u,v]:E){
if(find(u)!=RT)continue;
/*枚举本层本连通块的边*/
if(bel[u]==bel[v])C=4ll*C%mod;//不影响连通性
else{
if(R&J[v])++e[B[bel[u]]][B[bel[v]]];
else C=2ll*C%mod;
if(R&J[u])++e[B[bel[v]]][B[bel[u]]];
else C=2ll*C%mod;
//考虑两条有向边，当且仅当指向原来的根集时会有影响。
}
}
for(int i=1;i<=OP;i++)for(int j=0;j<qpow2[OP];sum[i][++j]=0)F(j)sum[i][j]+=e[i][x];
for(int j=0;j<qpow2[OP];j++)Se[j]=Edge(j,j),g[j]=0;
//这一段是主旋律，为了体现这一点我的 g 的系数都没改。
//f[S] 是几个连通块强连通的方案数
//g[S] 是带系数的将 S 分成不交连通块的方案。
for(int S=1;S<qpow2[OP];S++){
int X=S^(S&-S);
for(int T=X;;T=(T-1)&X){g[S]=del(g[S],1ll*f[T^(S&-S)]*g[X^T]%mod);if(!T)break;}
f[S]=qpow2[Se[S]];
for(int T=S;T;T=(T-1)&S)f[S]=del(f[S],1ll*g[T]*qpow2[Edge(T,S^T)+Se[S^T]]%mod);
g[S]=add(g[S],f[S]);
}g[0]=mod-1;//系数反的哈
//这里枚举哪些合并在一起
for(int S=1;S<qpow2[OP];S++){
int O=(qpow2[OP]-1)^S,res=0;
for(int T=O;;T=(T-1)&O){res=add(res,1ll*(mod-g[T])*qpow2[Edge(S|T,O^T)+Se[O^T]]%mod);if(!T)break;}
int X=0;F(S)X|=R&con[D[x]];
H[X]=add(H[X],1ll*C*f[S]%mod*res%mod);
}
for(int i=1;i<=OP;i++)for(int j=1;j<=OP;j++)e[i][j]=0;
}
il vd solve(){
cin>>n>>m,t=(1<<n)-1;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,E[w].pb(MP(u,v));
for(int j=0;j<=t;j++)h[j]=0;
for(int i=1;i<=n;i++)con[i]=J[i],bel[i]=fa[i]=i,h[J[i]]=1;
for(int w=1;w<=m;w++)if(!E[w].empty()){
for(auto[u,v]:E[w])merge(u,v);
for(int j=0;j<=t;j++)H[j]=0;
for(int i=1;i<=n;i++)if(find(i)==i){
int P=0;OP=0;
for(int j=1;j<=n;j++)if(find(j)==i&&!vis[bel[j]])vis[bel[j]]=1,++OP,B[D[OP]=bel[j]]=OP,P|=con[bel[j]];
for(int R=P;R;R=(R-1)&P)MakeRt(P,R,E[w],i);
/*在新连通块中尝试钦定根。*/
for(int j=1;j<=OP;j++)vis[D[j]]=0;
}
for(int i=1;i<=n;i++)con[bel[i]=find(i)]|=J[i];
for(int j=0;j<=t;j++)h[j]=H[j];
}
ans=0;for(int j=0;j<=t;j++)ans=add(ans,h[j]);
cout<<1ll*ans*qpow(qpow(4,m),mod-2)%mod<<'\n';
}
```