【AtCoder Grand Contest 020 F】Arcs on a Circle | Mrsrz's blog

状压 DP，暴力。

题目大意：

给定一个长度为 $C$ 的圆，和 $n$ 条长度为整数的弧。现在把每条弧等概率放到圆上，问这些弧恰好覆盖整个圆的概率为多少。

题解：

首先我们可以钦定最长的弧的位置，并将其开始的位置记为 $0$，然后变成线段覆盖的问题。注意若不取最长的，则可能有一条弧覆盖了区间的一个后缀加一个前缀。而取最长的则避免了这个问题。

考虑两条弧的起点为 $p_i,p_j$，设 $p_i\lt p_j$。令 $[p_i]$ 表示取 $p_i$ 的整数部分，$\{p_i\}$ 表示取 $p_i$ 的实数部分。则相交有两种情况：

• $[p_i]+l_i\gt [p_j]$。

• $[p_i]+l_i=[p_j]$ 且 $\{p_i\}\gt \{p_j\}$。

由于实数部分均匀随机分布，所以可以不考虑相等的情况。容易发现，两条弧是否相交，只和它们整数部分的值和实数部分的相对大小有关。

那么可以将整个圆离散成 $nC$ 个位置。

考虑 $O((n-1)!)$ 枚举它们的相对大小并计算方案数。

使用状压 DP，令 $f[S][r]$ 表示用了集合 $S$ 中的弧，覆盖到了位置 $r$ 的方案数（$r$ 左边已经被覆盖）。

按照 $r$ 从小到大转移，每次转移所用的弧是固定的，分使用还是不使用即可。

用合法方案数除以总方案数（每条弧的整数部分有 $C$ 种取值，所以总数为 $C^{n-1}$）。

最后除以排列个数即可。

时间复杂度 $O((n-1)!2^{n-1}n^2C^2)$。

Code：

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<functional>
#include<cstring>
using namespace std;
const int N=6,nC=324;
int n,C,L[N];
int f[1<<N-1][nC];
unsigned long long ans;
int main(){
    scanf("%d%d",&n,&C);
    for(int i=0;i<n;++i)scanf("%d",L+i);
    sort(L,L+n);
    int tot=0;
    do{
        ++tot;
        memset(f,0,sizeof f);
        f[0][n*L[n-1]]=1; 
        for(int i=1;i<=n*C;++i)if(i%n){
            const int id=i%n-1,t=min(i+L[id]*n,n*C);
            for(int S=0;S<1<<n-1;++S)
            if(!(S>>id&1))
            for(int k=i;k<=n*C;++k)
            f[S|1<<id][max(k,t)]+=f[S][k];
        }
        ans+=f[(1<<n-1)-1][n*C];
    }while(next_permutation(L,L+n-1));
    printf("%.16g\n",1.*ans/tot/pow(C,n-1));
    return 0;
}