题解 AT3860 [AGC020F] Arcs on a Circle

· · 题解

安利个人 blog：https://www.cnblogs.com/ET2006/

Atcoder 题面传送门 & 洛谷题面传送门

一道难度 unavailable 的 AGC F 哦

首先此题最棘手的地方显然在于此题的坐标可以为任意实数，无法放入 DP 的状态，也无法直接计算概率。我们考虑是否能将实数坐标转化为我们熟知的整数坐标。这里有一个套路，注意到每条弧的长度都是整数这个条件，考虑两个坐标 A,B，显然以 A 开始的长度为 l 的弧能覆盖到 B 当且仅当 \lfloor B\rfloor-\lfloor A\rfloor<l，或者 \lfloor B\rfloor-\lfloor A\rfloor=l 且 (B-\lfloor B\rfloor)<(A-\lfloor A\rfloor)。这就告诉我们，坐标的小数部分具体是什么并不重要，我们只关心它们的相对大小。又因为小数部分为取值范围为 [0,1) 的连续性变量，因此出现两点小数部分相同的概率可以视作 0，因此我们暴力枚举这 n 条线段小数部分的相对大小——共有 n! 种可能的情况，它们是等可能的（yyq 既视感），计算出它们覆盖整个圆周的概率后除以 n! 即可。

接下来考虑给定这 n 条线段小数部分的相对大小后怎样计算概率，首先我们固定住一条线段的位置，这样即可实现断环成链，其次由于我们已经知道了它们的相对大小了，所以最多只可能有 nc 个起点位置，故可将 c 个坐标拆成 nc 个并将线段覆盖转化为点覆盖——这个异常容易理解。我们强制要求小数部分相对大小排名为 k 的线段只能在 tn+k(t\in\mathbb{Z}) 的位置作为起始位置。这样就可以 dp 了，设 dp_{i,j,k} 表示现在覆盖了起点坐标 \leq i 的线段，当前覆盖到的右端点的最大值为 j，当前使用的线段集合为 k（这个状态设计感觉有点像此题），转移就分 i 处不放线段和放线段两种情况转移即可，显然如果 i 处放线段，那放置的线段是唯一的（i\bmod n），因此总复杂度 n!\times 2^n\times n\times c，由于此题 n 数据范围极小，可通过此题。

最后值得一提的是不少题解都没有提到一点，就是为什么一定要强制令长度最大的线段的起点为圆周的起始位置，这里稍微讲下，因为假设我们用一个长度较小的线段作为圆周的起始位置，根据我们的 DP 过程可知对于线段超过断成的链的部分我们会直接忽略，但有可能会出现长度较大的线段从链的末尾开始覆盖，由于这是一个圆周，因此多出的部分又绕回链的开头，补上链开头线段覆盖的空隙的情况，这种情况是不会被我们纳入总方案的，不过 in fact 这种方案也是合法的。而使用长度最大的线段作为开头就恰好避免的这种情况，因此需要强制令长度最大的线段的起点为圆周的起始位置。

似乎 WC2021 的时候 lyx 神仙给出了一个更优秀的解法，要什么高级插值技巧什么的，not for me，thx

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
namespace fastio{
    #define FILE_SIZE 1<<23
    char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;
    inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}
    inline void putc(char x){(*p3++=x);}
    template<typename T> void read(T &x){
        x=0;char c=getchar();T neg=0;
        while(!isdigit(c)) neg|=!(c^'-'),c=getchar();
        while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
        if(neg) x=(~x)+1;
    }
    template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}
    template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}
    void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}
}
const int MAXN=6;
const int MAXC=50;
int n,l[MAXN+2],c,p[MAXN+2];
ll dp[MAXN*MAXC+5][(1<<MAXN)+5];
int main(){
    scanf("%d%d",&n,&c);ll ret=0;
    for(int i=0;i<n;i++) scanf("%d",&l[i]),p[i]=i;
    sort(l,l+n);reverse(l,l+n);
    do {
        memset(dp,0,sizeof(dp));dp[l[p[0]]*n][1]=1;
        for(int i=1;i<n*c;i++) for(int j=i;j<=n*c;j++){
            int t=i%n;
            for(int k=0;k<(1<<n);k++) if(~k>>t&1)
                dp[min(n*c,max(j,i+l[p[t]]*n))][k|(1<<t)]+=dp[j][k];
        } ret+=dp[n*c][(1<<n)-1];
    } while(next_permutation(p+1,p+n));
    double ans=ret;//printf("%lld\n",ret);
    for(int i=1;i<=n-1;i++) ans=1.*ans/i;
    for(int i=2;i<=n;i++) ans=1.*ans/c;
    printf("%.17lf\n",ans);
    return 0;
}