# B - Kleene Inversion (opens new window)

# 概要

長さ $N$ の整数列 $A$ を $K$ 回繰り返した整数列を $B$ とする
$B$ の転倒数を $10^9 + 7$ で割ったあまりを求めよ

# 思考

手元で実験すると, $A$ の要素ごとの転倒数を $C_i$ とすると, $\sum_{i=0}^{n-1} {C_i * k * (k+1) / 2}$ で求められそう?
実装する
テストケース3で詰まる
MODの取り方がよくない?
直しても通らない

ここで30分終了

editorialを見る
$A$ $A$ の内部のみで完結している転倒数と, $A$ $A$ の内部および $A$ $A$ の外部とでできる転倒数の2つに分けて考えると良いとのこと
- 元々の実装だと, Aが単調増加の時のテストケースに対応していなかった

# 解法

$A$ $A$ の内部のみで完結している転倒数は, $O(N^2)$ $O (N^{2})$ で求められる
- $A_i, A_j(i < j)$ を比較して, $A_i > A_j$ となっている数をカウント
- $A$ の内部のみで完結している転倒数は $K$ 個あるので, $K$ 倍する
$A$ $A$ の内部および $A$ $A$ の外部とでできる転倒数も, $O(N^2)$ $O (N^{2})$ で求められる
- $A_i, A_j(i < j)$ を比較して, $A_i > A_j$ となっている数をカウント
- $A$ の内部および $A$ の外部とでできる転倒数は, $A_i$ と $A_j$ を選ぶので, $K\times(K-1)/2$ 倍する
これらの和を取れば良い

# 提出

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