YbtOJ 507「状压 dp」以线覆圆

(Updated: )
oi

题目链接：YbtOJ #507

小 A 有 $n$ 条线，长度分别为 $a_{1\sim n}$。此外，他还有一个周长为 $m$ 的圆。

现在，他想要随机将这 $n$ 条线放到圆周上（线之间可能重叠），长度为 $x$ 的线将覆盖一段长度为 $x$ 的圆弧上的所有点。

求圆上所有点都被覆盖的概率。

$2\le n\le 6$，$2\le m\le 50$，$1\le a_i < m$。

Solution

不妨先钦定所有左端点的小数部分，这样实际有用的点只有 $n\times m$ 个。

把最长的线段左端点作为原点，化圆为链。

设 $f_{i,j,k}$ 为处理完左端点小于等于 $i$ 的线段，最大右端点为 $j$，已用线段状压为 $k$ 的方案数。

由于我们对小数部分离散化过了，所以每一个左端点只可能有某一条线段，右端点也是唯一确定的，所以我们这样 DP 没有问题。

$$
f_{i+1,\min{n\times m,\max{j,i+a_x\times n}},k2^{x-1}}\texttt{+=}f_{i,j,k}
$$
时间复杂度：$O(n^2m^2\times n!\times 2^{n-1})$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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%10+'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("%.15Lf\n",(A=Ans/T/QP(m,cnt))),0;
}