はまやんはまやんはまやん

hamayanhamayan's blog

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

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_b

前提知識

  • 転倒数の計算

解説

https://atcoder.jp/contests/jsc2019-qual/submissions/7121477

Kの値が109なので、繰り返しの分をどのように効率的に計算するかが問題となる。
まず、2回Aを繰り返した場合を考える。
この場合の答えは、(1つ目のA内部での転倒数) + (2つ目のA内部での転倒数) + (1つ目のA内部と2つ目のA内部での転倒数)となる。
ここで、前半2つは同じになる。
よって、tot1 = A内部での転倒数、tot2 = ある2つのA間での転倒数とすると、
答えは、2 * tot1 + tot2となる。
3回Aを繰り返した場合は、以下の総和となる。

  • 1つ目のA内部での転倒数
  • 2つ目のA内部での転倒数
  • 3つ目のA内部での転倒数
  • 1つ目のA内部と2つ目のA内部での転倒数
  • 1つ目のA内部と3つ目のA内部での転倒数
  • 2つ目のA内部と3つ目のA内部での転倒数

前半と後半はそれぞれ等しくなるので、 3 * tot1 + 3 * tot2が答えになる。
よって、K回繰り返した場合は、K * tot1 + C(K, 2) * tot2が答えになる。
なので、後はtot1, tot2が計算できればいい。

tot1については通常の転倒数計算をすればいい。
BITを使えばそれが実現できる。
tot2については、全ての要素について、それより大きいの要素が何個あるかをとってくればいい。

int N, K, A[2010];
BIT<int> bit(2010);
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];

    mint tot1 = 0;
    rep(i, 0, N) {
        tot1 += bit.get(A[i] + 1, 2010);
        bit.add(A[i], 1);
    }

    mint tot2 = 0;
    rep(i, 0, N) tot2 += bit.get(A[i] + 1, 2010);

    mint ans = tot1 * K + mint(K) * mint(K - 1) / 2 * tot2;
    cout << ans << endl;
}