AGC020F Arcs on a Circle 题解

将所有线段从短到长排序，考虑断环为链，以第

n

条线段即最长的线段的左端点作为起点，将问题转化为：最长的线段的左端点位于位置

0

，其余线段的左端点在

[0,c]

上随机，求

[0,c]

都被覆盖的概率。其中，以最长的线段的左端点作为起点是为了防止存在另一条更长的线段

[x,c+y]

覆盖了

[x,c]

和

[0,y]

，对

[x,c]

和

[a_n,y]

均造成贡献的情况出现。

虽然每条线段的左端点都是在实数范围内随机的，但我们其实只关心小数部分的相对大小关系，且可以认为小数部分两两不同，因此我们可以考虑直接枚举

1\sim n-1

的排列

p

表示前

n-1

条线段左端点小数部分的相对大小关系。于是我们现在得到了

nc

个整数坐标

0,1,\dots,nc-1

，第

i

条线段的左端点只能放在

x \bmod n=p_i

的坐标

x

上，我们需要求出

[0,nc]

都被覆盖的概率。

考虑 dp：设

f_{i,j,S}

表示，当前考虑到坐标

i

，前

j

个坐标都被覆盖了，当前使用了的线段的集合为

S

的方案数。设

i\bmod n=p_k

，转移时选择使用或不使用第

k

条线段即可。由于总方案数为

c^{n-1}

，所以此时覆盖

[0,nc)

的概率等于

\dfrac {f_{nc,nc,2^{n-1}-1}}{c^{n-1}}

。又由于每种小数部分的相对大小关系的出现概率相等，所以答案即为每个

p

所对应的

\dfrac {f_{nc,nc,2^{n-1}-1}}{c^{n-1}}

的平均数。

直接计算即可。时间复杂度

\mathcal O(n!n^2c^22^n)

。

const int N=7,C=51;
int n,c,V,a[N],p[N],rk[N];
ll ans,dp[N*C][N*C][1<<N],cnt;
void solve(){
	cin>>n>>c,V=1<<(n-1);
	for(int i=1;i<=n;i++) cin>>a[i],p[i]=i;
	sort(a+1,a+n+1);
	while(1){
		memset(dp,0,sizeof dp);
		dp[0][a[n]*n][0]=1,cnt++;
		for(int i=1;i<n;i++) rk[p[i]]=i;
		for(int i=0;i<n*c;i++){
			for(int j=i;j<=n*c;j++){
				for(int s=0;s<V;s++){
					int k=rk[i%n];
					dp[i+1][j][s]+=dp[i][j][s];
					if(k!=0&&(!(s&(1<<(k-1))))) dp[i+1][min(max(j,i+a[k]*n),c*n)][s|(1<<(k-1))]+=dp[i][j][s];
				}
			}
		}
		ans+=dp[n*c][n*c][V-1];
		if(!next_permutation(p+1,p+n)) break;
	}
	printf("%.18lf",ans*1.0/cnt/pow(c,n-1));
}

AGC020F Arcs on a Circle 题解

文章操作

相关推荐

评论

AGC020F Arcs on a Circle 题解