题解：P11567 建造军营 II
cyffff
·
2025-05-27 21:35:56
·
题解
\text{Link}
联考迫真 NOIP 模拟赛 T3（
学完了 cxy 的 APIO2025 课件来做的，复杂度比原 std 优一点。
题意
给定一个 n 个点 m 条边的无向连通图 G=(V,E) ，再给定 k 个点对 (a_i,b_i) 。对于一个连通边子图 G'=(V,E') ，可以选择其中的一个边子集，一条边可选当且仅当不存在 1\le i\le k 使得存在从 a_i 到 b_i 且经过该边的边简单路径，定义 G' 的权值为选择边子集的方案数。
求所有连通边子图的权值和，对 10^9+7 取模。
## 题解
容易发现权值计算与边双有关，具体地，将边双缩点后，对于每一对点对 $(a_i,b_i)$，将 $a_i,b_i$ 所在边双之间的所有边标黑，则可以进行选择的边为不被标黑的边。
### 边双连通-连通变换
首先必须要会求边双连通子图数。先考虑如下问题：定义 $G=\text{Trans}(F,c)$，其中 $F,G$ 分别为集合幂级数，$c$ 为一常数。对于集合 $s$ 定义其划分 $s_{1\sim k}$ 的权值为 $c^{k-1}\prod_{i=1}^k F_{s_i}$ 再乘上用 $k-1$ 条边将它们连通的方案数，即每选择一条边合并两个连通块带来 $c$ 的贡献。需要返回的集合幂级数 $G$ 的 $s$ 项系数即为 $s$ 所有划分的权值和。
考虑按照两端点编号的最大值的顺序进行加边。设集合幂级数 $p_i$ 表示允许加两端点编号均 $\le i$ 的边时的答案。对于一个点集 $S$，考虑删去新加边中一端点为 $i$ 的边，形成若干个连通块 $S=P\cup T_1\cup T_2\cup\cdots\cup T_k$，其中 $P$ 包含点 $i$，其余连通块均不包含。
设集合幂级数 $q_{i-1,s}=[i\notin S]p_{i-1,s}\cdot cof(i,S)\cdot c$，其中 $cof(i,S)$ 表示 $i$ 与集合 $S$ 内编号 $\le i$ 的点的边数。容易发现有 $p_{i,s}=(p_{i-1}\cdot \exp q_{i-1})_s$，注意该式只有在 $i\in S$ 的项成立，对于其余项平凡地有 $p_{i,s}=p_{i-1,s}$。
令 $F_s$ 表示 $s$ 内连通子图数，则 $\text{Trans}(F,-1)$ 即为边双连通子图数的集合幂级数。考虑 $s$ 的一个子图，若其中存在割边，则这条割边必然分别在 $F_s$ 处和合并时贡献 $1$ 与 $-1$，即该方案不会被计入。求解 $F_s$ 是经典问题，直接求 $\ln $ 即可。
时间复杂度 $O(2^nn^3)$。
### 本题解法
我们希望将原图划分为若干黑边连通块与白边双连通分量，且这些连通块之间均用白边连接。
先求出每个集合 $s$ 作为黑边连通块的方案数。令 $F_s$ 表示 $s$ 内连通子图数，注意不能存在 $a_i,b_i$ 使得其中恰有一个点在 $s$ 内。考虑 $F'=\text{Trans}(F,-1)$，则若一种方案中存在白边，其必然会被抵消。
接下来需要求出集合 $s$ 作为白边双连通分量时的权值之和。令 $G_s$ 表示 $s$ 内连通子图权值和，注意不能存在任意 $a_i$ 或 $b_i$ 在 $s$ 内。$G$ 的求解仍可用求 $\ln$ 解决，而 $G'=\text{Trans}(G,-2)$ 即为所求。
最后只需调用 $\text{Trans}(F'+G',2)$ 合并连通块即可。
时间复杂度 $O(2^nn^3)$，经卡常可获得最优解。
附一份未经卡常的代码：
```cpp
const int S=1<<16,N=16+2,M=N*N,mod=1e9+7;
int n,m,k,u,pw2[M],pw3[M],a[N],ct[S],c1[S],c2[S],T[S],F[S],G[S],A[S],B[S];
inline void Trans(int *F,int c){
static int A[S],G[S];
for(int i=0;i<n;i++){
for(int s=0;s<u;s++)
A[s]=s>>i&1?0:1ll*c*F[s]%mod*__builtin_popcount(a[i]&s)%mod;
Poly::Exp(A,A);
Poly::Mul(A,F,G);
for(int s=0;s<u;s++)
F[s]=s>>i&1?G[s]:F[s];
}
}
int main(){
// freopen("ex_war4.in","r",stdin);
n=read(),k=read(),u=1<<n;
Prefix(u),Poly::init(u);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
int c=getc()-'0';
if(i<=j||!c) continue;
a[i]|=1<<j,ct[(1<<i)|(1<<j)]++;
}
while(k--){
int u=read()-1,v=read()-1;
c1[1<<u]++,c1[1<<v]++,c1[(1<<u)|(1<<v)]-=2;
c2[1<<u]++,c2[1<<v]++;
}
pw2[0]=pw3[0]=1;
for(int i=1;i<=n*n;i++)
pw2[i]=add(pw2[i-1],pw2[i-1]),
pw3[i]=3ll*pw3[i-1]%mod;
for(int i=0;i<n;i++)
for(int s=0;s<u;s++)
if(s>>i&1)
ct[s]+=ct[s^(1<<i)],
c1[s]+=c1[s^(1<<i)],
c2[s]+=c2[s^(1<<i)];
for(int s=0;s<u;s++)
T[s]=pw2[ct[s]];
Poly::Ln(T,F);
for(int s=1;s<u;s++)
if(!c1[s])
A[s]=F[s];
Trans(A,mod-1);
for(int s=0;s<u;s++)
T[s]=pw3[ct[s]];
Poly::Ln(T,F);
Trans(F,mod-2);
for(int s=1;s<u;s++)
B[s]=c2[s]?A[s]:F[s];
Trans(B,2);
write(B[u-1]);
flush();
}
```