题解：CF2223B Zhily and Barknights

· · 题解

CF2223B Zhily and Barknights

思路

题目的意思是：把 b 数组随机打乱，然后和 a 对应位置相乘得到新数组 c，问 c 里逆序对数量的期望值。
期望可以拆成每一对位置 i,j(i<j) 的逆序概率之和。
对于固定的 i 和 j，我们关心的是 a_i\times b_i>a_j\times b_j 的概率，其中 b_i 和 b_j 是从 b 里随机抽的两个不同数。
把 b 里的数两两配对（有序），总共有 n\times (n-1) 种可能。
条件 a_i\times u>a_j\times v 等价于 u\div v > a_j\div a_i。
所以问题变成：给定一堆 u,v 对，以及一堆比值 a_j\div a_i，统计有多少组满足 u\div v 大于这个比值。
可以先把所有 u\div v 排好序，然后对于每个比值二分查找，一次性累加结果。
最后除以总方案数 n\times(n-1) 即可。

代码

#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define pii pair<int,int>
#define fep(i,s,e) for(int i=s;i<e;i++)
#define pef(i,s,e) for(int i=s;i>e;i--)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define per(i,s,e) for(int i=s;i>=e;i--)
namespace FastIO{
    template<typename T>inline void read(T &x){
        x=0;int f=1;char c=getchar();
        for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
        for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
    }
    template<typename T,typename...Args>
    inline void read(T &x,Args&...args){
        read(x);
        read(args...);
    }
    template<typename T>void print(T x){
        if(x<0)x=-x,putchar('-');
        if(x>9)print(x/10);
        putchar((x%10)^48);
    }
}
using namespace std;
using namespace FastIO;
const int N=2047;
const int mod=998244353;
int T,n;
int calc(int n,int x){
    if(x==0)return 1;
    if(x==1)return n;
    int hf=x/2,el=x%2;
    int hfv=calc(n,hf);
    int elv=calc(n,el);
    return hfv*hfv%mod*elv%mod;
}
bool cmp(pii a,pii $b$){
    return a.fir*$b$.sec>$b$.fir*a.sec;
}
void solve(){
    read(n);
    vector<int>a(n),$b$(n);
    fep(i,0,n)read(a_i);
    fep(i,0,n)read(b_i);
    sort($b$.begin(),$b$.end());
    int tot=n*(n-1)%mod;
    int inv=calc(tot,mod-2);
    vector<pii>f;
    vector<int>I,J;
    fep(i,0,n){
        fep(j,i+1,n){
            f.push_back({a_i,a_j});
            I.push_back(i);
            J.push_back(j);
        }
    }
    sort(f.begin(),f.end(),cmp);
    int m=f.size();
    vector<int>V(m);
    fep(i,0,m){
        V[i]=f[i].first*1e9/f[i].second;
    }
    int num=0;
    fep(i,0,n){
        fep(j,0,n){
            if(i==j)continue;
            int tar1=$b$[j];
            int tar2=b_i;
            int l=0,r=m;
            while(l<r){
                int mid=(l+r)/2;
                if(f[mid].fir*tar2>f[mid].sec*tar1)l=mid+1;
                else r=mid;
            }
            num=(num+l)%mod;
        }
    }
    int ans=num*inv%mod;
    print(ans);
    puts("");
}
signed main(){
    read(T);
    while(T--){
        solve();
    }
}