P11834 Sol（省选联考 2025 D2T2）

\gdef\mst#1{\operatorname{MST}(#1)}\gdef\most#1{\operatorname{MOST}(#1)}

图计数超值全家桶。之后的省选应该不会 D2T2 稳定出一道状压图计数题吧。

下面会有大量也许无关紧要的细节，但如果你对这些知识熟悉的话其实很多地方都可以一下就想清楚。所以主要也是帮我自己整理一些图计数的思路。虽然写的不太是人话。

首先觉得不顺眼的话可以和重塑时光一样开局把概率杀了转纯方案数计算，但这题不杀的话做法貌似更好理解。所以保留概率计算。估计是这种元素概率性存在问题，直接用概率算可以更好地表示一些互相独立的信息，系数会简单一点。但是赛场上写调试难度极大，见仁见智吧。

明确一下使用的定义：

$U$ 为点全集。
$G$ 是输入给定的带权无向图；
$G"$ 为有向图形态下的 $G$ ，即 $G$ 的无向边在 $G"$ 里以成对有向边形式存在；
$G'$ 为 $G"$ 里的每一条有向边以 $\frac{1}{2}$ 的概率出现或不出现时得到的有向图。
$E(S,T)$ 为 $G$ 中连接点集 $S$ 和 $T$ 的边的数量。 $E(S)$ 为 $S$ 内部的边数。
ST 指无向图的生成树，MST 指无向图的最小生成树，OST 指有向图的外向生成树，MOST 指有向图的最小外向生成树。
$\mst G$ 为无向图 $G$ 的一棵 MST， $\most G$ 为有向图 $G$ 的一棵 MOST。
反斜杠太难打了，用正斜杠。

A 性质

直接枚举

G'

，判定是否存在

G'

的子边集为 OST 且权值等于

\mst G

即可。至此

12

分。

B 性质

\mst G

是唯一的，那么

\most{G'}

肯定为

\mst G

上每一条边定向得到，并且

G'

上其它的边没有任何限制，反正它们不可能成为合法 MOST 上的边。所以可以直接令

G\gets \mst G

，然后问题就变成了

G

是一棵树，求

G'

存在 OST 的概率，无需考虑最小性。

如果固定

G'

上的外向树根为

rt

，那么对

G'

合法性的限制其实只有，

G'

上所有朝

rt

外侧的有向边必须存在。

但实际计数时一个

G'

可以有多个合法的 OST 根，直接枚举

rt

包算重的。那就直接枚举

G'

合法 OST 根的集合

R

是什么。要求：从

R

任意一个点开始能走到全图；不存在

x\notin R

也可作为外向树根。

意会一下把条件转为更形象的东西：

R

内部每一对有向边都双向存在（

R

是强连通的）；剩下所有指向外侧的有向边都存在；不存在任何边从

R

外指向

R

内。

这三种边集不相交，所以计算三种边数各自概率乘起来即可。于是

O(2^n)

左右解决，至此

24

分。

C 性质

G'

上任意一棵 OST 都是 MOST。所以就是把 B 性质加强了一下，还是计算有多少个

G'

满足存在外向生成树，但

G

不一定是树了。

考虑还是一样枚举合法 OST 根集合

R

。答案概率还是可以跟 B 性质一样分成类似的三部分。

$R$ $R$ 强连通。
- 这是主旋律。具体做法建议到那题题解下学习。
- ~~我场上就死这了。~~
- 简单来说，考虑缩点后的 $R$ ，那么如果 $R$ 不合法它就会形成 $>1$ 个 scc 的 DAG。然后套 DAG 计数的容斥做法，但这里容斥系数看的是 scc 数（而不是更普遍的点数），不太好直接求，所以点集作为零度点的贡献带上容斥系数之和需要额外来一个 DP（奇 scc 数贡献 $-$ 偶 scc 数贡献）。
$G'$ $G^{'}$ 中（在假定 $R$ $R$ 内部已经强连通的情况下），剩下存在的边支持从 $R$ $R$ 开始可以走到全图。
- 也是一个经典的 DP 思路。设 $dp_S(S\supseteq R)$ 为从 $R$ 能走到 $S$ 内全部点的概率， $dp_R=1$ 。
- 每次转移减去不合法的概率。每次转移到 $S$ 时，枚举 $S$ 内有一个集合 $T$ ，从 $R$ 不能到，于是有转移 $dp_S=1-\sum\limits_{T\subsetneq S,T\cap R=\varnothing} dp_{S/T}\cdot 2^{-E(S/T,T)}$ ，表示限制 $G'$ 里从 $S/T$ 连向 $T$ 的所有边都不存在。直接拿 $dp_U$ 就是结果。但这个和枚举 $R$ 搞在一起是 $O(4^n)$ 的，不太牛。
- 注意所有 $R$ $R$ 的 DP 中，始态五花八门，但是终态都是一个 $dp_U$ $d p_{U}$ ，而且转移只有简单的加减乘。于是可以转置此 DP，只用从 $U$ $U$ 开始反过来做一遍就可以得到所有 $dp_R$ $d p_{R}$ 对应的结果，喜提 $O(3^n)$ $O (3^{n})$ 。
  - 关于转置 DP：
  - 把转移看成在点数 $2^n$ 的图上移动，相当于你可以从任意 $R'\supseteq R$ （注意这里的超集关系）以 $1$ 为初始权值开始走，每次从 $S/T\to S$ 的话权值要乘 $-2^{-E(S/T,T)}$ ，问 $R'\to U$ 的所有路径权值之和。
  - 如果把所有的转移方向反过来，那么结合上面意义可知此时 $U\to R'$ 算出的路径权值和正向时的 $R'\to U$ 是一样的。
  - 然后因为有个 $R'\supseteq R$ ，所以反向 DP 完之后还要做超集和。
