Arcs on a Circle
首先，一个非常自然的想法是尝试断环成链。怎么断呢？我们发现，选择最长线段的起点处截断是个非常好的选择，因为不可能有一个线段完全覆盖它。这之后，一个紧接着的想法就是 DP。
假如把描述中的全部“实点”改成“整点”的话，那么这题是比较 trivial 的，可以通过随便状压就出来了。
但是现在是实点。怎么办？
DP 状态里必然涉及到记录当前所有线段最远覆盖的位置，但这是个实数，不好记录。
这时候，一个不知道咋想出来的主意便产生了——我们考虑比较两个实数时的步骤，肯定是先比较整数，再比较小数。而因为所有线段长度都是整数，整数部分的大小关系是容易比较的，而小数部分可以选择离散化。具体而言，我们枚举它们小数部分的大小关系构成一个排列，然后将整个长度为 \(c\) 的环变作 \(n\times c\) 个点表示大小关系。我们枚举的排列的实际意义是，限制第一条线段的起始位置只能是 \(1,n+1,2n+1,\dots,(c-1) \times n+1\) 这些位置，再限制第二条线段的位置只能是 \(2,n+2,2n+2,\dots,(c-1) \times n+2\) 这样，大小关系确定，就可以 DP 了，只需要记得枚举完全排列后除以排列数即可。
时间复杂度 \(n!\times 2^n\times(nc)^2\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=310;
int n,c,a[6],p[6];
double f[N][1<<5][N<<1],res;
int main(){
scanf("%d%d",&n,&c);
for(int i=0;i<n;i++) scanf("%d",&a[i]),p[i]=i;
sort(a,a+n);
do{
f[0][0][a[n-1]*n]=1;
for(int i=0;i<c*n;i++){
for(int j=0;j<(1<<(n-1));j++){
for(int k=i;k<2*c*n;k++){
f[i+1][j][k]+=f[i][j][k];
if(i%n&&!(j&(1<<p[i%n-1]))){
f[i+1][j|(1<<p[i%n-1])][max(k,i+a[p[i%n-1]]*n)]+=f[i][j][k]/c;
}
f[i][j][k]=0;
}
}
}
for(int i=c*n;i<2*c*n;i++){
res+=f[c*n][(1<<(n-1))-1][i];
f[c*n][(1<<(n-1))-1][i]=0;
}
}while(next_permutation(p,p+n-1));
for(int i=1;i<n;i++) res/=i;
printf("%.11lf\n",res);
return 0;
}