[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);
}