不存在任何边从 $R$ $R$ 外指向 $R$ $R$ 内。
- 一个简单细节：为什么这个概率和前两个是独立的？
  - 显然它和强连通部分独立。
  - $U/R\to R$ 边的存在性和 $R$ 到全图的可行性没有关系。具体来说，就算这样的边加上了，你也只能可能可以从外面的某个点再走回到 $R$ ，不影响你能不能从 $R$ 走到外面的某个点。
- 概率为 $2^{-E(U/R,R)}$ 。

O(3^n)

，至此

64

分。代码。

正解

这里开始才需要真正跟 MST 的条件硬刚。现在是计算

G'

里有 MOST，且其权值等于

\mst G

的概率。我们需要想一些方法刻画它。

如果你做过类似的题，或者是从 B 性质 MST 唯一的结论受到启发，或者是狂暴分析了 Kruskal 操作的性质，那么你会知道，去按边权分层转化为连通性问题是一个不错的选择。

结论：设 $G_x$ $G_{x}$ 是图 $G$ $G$ 只保留权值 $\le x$ $\leq x$ 的边得到的图， $T$ $T$ 是 $G$ $G$ 的任意一棵 MST。设 $T'$ $T^{'}$ 是 $G$ $G$ 的一棵 ST，那么当且仅当对于所有 $x$ $x$ 都满足， $T_x$ 和 $T'_x$ 中每一对点的可达性都相同（或者说它们形成了相同的连通块）， $T'$ $T^{'}$ 才是 $G$ $G$ 的一棵 MST。
- 证明直接考虑 Kruskal 的过程。
考虑如何类比这个结论先判断 $G'$ 是否有 MOST。
这个结论是对于无向图的，所以对有向图 $G'$ 还要加一个限制就是，对于所有 $x$ 都满足， $G'_x$ 的各个连通块里都存在 OST，并限制 $G'_x$ 的 “OST” 必须由 $G'_{x-1}$ 各个连通块的 “OST” 加上权值 $=x$ 的几条有向边得到。
这样做完， $G'$ 里的 “OST” 一定就是它的 MOST 了。现在只需考虑这个 MOST 的权值是否和 $G$ 的相同。

可以计数了。按边权从小到大处理这些边是否在

G'

中出现。假设现在我们统一处理边权为

w

的边，

\le w-1

的边的选取情况已经确定。

那这个时候，根据

G

，我们一定知道，

G'_{w-1}

形成了哪几个连通块；

G'_{w-1}\to G'_w

是哪些小连通块合并成了大连通块。这是固定的。问题只在于，需要把这些各自有 OST 的小连通块，用

=w

的边连成一个也有 OST 的大连通块。这部分看起来就很像 C 性质。

只要严格根据 $G$ 各层的连通性进行合并，就能保证最终 $G'$ MOST 的权值和 $G$ 相同。

细细地盘一下每次

=w

需要做什么。以下的连通块指的全部都是弱连通块。

称一个连通块中，可以作为这个连通块的某个 MOST 的根的所有点，为“根点”。其余为非根点。
维护 $f_{w,R}$ 表示， $R$ 集合恰好为 $G'_w$ 中，其所在的连通块的根点集合，的概率。令 $R$ 必须全部在同一个连通块中才有意义。
假设现在需要把 $k$ 个连通块 $P_1,P_2,\cdots,P_k$ 用 $=w$ 的边全部合并成一个大连通块 $P$ 。
跟 C 性质相比主要多的细节在于，每个小连通块内的所有点都能对其它连通块输出有效的出边，但是只有根点能接受有效的入边。一个小连通块入边如果全部连到非根点就是不合法的，因为根点依然不可达。所以连边的时候需要多几个心眼子。
- 枚举大连通块的根点集合 $R$ 。
- 设点集 $S$ 里的点出现在的小连通块集合为 $sc_S$ 。
- 依然把概率分为独立的几部分。
  - 这次多了一部分概率：我们还需要让 $R$ 的点在 $G'_{w-1}$ 就是各自小连通块里的根点，并且这些小连通块没有别的根点不在 $R$ 里（不然 $G'_w$ 的根点就不只有 $R$ 了）。这在接下来设计 DP 的时候可以一起处理。
- 从 $R$ $R$ 能走到其它所有的连通块（以及 $R$ $R$ 里的点为各自小连通块的根点）。
  - 方法很多。感觉这篇题解的 DP 设法比较好看，解释一下。
  - 很多人第一反应是设能到的连通块集合为 $S$ 然后转移。
  - 但实际上因为连边的时候我们只关心小连通块的根点集合，所以 DP 状态里也可以只存这些根点。反正只要知道哪些根点能到，就知道哪些小连通块可以到了。并且还可以把多出来的那一部分概率（ $R$ 为小连通块根点）给处理了。
  - 设 $dp_S$ 为从 $R$ 开始，可以走到的小连通块根点集合为 $S$ 的概率。这个状态同时隐含了一个“从 $R$ 可以走到的连通块集合恰好为 $sc_S$ ”的条件，所以就不需要单独把 $sc_S$ 开进状态了。
  - 可以预处理一个 $be_S$ 表示， $sc_S$ 里的所有小连通块，它们的根点集合恰好组成了 $S$ 的概率。
  - 那么有转移 $dp_S=be_S-\sum\limits_{T\subsetneq S,sc_T\cap sc_{S/T}=\varnothing}2^{-E(sc_{S/T},T)}dp_{S/T}be_T$ 。注意这里多出来的几个 $sc$ 。
  - 依然可以用类似的方法转置成 $O(3^n)$ 。
  - 注意 $S$ 只要满足 $sc_S$ 包含了被合成一个大连通块的所有小连通块，它就是一个终态。
- $R$ $R$ 强连通。
  - 对 $=w$ 的边跑主旋律。这里要魔改一下，根据定义，我们假定在同一个小连通块的根点一定是强连通的。这个概率在前一部分已经算过了。
  - 那么容斥的 $T$ 和 $S/T$ 里不能出现同一个小连通块。转移系数也有一点变化。
- 没有边从完全与 $R$ $R$ 不交的连通块里的点连进 $R$ $R$ 。
  - 这是简单的。
- 乘起来就获得了大连通块的 $f_{w,R}$ 。

时间复杂度？每次

w-1\to w

时不需要管没有任何动静的连通块。瓶颈在每次的

O(3^n)

上，加上这个优化后容易知道总共还是

O(3^n)

的。

于是，我们通过了此题……

CPP

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mms(x) memset(x,0,sizeof(x))
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9;
const ll J=1e18,N=15,M=507,P=1e9+7;
ll qp(ll x,ll y=P-2) { return y?(y&1?x:1)*qp(x*x%P,y>>1)%P:1; }
ll type,n,m,U,p2[M],q2[M];
ll ee[1<<N],sc[1<<N],nsc[1<<N],be[1<<N],is[1<<N],cn[N],to[N];
ll f[1<<N],g[1<<N],dp[1<<N],ans[1<<N];
struct dsu {
	ll f[N];
	void ini() { iota(f,f+N,0); }
	ll fnd(ll x) { return f[x]==x?x:f[x]=fnd(f[x]); }
	void mrg(ll x,ll y) { f[fnd(x)]=fnd(y); }
} D;
struct edg { ll x,y,z; } b[M];
ll ce(ll s,ll t) { return ee[s|t]-ee[s]-ee[t]; }
void mian() {
	scanf("%lld%lld",&n,&m),U=(1<<n)-1,D.ini(),mms(ans);
	for (ll i=0,x,y,z;i<m;i++) scanf("%lld%lld%lld",&x,&y,&z),x--,y--,b[i]={x,y,z};
	sort(b,b+m,[](edg x,edg y){return x.z<y.z;});
	for (ll i=0;i<n;i++) ans[1<<i]=1,cn[i]=1<<i;
	for (ll s=1;s<=U;s++) nsc[s]=s;
	for (ll l=0,r;l<m;l=r+1) {
		for (r=l;r+1<m&&b[r+1].z==b[l].z;r++);
		swap(sc,nsc),mms(ee),mms(nsc),mms(be),mms(is),mms(to),mms(f),mms(g),mms(dp);
		for (ll i=l;i<=r;i++) if (D.fnd(b[i].x)!=D.fnd(b[i].y))
			cn[D.fnd(b[i].y)]|=cn[D.fnd(b[i].x)],D.mrg(b[i].x,b[i].y);
		for (ll i=l;i<=r;i++) to[b[i].x]|=1<<b[i].y,to[b[i].y]|=1<<b[i].x;
		be[0]=1;
		for (ll s=1;s<=U;s++) {
			be[s]=be[s^(s&sc[s&-s])]*ans[s&sc[s&-s]]%P,
			nsc[s]=nsc[s^(s&cn[D.fnd(__lg(s&-s))])]|cn[D.fnd(__lg(s&-s))];
			for (ll i=l;i<=r;i++) ee[s]+=s>>b[i].x&1&&s>>b[i].y&1;
		}
		for (ll i=0;i<n;i++) if (D.fnd(i)==i) {
			for (ll s=cn[i];s;s=(s-1)&cn[i]) nsc[s]=cn[i];
			if (sc[1<<i]!=nsc[1<<i]) for (ll s=cn[i];s;s=(s-1)&cn[i]) is[s]=1;
		}
		for (ll s=1;s<=U;s++) if (is[s]) {
			f[s]=1;
			for (ll t=s;t;t=(t-1)&s) if (t&(s&-s)&&(sc[s^t]&sc[t])==0)
				(g[s]+=P-f[t]*g[s^t]%P*q2[ce(sc[s^t],t)+ce(s^t,sc[t])]%P)%=P;
			for (ll t=s;t;t=(t-1)&s) if ((sc[s^t]&sc[t])==0) (f[s]+=P-g[t]*q2[ce(sc[s^t],t)]%P)%=P;
			(g[s]+=f[s])%=P;
		}
		for (ll s=1;s<=U;s++) if (is[s]) {
			ll cnm=0,t=__lg(s&-s);
			for (ll i=0;i<n;i++) if (nsc[1<<i]==nsc[1<<t]&&(sc[1<<i]&sc[s])==0)
				cnm+=__builtin_popcount(to[i]&s);
			(f[s]*=q2[cnm])%=P;
		}
		for (ll s=1;s<=U;s++) if (is[s]) {
			ll flg=1,t=__lg(s&-s);
			for (ll i=0;i<n;i++) if (nsc[1<<i]==nsc[1<<t]&&(sc[1<<i]&s)==0) { flg=0; break; }
			dp[s]=flg;
		}
		for (ll s=U;s;s--) if (is[s]) {
			for (ll t=(s-1)&s;t;t=(t-1)&s) if ((sc[s^t]&sc[t])==0)
				(dp[s^t]+=dp[s]*(P-q2[ce(sc[s^t],t)])%P*be[t])%=P;
		}
		for (ll s=1;s<=U;s++) if (dp[s]) {
			(dp[s]*=be[s])%=P;
			for (ll t=(s-1)&s;t;t=(t-1)&s) if ((sc[s^t]&sc[t])==0) (dp[t]+=dp[s])%=P;
		}
		for (ll s=1;s<=U;s++) if (is[s]) ans[s]=dp[s]*f[s]%P;
	}
	ll tot=0;
	for (ll s=1;s<=U;s++) (tot+=ans[s])%=P;
	cout<<tot<<"\n";
}
bool ORY; int main() {
	p2[0]=q2[0]=1;
	for (ll i=1;i<M;i++) p2[i]=p2[i-1]*2%P,q2[i]=qp(p2[i]);
	// while (1)
	int t; for (scanf("%lld%d",&type,&t);t--;)
	mian();
	cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB";
	return 0;
}

难度相比去年重塑时光的话算是全面超级加强了吧。重塑时光也就涉及到了 DAG 计数的套路，以及一个不加也能过的插值优化。但这题包含了 DAG 计数，SCC 计数，MST 计数等等各种奇怪但经典的东西，而且应用形式都比较灵活，细节非常多，一旦里面有任何一个不熟悉就很难获得较高的分数。

~~所以也很难想象明年 D2T2 如果还要出状压图计数的话要放什么东西了。~~

总之用这题来检验一下自己对图计数的理解我觉得是非常好的。我检验过了，我不理解。

25-5-6 upd：修改了一些用词，希望能明白一些。

P11834 Sol（省选联考 2025 D2T2）

文章操作

A 性质

B 性质

C 性质

正解

相关推荐

评论

P11834 Sol（省选联考 2025 D2T2）