自动搬运

查看原文

来自洛谷，原作者为

	FZzzz **

搬运于2025-08-24 22:27:00，当前版本为作者最后更新于2020-12-26 22:10:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑最短路树，对于深度为 $i$ 的某个点，深度小于 $i-1$ 的点不能向其连边，至少有一个深度为 $i-1$ 的点向其连边，对于其他点连向它的边没有限制。

这启发我们分层状压 dp。设 $f_{d,s_1,s_2}$ 为，深度为 $d$ 的点的集合为 $s_1$，深度小于等于 $d$ 的点的集合为 $s_2$，只考虑连向深度大于 $d$ 的点的边的限制，时，图满足条件的概率。

考虑转移。枚举深度为 $d+1$ 的点的集合 $s_3$，则 $s_1-s_2$ 内的点都不能向 $s_3$ 内的点连边，且对于 $s_3$ 内的每一个点，$s_2$ 内至少有一个点需要向其连边。dp 值即为每个这样的 $s_3$ 符合条件的概率之和。

直接实现即可做到 $O(\operatorname{poly}(n)4^n)$ 的复杂度，因为这个 dp 实际上相当于枚举子集的子集。

对于每个 $s_1$ 和 $s_2$，预处理 $s_1$ 内的点都不向 $s_2$ 内的点连边的概率，和对于每个 $s_2$ 内的点 $s_1$ 内的点至少有一个向其连边的概率。这部分可以在 $O(3^n)$ 至 $O(n4^n)$ 不等的时间内完成。预处理后每次转移的复杂度降为 $O(1)$，总时间复杂度为 $O(n4^n)$。

需要进行一些卡常卡空间。

下面是我的最终代码，使用了滚动数组进行优化，空间 $O(4^n)$。理论上最好可以做到 $O(3^n)$ 空间。

#include<bits/stdc++.h>
using namespace std;
inline int readint(){
	int x=0;
	bool f=0;
	char c=getchar();
	while(!isdigit(c)&&c!='-') c=getchar();
	if(c=='-'){
		f=1;
		c=getchar();
	}
	while(isdigit(c)){
		x=x*10+c-'0';
		c=getchar();
	}
	return f?-x:x;
}
const int maxn=12;
int n,k;
const int mod=998244353;
int ksm(int a,int b){
	int ans=1;
	while(b){
		if(b%2==1) ans=1ll*ans*a%mod;
		a=1ll*a*a%mod;
		b/=2;
	}
	return ans;
}
inline void mul(int& x,int y){
	x=1ll*x*y%mod;
}
int p[maxn+5][maxn+5];
int f[2][(1<<maxn)+5][(1<<maxn)+5];
int g[(1<<maxn)+5][(1<<maxn)+5],h[(1<<maxn)+5][(1<<maxn)+5];
int main(){
	#ifdef LOCAL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	n=readint();
	k=readint();
	for(int i=0;i<n*(n-1);i++){
		int x,y;
		x=readint()-1;
		y=readint()-1;
		p[x][y]=readint();
		mul(p[x][y],ksm(readint(),mod-2));
	}
	int all=(1<<n)-1;
	for(int s1=0;s1<=all;s1++){
		for(int i=0;i<n;i++) if(!(s1>>i&1)){
			g[s1][1<<i]=1;
			for(int j=0;j<n;j++) if(s1>>j&1) mul(g[s1][1<<i],(1-p[j][i]+mod)%mod);
		}
		for(int s2=all^s1;s2;s2=(s2-1)&(all^s1)) if((s2&-s2)!=s2){
			g[s1][s2]=1;
			for(int i=0;i<n;i++) if(s2>>i&1) mul(g[s1][s2],g[s1][1<<i]);
		}
	}
	for(int s1=0;s1<=all;s1++){
		for(int i=0;i<n;i++) if(!(s1>>i&1)) h[s1][1<<i]=(1-g[s1][1<<i]+mod)%mod;
		for(int s2=all^s1;s2;s2=(s2-1)&(all^s1)) if((s2&-s2)!=s2){
			h[s1][s2]=1;
			for(int i=0;i<n;i++) if(s2>>i&1) mul(h[s1][s2],h[s1][1<<i]);
		}
	}
	f[(k+1)%2][all][0]=1;
	for(int d=k;d>=0;d--) for(int s1=1;s1<=all;s1++){
		f[d%2][s1][0]=s1==all;
		for(int s2=s1;s2;s2=(s2-1)&s1){
			long long res=s1==all;
			for(int s3=all^s1;s3;s3=(s3-1)&(all^s1))
				res+=1ll*f[!(d%2)][s1|s3][s3]*g[s1^s2][s3]%mod*h[s2][s3]%mod;
			f[d%2][s1][s2]=res%mod;
		}
	}
	printf("%d\n",f[0][1][1]);
	return 0;
}