题解 AT3860 [AGC020F] Arcs on a Circle
tzc_wk
2021-03-16 00:04:07
安利个人 blog：https://www.cnblogs.com/ET2006/
[Atcoder 题面传送门](https://atcoder.jp/contests/agc020/tasks/agc020_f) & [洛谷题面传送门](https://www.luogu.com.cn/problem/AT3860)
~~一道难度 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$（这个状态设计感觉有点像[此题](https://www.luogu.com.cn/problem/CF559E)），转移就分 $i$ 处不放线段和放线段两种情况转移即可，显然如果 $i$ 处放线段，那放置的线段是唯一的（$i\bmod n$），因此总复杂度 $n!\times 2^n\times n\times c$，由于此题 $n$ 数据范围极小，可通过此题。
最后值得一提的是不少题解都没有提到一点，就是为什么一定要强制令**长度最大的线段**的起点为圆周的起始位置，这里稍微讲下，因为假设我们用一个长度较小的线段作为圆周的起始位置，根据我们的 DP 过程可知对于线段超过断成的链的部分我们会直接忽略，但有可能会出现长度较大的线段从链的末尾开始覆盖，由于这是一个圆周，因此多出的部分又绕回链的开头，补上链开头线段覆盖的空隙的情况，这种情况是不会被我们纳入总方案的，不过 in fact 这种方案也是合法的。而使用长度最大的线段作为开头就恰好避免的这种情况，因此需要强制令长度最大的线段的起点为圆周的起始位置。
~~似乎 WC2021 的时候 lyx 神仙给出了一个更优秀的解法，要什么高级插值技巧什么的，not for me，thx~~
```cpp
#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;
}
```