专栏文章

省选联考 2025 D2T2 题解

220_200
P11834题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipzocqm
此快照首次捕获于
2025/12/03 20:34
3 个月前
此快照最后确认于
2025/12/03 20:34
3 个月前
查看原文
一年前，你首次亮相，我满怀悲痛的走出考场。
一年的岁月磨灭了那悲痛的痕迹，我时不时幻想着一年后的那天能够重塑时光。
而当这一天真的来临，你竟然再次出现，虽经历岁月侵蚀，但核心却仍然保持不变。
我却只能在无尽的代码中苦苦挣扎，面对着即便重塑时光依旧无法改变的必死结局，追忆这逝去的青春岁月。
题意
给定一个 nn 个点 mm 条边的带权无向图，现在每条边对应的正反向边都有 12\frac{1}{2} 的概率被删除，求删边后的有向图存在最小外向生成树且其权值和等于原图最小生成树的概率。
分析
因为总方案数有限，所以直接把概率转计数，最后再除以 22m2^{2m}，虽然直接算概率能省去很多系数但是概率全是分数debug过于困难。
定义 A/BA/B 表示集合 AA 去掉集合 A∩BA\cap B 得到的集合。
定义一个有向图弱连通当且仅当将其所有边看作无向图后连通，有向图的 MST 为其最小外向生成树。
定义一个有向图合法当且仅当将其存在 MST，可以发现这等价于将其缩点后只有一个入度为零的强连通分量。接下来我们只讨论合法的有向图。
定义合法有向图的关键点集为可以作为MST的根的点集，显然该点集强连通。
显然删边后的有向图 MST 的权值和大于等于原图 MST，而根据 Kruskal 算法的原理，两者相等的必要条件是对任意 i∈[1,m]i\in[1,m]，加入所有边权 ≤i\le i 的边，得到的图的弱连通性与原图加入所有边权 ≤i\le i 的边后的图相同，且每个弱连通分量都合法。
我们对每个 ii 的每个弱连通分量分别考虑（注意因为原图的边是给定的，所以这里的弱连通分量是固定的），我们需要选择一些该弱连通分量中边权为 ii 的边，把若干个由边权 <i<i 的边组成的合法弱连通分量合并成一个。
对于一个边权-弱连通分量 kk，设其点集为 AkA_k，对应的边权为 vkv_k，其合并集为 CkC_k，即 Ak=∪x∈CkAxA_k=\cup_{x\in C_k}A_x 的，该连通分量中权值等于 vkv_k 的边集为 EkE_k。现在只考虑 EkE_k 中的边，定义两端点不在同一个 AxA_x，且终点为某个 AxA_x 的关键点的边称为关键边。
由于在任意一个 MST 中，每个 AxA_x 的入度不超过一，因此，最终的 MST 只可能包含关键边。那么对于上面所说的必要条件，可以发现，若只考虑关键边，则上述条件变为充要条件，因为对每个边权-弱连通分量 kk，从关键点出发就可以充分利用边权 ≤vk\le v_k 的所有边，而关键边都会连接到关键点，若仅靠关键边就能保持弱连通和合法性，则可以选择和原图数量相同的边权为 vkv_k 的边并充分利用边权小于 vkv_k 的边，使得 AkA_k 的 MST 等于原图。
而一条边是否关键只与其对应 AxA_x 的关键点集有。所以，对每个 kk，将 x∈Ckx\in C_k 的每个 AxA_x 看作一个点，这些点和关键边组成一个有向图，则选择的关键边应使得该图合法，而 AkA_k 的关键点集为该图的关键点集对应的 AxA_x 对应的关键点集的并集。
那么现在这题的思路就很明确了，状态只需要记录关键点集，然后由于关键点集的强连通性，还需要做强连通计数。
DP
这个部分基本是和重塑时光一脉相承的东西，核心思想就是容斥入度为零的点（强联通分量）。
考虑设计 dp 状态，设 dpk,S\text{dp}_{k,S} 表示选择两端点都在 AkA_k 中的边使得 AkA_k 合法且其关键点集是 SS 的方案数。
下面计算某一个 kk 的 dp，以下讨论的 SS 为 AkA_k 的子集。
定义 cnt(S,T)=2∑[x∈S][y∈T][(x,y)∈Ek]cnt(S,T)=2^{\sum[x\in S][y\in T][(x,y)\in E_k]}。
设 uSu_S 表示所有 S∩Ax≠∅S\cap A_x\neq\varnothing 的 xx 构成的集合，dS=∪x∈uSAxd_S=\cup_{x\in u_S}A_x。
设 fSf_S 表示对于 x∈uSx\in u_S，AxA_x 的关键点集为 S∩AxS\cap A_x，用关键边将 uSu_S 合并成一个强连通分量的方案数。
设 gS=∑T1,T2,…,Tx(−1)x∏i=1xfTig_S=\sum_{T_1,T_2,\dots,T_x}(-1)^x\prod_{i=1}^xf_{T_i}，其中 T1,T2,…,TxT_1,T_2,\dots,T_x 是 SS 的无序划分，且对于 i≠ji\neq j，uTi∩uTj=∅u_{T_i}\cap u_{T_j}=\varnothing，即 SS 带容斥系数的划分的 ff 的贡献和。
fSf_S 的转移考虑容斥，uSu_S 强连通相当于所有连边方案减去不是强连通的情况，即有多个入度为零的强连通分量或者有一个入度为零且不等于 uSu_S 的强连通分量，那么我们钦定有 kk 个入度为零强连通分量并确定关键点集，剩下点的关键边随便连，这里容斥系数为 −(−1)k−1=(−1)k-(-1)^{k-1}=(-1)^k，可以直接用 gg，最后减去 k=1k=1 且该强连通分量等于 uSu_S 的情况，得到
fS=cnt(dS,S)−fS+∑T⊆S,T≠∅,uT∩uS/T=∅gT×cnt(dT,S/T)f_S=cnt(d_S,S)-f_S+\sum_{T\subseteq S,T\neq\varnothing,u_T\cap u_{S/T}=\varnothing}g_T\times cnt(d_T,S/T)
gSg_S 的转移，由于其无序性，考虑每次划分出一个包含 SS 中编号最小的点（即 lowbit）的点集 TT 作为一个强连通分量并确定关键点集，乘以 −1-1 的容斥系数，得到
gS=−∑T⊆S,T≠∅,uT∩uS/T=∅,lowbit(S)∈TfT×gS/Tg_S=-\sum_{T\subseteq S,T\neq\varnothing,u_T\cap u_{S/T}=\varnothing,\text{lowbit(S)}\in T}f_T\times g_{S/T}
注意这里 ff 和 gg 相互转移，要先转移 gSg_S，由于 fSf_S 还没转移，此时得到的 gSg_S 刚好没算上 fSf_S，可以用来转移 fSf_S，这样 fSf_S 的转移里面就不用减去自己，在 fSf_S 转移完后再把 gSg_S 减去 fSf_S 即可。
设 hTh_T 为对所有 Ck/uTC_k/u_T 中的 AxA_x 选择关键点集和关键边，还有选择非关键边和两端点都在 AkA_k 中且权值 <vk\lt v_k 的边的方案数，考虑所有 AxA_x 的关键点集的并为 SS，则
hT=∑T⊆S⊆Ak,uS=Ckcnt(dS,dS/S)×cnt(dS,S/T)∏x∈Ckdpx,S∩Axh_T=\sum_{T\subseteq S\subseteq A_k,u_S=C_k}cnt(d_S,d_S/S)\times cnt(d_S,S/T)\prod_{x\in C_k}\text{dp}_{x,S\cap A_x}
dpk,T\text{dp}_{k,T} 的转移，这里 TT 作为 AkA_k 的关键点集，是缩点后唯一的入度为零的强连通分量，那么仍然考虑容斥，钦定除了 TT 外还有一些入度为零的强连通分量（也可能没有）并确定关键点集，TT 和它们的并为 SS，发现还是可以用 gg 自带的容斥系数，再乘上 SS 外的部分和非关键边的方案数 hh，那么得到
dpk,T=∑T⊆S⊆Ak,uT∩uS/T=∅fT×gS/T×hS\text{dp}_{k,T}=\sum_{T\subseteq S\subseteq A_k,u_T\cap u_{S/T}=\varnothing}f_T\times g_{S/T}\times h_S
初始状态是 g∅=h∅=1g_\varnothing=h_\varnothing=1，对于每个点 xx，若只有它一个点的集合为 AkA_k，则 dpk,{x}=1\text{dp}_{k,\{x\}}=1。
答案就是 {1,2,…,n}\{1,2,\dots,n\} 对应的 kk（注意不一定是最大的）的所有 dp 值求和 ×2−2m\times2^{-2m}。
注意对每个 kk 都需要特判掉 EkE_k 中两端点都在同一个 AxA_x 的边，最后算概率除的时候也不能除这些边。
还要注意转移的条件。
复杂度瓶颈在于 cnt，直接算是要 O(n2)O(n^2) 的，而将每个点的出边用二进制数存就成 O(n)O(n) 了，可以过。后来看别的题解好像可以做到 O(1)O(1)，但是我懒得改了。
时间复杂度 O(T3nn)O(T3^nn)。
代码
目前写过的最长非 NTT 计数题，细节巨多，非常难调。
代码经过优化，截至提交时是最短解（2.03KB），变量名和上面说的一样，可以辅助理解一些细节。
CPP
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<ll,ll>
#define ve vector<ll>
#define fi first
#define se second
#define pb push_back
#define mid (l+r>>1)
#define lx (x<<1)
#define rx (x<<1|1)
using namespace std;
const ll N=502,M=(1<<15)+2,P=1e9+7;
ll T,n,m,a[N],e[N],p[N],v[N];
ll d[M],f[M],g[M],h[M],dp[N][M];
vector<pii>b[N];
vector<ll>c[N];
ll find(ll x){return x==p[x]?x:p[x]=find(p[x]);}
ll cnt(ll s,ll t){
	ll x=1;
	for(ll i=0;i<n;i++)
		if(s>>i&1)(x*=1<<__builtin_popcount(t&e[i]))%=P;
	return x;
}
void DP(ll k){
	g[0]=h[0]=1;
	for(ll s=1;s<(1<<n);s++){
		f[s]=g[s]=h[s]=d[s]=0;
		if((s&a[k])!=s)continue;
		ll x=1,y;
		for(ll i:c[k])
			if(s&a[i])d[s]|=a[i],(x*=dp[i][s&a[i]])%=P;
		(x*=cnt(d[s],d[s]^s))%=P;
		for(ll t=s;t;t=(t-1)&s)
			if(!(d[t]&d[s^t])){
				y=cnt(d[s],s^t),(f[s]+=g[t]*y)%=P;
				if((t|(s&-s))==t)(g[s]-=f[t]*g[s^t])%=P;
				if(d[s]==a[k])(h[t]+=x*y)%=P;
			}
		(f[s]+=g[s]+cnt(d[s],s))%=P;
		(g[s]-=f[s])%=P;
	}
	for(ll s=1;s<(1<<n);s++)
		for(ll t=s;d[s]&&t;t=(t-1)&s)
			if(!(d[t]&d[s^t]))(dp[k][t]+=f[t]*g[s^t]%P*h[s])%=P;
}
void slv(){
	cin>>n>>m;
	ll k=0,ans=0,u=0,w=1;
	memset(dp,0,sizeof dp);
	for(ll i=1;i<=m;i++)b[i].clear();
	for(ll i=1,x,y,z;i<=m;i++)
		cin>>x>>y>>z,b[z].pb({x,y});
	for(ll i=0;i<n;i++)
		a[++k]=1<<i,dp[k][a[k]]=1,
		p[k]=k,v[k]=0,c[k].clear();
	for(ll i=1;i<=m;i++){
		for(ll j=0;j<n;j++)e[j]=0;
		for(pii j:b[i])
			if(find(j.fi)!=find(j.se))
				e[j.fi-1]|=1<<(j.se-1),e[j.se-1]|=1<<(j.fi-1),
				(w*=(P+1)/4)%=P;
		for(pii j:b[i]){
			ll x=find(j.fi),y=find(j.se);
			if(x!=y){
				if(v[x]<v[y])swap(x,y);
				if(v[x]==i){
					if(v[y]==i)
						for(ll j:c[y])c[x].pb(j);
					else c[x].pb(y);
					p[y]=x,a[x]|=a[y],v[y]=0;
				}
				else
					p[x]=p[y]=++k,p[k]=k,v[k]=i,
					a[k]=a[x]|a[y],c[k].clear(),
					c[k].pb(x),c[k].pb(y);
			}
		}
		for(ll j=1;j<=k;j++)
			if(v[j]==i)DP(j),u=j;
	}
	for(ll s=1;s<(1<<n);s++)(ans+=dp[u][s])%=P;
	cout<<(ans*w+P*P)%P<<'\n';
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T>>T;
	while(T--)slv();
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...