fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define all(x) (x).begin(), (x).end()
  3. #define ll long long
  4. using namespace std;
  5.  
  6. const ll MOD = 998244353;
  7.  
  8. ll pw(ll a, ll e, ll m) {
  9.     ll r = 1 % m; a %= m;
  10.     while (e > 0) {
  11.         if (e & 1) r = r * a % m;
  12.         a = a * a % m;
  13.         e >>= 1;
  14.     }
  15.     return r;
  16. }
  17.  
  18. int main() {
  19.     ios_base::sync_with_stdio(false);
  20.     cin.tie(nullptr);
  21.  
  22.     int t;
  23.     cin >> t;
  24.     while (t--) {
  25.         int n;
  26.         cin >> n;
  27.         vector<ll> a(n), b(n);
  28.         for (int i = 0; i < n; ++i) cin >> a[i];
  29.         for (int i = 0; i < n; ++i) cin >> b[i];
  30.  
  31.         if (n == 1) {
  32.             cout << 0 << '\n';
  33.             continue;
  34.         }
  35.  
  36.         int N2 = n * n;
  37.         vector<pair<ll,ll>> pairs(N2);
  38.         int idx = 0;
  39.         for (int p = 0; p < n; ++p) {
  40.             for (int q = 0; q < n; ++q) {
  41.                 pairs[idx++] = {b[p], b[q]};
  42.             }
  43.         }
  44.  
  45.         sort(all(pairs), [](const pair<ll,ll>& x, const pair<ll,ll>& y){
  46.             return x.second * y.first < y.second * x.first;
  47.         });
  48.  
  49.         ll total = 0;
  50.  
  51.         for (int i = 0; i < n; ++i) {
  52.             for (int j = i + 1; j < n; ++j) {
  53.                 ll ai = a[i], aj = a[j];
  54.  
  55.                 int lo = 0, hi = N2;
  56.                 while (lo < hi) {
  57.                     int mid = (lo + hi) >> 1;
  58.                     if (pairs[mid].second * aj < pairs[mid].first * ai) lo = mid + 1;
  59.                     else hi = mid;
  60.                 }
  61.  
  62.                 ll cnt = lo;
  63.                 if (ai > aj) cnt -= n;
  64.  
  65.                 total = (total + cnt) % MOD;
  66.             }
  67.         }
  68.  
  69.         ll denom = (ll)n * (n - 1) % MOD;
  70.         ll ans = total % MOD * pw(denom, MOD - 2, MOD) % MOD;
  71.  
  72.         cout << ans << '\n';
  73.     }
  74.  
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
3
5
1 14 5 1 4
1 1 1 1 1
3
3 2 5
3 2 5
10
10 72 65 43 73 23 78 13 49 99
31 90 45 19 44 18 59 31 48 29
stdout
copy 
5
665496236
820778710
https://ideone.com/v1hECV
language:
C++ (gcc 8.3)
created:
12 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!