YbtOJ 507「状压 dp」以线覆圆
题目链接：YbtOJ #507
小 A 有 n 条线，长度分别为 a_{1sim n}。此外，他还有一个周长为 m 的圆。
现在，他想要随机将这 n 条线放到圆周上（线之间可能重叠），长度为 x 的线将覆盖一段长度为 x 的圆弧上的所有点。
求圆上所有点都被覆盖的概率。
2le nle 6，2le mle 50，1le a_i < m
Solution
不妨先钦定所有左端点的小数部分，这样实际有用的点只有 ntimes m 个。
把最长的线段左端点作为原点，化圆为链。
设 f_{i,j,k} 为处理完左端点小于等于 i 的线段，最大右端点为 j，已用线段状压为 k 的方案数。
由于我们对小数部分离散化过了，所以每一个左端点只可能有某一条线段，右端点也是唯一确定的，所以我们这样 DP 没有问题。
时间复杂度：
Code
代码语言：javascript复制#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3) (x<<1) (c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x '0'),0):(write(x/10),pc(x '0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('n');}
}using namespace FastIO;
Cn int N=7,M=52;
int n,m,S,a[N],b[N],cnt,rk[N],f[2][(1<<N-1) 5][N*M],T;
long double Ans,A;I LL QP(LL a,RI b){LL s=1;W(b) b&1&&(s*=a),a*=a,b>>=1;return s;}
int main(){
freopen("circle.in","r",stdin),freopen("circle.out","w",stdout);
RI i,j,k,Mx=-1,id;for(read(n,m),S=1<<(n-1),i=1;i<=n;i ) read(a[i]),a[i]>Mx&&(Mx=a[id=i]);
for(i=1;i<=n;i ) i^id&&(b[ cnt]=a[i],rk[cnt]=cnt);do{
for(k=0;k<=1;k ) for(i=0;i<S;i ) for(j=0;j<=n*m;j ) f[k][i][j]=0;
for(f[1][0][Mx*n]=i=1;i<=n*m;i ) if(memcpy(f[i&1^1],f[i&1],sizeof(f[i&1])),i%n) for(j=0;j<S;j )
if(!(j>>(i%n-1)&1)) for(k=i;k<=n*m;k ) f[i&1^1][j(1<<(i%n-1))][max(k,min(n*m,i b[rk[i%n]]*n))] =f[i&1][j][k];
Ans =f[(n*m)&1][S-1][n*m],T ;
}W(next_permutation(rk 1,rk cnt 1));return printf("%.15Lfn",(A=Ans/T/QP(m,cnt))),0;
}
