题解归档 - cf2224D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2224D
• 本地来源：problems/cf2224D/idea.md
• 题目链接：https://codeforces.com/contest/2224/problem/D
• 原始标题：cf2224D - Zhily and Barknights

思路

cf2224D - Zhily and Barknights

Pattern

Use linearity of expectation over index pairs (i,j).

For fixed i<j, the two modules assigned to these positions are two distinct
indices u != v from array b, uniformly among all n(n-1) ordered pairs.

We need:

a[i] * b[u] > a[j] * b[v]

which is equivalent to:

b[v] / b[u] < a[i] / a[j].

Algorithm

Precompute all n(n-1) fractions b[v] / b[u] for u != v, sort them by
cross multiplication.

For every i<j, binary search how many precomputed fractions are smaller than
a[i] / a[j]. This count is the numerator contribution for that pair.

The expected value is:

sum_counts / (n(n-1)) mod 998244353.

Strictness

The inversion condition is strict >, so the fraction comparison is strict
<; using lower_bound gives exactly the number of fractions strictly smaller
than the query fraction.

Complexity

O(n^2 log n) memory/sort scale per test case, with n<=2000 and total
n<=2000.

Checks

• python tools/run_exe.py cf2224D - sample OK.
• python tools/stress2.py cf2224D -n 500 --keep-fail - OK against direct
  counting on small random cases.

代码

来源：problems/cf2224D/solution.cpp

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const ll MOD=998244353;

struct Frac{
    ll num,den;
};

bool fracLess(const Frac&a,const Frac&b){
    return (__int128)a.num*b.den<(__int128)b.num*a.den;
}

ll modPow(ll a,ll e){
    ll r=1;
    while(e){
        if(e&1) r=r*a%MOD;
        a=a*a%MOD;
        e>>=1;
    }
    return r;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        vector<ll>a(n),b(n);
        for(ll &x:a) cin>>x;
        for(ll &x:b) cin>>x;
        if(n==1){
            cout<<0<<"\n";
            continue;
        }
        vector<Frac> ratios;
        ratios.reserve(1LL*n*(n-1));
        for(int u=0;u<n;u++){
            for(int v=0;v<n;v++){
                if(u==v) continue;
                ratios.push_back({b[v],b[u]});
            }
        }
        sort(ratios.begin(),ratios.end(),fracLess);
        ll ans=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                Frac q{a[i],a[j]};
                ll cnt=lower_bound(ratios.begin(),ratios.end(),q,fracLess)-ratios.begin();
                ans+=cnt%MOD;
                if(ans>=MOD) ans-=MOD;
            }
        }
        ll den=1LL*n*(n-1)%MOD;
        ans=ans*modPow(den,MOD-2)%MOD;
        cout<<ans<<"\n";
    }
    return 0;
}