题目链接：The Halfwitters
题目来源：神人模拟赛 B 题
定位：区分题

题意

三种操作：花费代价 $a$ 交换两个相邻位置，花费代价 $b$ 翻转整个排列，花费代价 $c$ 使得当前排列等概率变成任意排列。
$T$ 组数据，每次给定 $n,a,b,c$，然后有 $q$ 组询问一个排列 $p_i$，问变成上升排列的最优期望值。$T,q\le 10^5,n\le 16$。

思路

一般的操作流程是要么只用操作一，要么翻转一次后用操作一，所以这些操作只和排列的逆序对数有关系，所以可以把排列压缩成逆序对。

然后可以写出一个 dp（设 $dp(i)$ 表示将逆序对为 $i$ 的排列变成上升的最优期望），边界 $dp(0)=0$，其余的为 $dp(i)=min(dp(i-1)+a,dp(\frac{n(n-1)}{2}-i)+b,\sum_{j=0}^{\frac{n(n-1)}{2}}dp(j)P(j)+c)$，$P(j)$ 表示逆序对为 $j$ 的排列出现的概率。

似乎这个 dp 不能直接做，因为转移有环。但是我们可以做出以下观察：对于一些逆序对比较少的排列，只可能用操作一；对于一些逆序对比较多的，只会用操作二后用操作一；然后之间一段连续的部分，直接让它随机选，直到跳出中间的区间。

所以每次询问我们可以分两种情况： - 要么当前逆序对不再中间段，直接算； - 否则枚举这个左右边界，然后中间段的期望都是一样的，可以写出一个方程： $E_{mid}=P_{mid}E_{mid}+E_{left}+E_{right}+c$，解得 $E_{mid}=\frac{E_{left}+E_{right}+c}{1-P{mid}}$，然后对于所有的端点取 min 即可，单次询问 $O(n^4)$。

然后就是一些无聊的优化技巧，上面的式子可以改写成 $E_{mid}=\frac{E_{left}+E_{right}+c}{P_{left}+P_{right}}$。把 $(P_{left},E_{left})$ 和 $(P_{right},E_{right})$ 看做一个点，那么就是要求最小化 $\frac{Y+c}{X}$，可以看作是最小化 $(0,c)$ 到 $(X,Y)$ 的斜率，说明最优的点一定在下凸包上。所以我们可以先对 left,right 分别求出下凸包，然后再用Minkowski 和合并两个凸包（实现上就是按照斜率归并排序），这些都可以做到线性，所以单次查询复杂度为 $O(n^2)$。但是实际上 $O(n^4)$ 的常数很小，可以通过所有数据。

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define pll pair<long long,long long>
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long ll;
const int N=16;
const ll INF=(ll)1e14;
int t,n,m,q;
int p[N],cnt[N];
ll a,b,c;
ll f[N][N*N],val[N*N];
ll preX[N*N],preY[N*N],sufX[N*N],sufY[N*N];
void calc(){
    f[0][0]=1;
    for(int i=1;i<N;i++){
        for(int lst=0;lst<i*i;lst++){
            for(int j=0;j<=i;j++) f[i][lst+j]+=f[i-1][lst];
        }
    }
}
bool operator< (pll a,pll b){ //???С?? 
    if(a.se<0) a.fi=-a.fi,a.se=-a.se;
    if(b.se<0) b.fi=-b.fi,b.se=-b.se;
    if(b.se==0) return true;  
    return a.fi*1.0/a.se<b.fi*1.0/b.se; 
}
pll operator+ (pll a,pll b){
    return {a.fi*b.se+b.fi*a.se,a.se*b.se};
}
pll Min(pll a,pll b){
    return a<b?a:b;
}
pll mul(pll a,pll b){return {a.fi*b.fi,a.se*b.se};}
pll div(pll a,pll b){
    assert(b.fi!=0 && b.se!=0);
    return mul(a,{b.se,b.fi});
}
pll yue(pll a){
    if(a.se<0) a.fi=-a.fi,a.se=-a.se;
    ll d=__gcd(a.fi,a.se);
    a.fi/=d,a.se/=d;
    return a;
}
int top;
pll stk[N*N];
vector<pll>A,B;
double slope(pll a,pll b){
    if(a.fi==b.fi) return 1e9;
    return (a.se-b.se)*1.0/(a.fi-b.fi);
}
void solve(){
    ll sum=0,res=0;
    cin>>n>>a>>b>>c>>q;
    m=n*(n-1)/2;
    for(int i=0;i<=m;i++) val[i]=min(a*i,b+(m-i)*a),sum+=f[n-1][i];
    preX[0]=f[n-1][0],preY[0]=val[0]*f[n-1][0];
    for(int i=1;i<=m;i++) preX[i]=preX[i-1]+f[n-1][i],preY[i]=preY[i-1]+val[i]*f[n-1][i];
    sufX[m]=f[n-1][m],sufY[m]=val[m]*f[n-1][m];
    for(int i=m-1;i>=0;i--) sufX[i]=sufX[i+1]+f[n-1][i],sufY[i]=sufY[i+1]+val[i]*f[n-1][i]; 
    for(int Turn=1;Turn<=q;Turn++){
        for(int i=0;i<n;i++) cin>>p[i];
        int tot=0; 
        for(int i=0;i<n;i++){
            for(int j=p[i];j<n;j++) tot+=cnt[j];
            cnt[p[i]-1]++;
        } 
        pll ans={val[tot],1};
        stk[top=1]={0,0};
        for(int l=0;l<tot;l++){
            pll now={preX[l],preY[l]};
            while(top>=2 && slope(stk[top],now)<slope(stk[top-1],stk[top])) top--;
            stk[++top]=now;
        }
        A.resize(top);
        for(int i=1;i<=top;i++) A[i-1]=stk[i];
        stk[top=1]={0,0};
        for(int r=m;r>tot;r--){
            pll now={sufX[r],sufY[r]};
            while(top>=2 && slope(stk[top],now)<slope(stk[top-1],stk[top])) top--;
            stk[++top]=now;
        }
        B.resize(top);
        for(int i=1;i<=top;i++) B[i-1]=stk[i];
        int posA=0,posB=0;
        while(posA+1<A.size() || posB+1<B.size()){
            if(posA==A.size()-1) posB++;
            else if(posB==B.size()-1) posA++;
            else if(slope(A[posA],A[posA+1])<slope(B[posB],B[posB+1])) posA++;
            else posB++;
            ans=Min(ans,{c*sum+A[posA].se+B[posB].se,A[posA].fi+B[posB].fi});
        }
        A.clear(),B.clear();
        ans=yue(ans);
        cout<<ans.fi<<'/'<<ans.se<<'\n';
        for(int i=0;i<n;i++) cnt[i]=0;
    }
    for(int i=0;i<=m;i++) val[i]=0;
} 
int main(){
    freopen("perm.in","r",stdin);
    freopen("perm.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    calc();
    cin>>t;
    while(t--) solve();
    return 0;
}

总结

==本题考察了对期望的一些理解和数学能力，以及结论观察进而优化，难度大致在 NOIP T2 到 T3。==

后记

莫忘来时路，不负少年心。