提交时间:2022-07-20 11:53:06

运行 ID: 52775

#include<bits/stdc++.h> #define il inline #define ll long long using namespace std; const int maxn=25; const int maxs=(1<<21); il int read(){ int x=0; char c=getchar(); for(;!(c>='0'&&c<='9');c=getchar()); for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+c-'0'; return x; } double ans=0; ll F[maxn],f[maxn],g[maxn],cu[maxn]; int n,A,B,a[maxn],b[maxn],loc[maxn]; ll C(int n,int m){return F[n]/F[m]/F[n-m];} int main(){ n=read(),A=read(),B=read(),F[0]=1,cu[0]=1; for(int i=1;i<=n;i++) a[i]=b[i]=read(),F[i]=F[i-1]*i,loc[b[i]]=i; for(int i=1;i<=n;i++){ if(b[i]!=i){ swap(b[i],b[loc[i]]); ans+=A; } } if(B>ans) return printf("%.10lf\n",ans),0; for(int N=2;N<=n;N++){ memset(f,0,sizeof(f)); for(int i=1;i<=N;i++) g[i]=C(N,i)*F[N-i]; for(int x=1;x<=N;x++) for(int i=x;i<=N;i++) if(x-i&1) f[i]-=C(i,x)*g[i]; else f[i]+=C(i,x)*g[i]; cu[N]=F[N]; for(int i=1;i<=N;i++) cu[N]-=f[i]; } // for(int i=1;i<=n;i++) printf("%lld ",cu[i]); // printf("\n"); for(int i=0;i<=n;i++) ans=min((1.0/(C(n,i)*(cu[i]/1.0/F[i])*(1.0/F[n-i])))*B+i*A,ans); printf("%.10lf",ans); return 0; }