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