[AtCoder] 第一回日本最強プログラマー学生選手権-予選- B – Kleene Inversion

2019年8月25日2019年12月4日

問題

方針

転倒数

転倒数を求めるアルゴリズムはマージソートを利用したものや BIT を使ったものがありますが、今回はデータ数が小さいので、\( O(N^2)\) の計算量が間に合います。\( A \) の転倒数を \( s_1 \) とします。

全体の配列の転倒数

ここで、\( C_i = A = (A_0, A_1, \cdots, A_{N-1})\) として、\( B = (C_1, C_2, \cdots, C_K) \) と表現します。任意の二組の配列の転倒数 \( s_2 \) を次のように定義します。\( s_2 \) は、\( A_i > A_j \ ( 0 \leq i < N \wedge 0 \leq j < N) \) を満たす \( i, j \) の組み合わせとします。任意の二組の組み合わせは、\( {}_{N} \mathrm{ C }_{2} \) 通りあるので、全体の転倒数は、

\[s_1K + s_2{}_{N} \mathrm{ C }_{2} \]

となります。

コード

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

int main() {
  int N;
  ll K;
  cin >> N >> K;
  int A[N];
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  
  ll d = pow(10, 9) + 7;
  ll ans = 0;
  ll sum1 = 0;
  ll sum2 = 0;
  
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      if (A[i] > A[j]) sum1++;
    }
  }

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (A[i] < A[j]) sum2++;
    }
  }
  
  ans += K * sum1 % d;
  ans += (K * (K - 1) / 2) % d * (sum2);
  ans %= d;
  cout << ans << "\n";
  return 0;
}