AGC020F Arcs on a Circle 题解

· · 题解

将所有线段从短到长排序，考虑断环为链，以第 n 条线段即最长的线段的左端点作为起点，将问题转化为：最长的线段的左端点位于位置 0，其余线段的左端点在 [0,c] 上随机，求 [0,c] 都被覆盖的概率。其中，以最长的线段的左端点作为起点是为了防止存在另一条更长的线段 [x,c+y] 覆盖了 [x,c] 和 [0,y]，对 [x,c] 和 [a_n,y] 均造成贡献的情况出现。

虽然每条线段的左端点都是在实数范围内随机的，但我们其实只关心小数部分的相对大小关系，且可以认为小数部分两两不同，因此我们可以考虑直接枚举 1\sim n-1 的排列 p 表示前 n-1 条线段左端点小数部分的相对大小关系。于是我们现在得到了 nc 个整数坐标 0,1,\dots,nc-1，第 i 条线段的左端点只能放在 x \bmod n=p_i 的坐标 x 上，我们需要求出 [0,nc] 都被覆盖的概率。

考虑 dp：设 f_{i,j,S} 表示，当前考虑到坐标 i，前 j 个坐标都被覆盖了，当前使用了的线段的集合为 S 的方案数。设 i\bmod n=p_k，转移时选择使用或不使用第 k 条线段即可。由于总方案数为 c^{n-1}，所以此时覆盖 [0,nc) 的概率等于 \dfrac {f_{nc,nc,2^{n-1}-1}}{c^{n-1}}。又由于每种小数部分的相对大小关系的出现概率相等，所以答案即为每个 p 所对应的 \dfrac {f_{nc,nc,2^{n-1}-1}}{c^{n-1}} 的平均数。

直接计算即可。时间复杂度 \mathcal O(n!n^2c^22^n)。

const int N=7,C=51;
int n,c,V,a[N],p[N],rk[N];
ll ans,dp[N*C][N*C][1<<N],cnt;
void solve(){
    cin>>n>>c,V=1<<(n-1);
    for(int i=1;i<=n;i++) cin>>a[i],p[i]=i;
    sort(a+1,a+n+1);
    while(1){
        memset(dp,0,sizeof dp);
        dp[0][a[n]*n][0]=1,cnt++;
        for(int i=1;i<n;i++) rk[p[i]]=i;
        for(int i=0;i<n*c;i++){
            for(int j=i;j<=n*c;j++){
                for(int s=0;s<V;s++){
                    int k=rk[i%n];
                    dp[i+1][j][s]+=dp[i][j][s];
                    if(k!=0&&(!(s&(1<<(k-1))))) dp[i+1][min(max(j,i+a[k]*n),c*n)][s|(1<<(k-1))]+=dp[i][j][s];
                }
            }
        }
        ans+=dp[n*c][n*c][V-1];
        if(!next_permutation(p+1,p+n)) break;
    }
    printf("%.18lf",ans*1.0/cnt/pow(c,n-1));
}