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