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)$ 即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#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();
	}
}