YbtOJ 507「状压 dp」以线覆圆

#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;
}