[AGC020F] Arcs on a Circle [* hard]
给定一个长度为 (C) 的圆，在上面随机放置若干个长度为 (L_i) 的弧，求这些弧覆盖了圆上所有的点的概率。
(2le Nle 6,Cle 50,L_i<C)
Solution
很神奇的搞法，首先，可以忽略存在两个弧小数部分相同的概率，这是一个高阶小量，然后，一个事实是，由于输入的 (L_i) 都是整数，所以小数部分似乎只 care 相对大小关系，依次来判断相交与否。
考虑 (N!) 枚举小数部分的相对大小关系，接下来考虑问题等价于：
有一个长度为 (NC) 的圆（对于 (C) 中的每个整数位，我们相应扩充出 (N) 个“相对大小的小数位”）然后第 (i) 条线段长度为 (NL_i)，其起始位置只能为 (mod C=p_i) 的下标，求这些线段覆盖整个圆的概率。
我们发现 (L) 最大的线段不可能被别人包含，于是考虑从其起点处断环为链，不难发现此时问题等价于求所有可能的方案中，有多少种方案满足可以从起点走到 (NC) 处，以及更往后的位置。
- 也可以钦定 (L) 最大的线段处下标为 (0)，这样只需要枚举 ((N-1)!) 种相对大小关系。
此时已经得到了一个 (mathcal O(C^NN! imes NC)) 的解法。
考虑使用状压 dp 解决这一问题，我们可以这样考虑，我们先给这些元素按照整数大小为第一关键字，小数部分为第二关键字进行排序，于是依次考虑每个元素，新加入一个元素的时候如果方案是合法的，那么必然有其小于当前衍生到的最右点，于是又可以得到一个 (mathcal O(N!cdot (NC)^2)) 的做法。
事实上，我们可以直接使用状压 dp 来处理对相对大小关系的枚举，设 (f_{l,r,S}) 表示当前最远衍生到了 (r) 处，当前最大的左端点为 (l) 处，且用掉了集合 (S) 的方案数，此时，可以得到一个 (mathcal O((N-1)!2^{N}(NC)^2 imes NC)) 的做法。
可以考虑更换状态以得到更加优秀的做法，设 (f_{l,r,S}) 表示考虑到位置 (l)，集合 (S) 已经被使用，最远衍生到 (r) 处的方案数，则转移只需要考虑 (l) 处是否放入节点即可。复杂度 (mathcal O((N-1)!2^{N}(NC)^2))
(Code:)
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define mp make_pair
#define pi pair<int, int>
#define pb push_back
#define vi vector<int>
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ;
return cn * flus ;
}
const int N = 7 ;
const int M = 300 + 5 ;
int n, C, L[N], A[N], Id[N] ;
double f[M][M][1 << 6], Ans ;
signed main()
{
n = gi(), C = gi() ;
rep( i, 1, n ) L[i] = gi(), A[i] = i ;
sort(L + 1, L + n + 1) ;
do {
memset( f, 0, sizeof(f) ) ;
int lim = n * C, limit = (1 << (n - 1)) - 1 ;
f[0][n * L[n]][0] = 1 ; double d = 1 ;
rep( i, 2, n ) d = d * C ;
rep( i, 1, lim ) {
rep( S, 0, limit ) rep( r, i, lim ) f[i][r][S] = f[i - 1][r][S] ;
if(i % n) {
int u = (1 << (A[i % n] - 1)), v = A[i % n] ;
rep( S, 0, limit ) rep( r, i, lim ) {
if(S & u) continue ;
f[i][min(lim, max(r, i + n * L[v]))][S | u] += f[i - 1][r][S] ;
}
}
}
double ans = f[lim][lim][limit] / d ;
Ans += ans ;
} while(next_permutation(A + 1, A + n)) ;
rep( i, 1, n - 1 ) Ans /= i ;
printf("%.11lf
", Ans ) ;
return 0 ;
}