[AGC020F] Arcs on a Circle

题面

你有一个长度为的圆,你在上面画了个弧。弧有长度

每一条弧随机均匀地放置在圆上:选择圆上的一个随机实点,然后出现一条以该点为中心的长度为的弧。弧是独立放置的。例如,它们可以相互交叉或包含。

现在问你圆的每一个实点被至少一个弧覆盖的概率是多少?注意一条弧覆盖了它的两个端点。

思路

问题可转换为个弧随机放置在周长为的圆上,问圆被所有弧覆盖的概率。

可以想到暴力枚举它们在圆上依次的顺序。通过表示为第个线段,为当前覆盖到~的位置,所用的线段集合为

当将圆无限细分后,得到的答案可以无误差(可是明显这样是绝对会超时的

考虑到弧长度为正整数,覆盖的左端点和右端点小数部分一样,判断两个弧是否相交仅仅只用判断小数部分相对大小。因此圆上每单位长度只用划分成段,就可以保证精度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int n ,c;
int a[500];
double dp[500][500] ,ans=0;
int main()
{
cin >> n >> c;
for(int i=1;i<=n;i++)
cin >> a[i];
sort(a+1 ,a+n+1);
int t=0;
do{
++t;
memset(dp ,0 ,sizeof(dp));
dp[a[n]*n][0]=1;
for(int i=1;i<=n*c;i++){//枚举小数部分相对位置
if(i%n==0)continue;
int x=i%n;//本次选取的线段id
for(int j=i;j<=n*c;j++){//线段覆盖位置
for(int l=0;l<(1<<n-1);l++){//选取线段的集合
if(!((1<<(x-1))&l))
dp[min(max(j ,i+a[x]*n) ,n*c)][l|(1<<(x-1))]+=dp[j][l];
// cout << dp[j][l] << endl;
}
}
}
ans+=dp[n*c][(1<<n-1)-1];
}while(next_permutation(a+1 ,a+n));//枚举每一种先后次序
int C=1;
for(int i=1;i<n;i++)
C=C*c;
//算的是方案数,需除以全部方案数获得最后所求的概率。
printf("%.12lf\n" ,ans/t/C);
}