AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。
出典：
第一回日本最強プログラマー学生選手権-予選- B – Kleene Inversion
転倒数なる言葉が出てくるが、ソートされていない数字の個数……くらいに考えると分かりやすいかもしれない。転倒＝ソート順に逆らっている、というわけだ。
実際、バブルソートを実装した時、その操作回数は転倒数と等しくなる。
# 第一回日本最強プログラマー学生選手権-予選- B - Kleene Inversion
# https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_b
# tag: 数列 転倒数 考察 MOD 数え上げ
# A の中の数 Ai を考える。
# 転倒数を求める、すなわち、各 Ai より大きな数が左側にいくつあるか ＆
# 小さな数が右側にいくつあるかの合計を求めよ、という問題である。
# K < 10^9 という制限から、真面目に一つ一つを計算しては間に合わないので、
# どうにかまとめて計算をしてやる必要がある。
# 仮に自分の左側にある大きな数だけを考えるとする。
# まず、今自分が含まれている A における、自分より左側の大きな数を数える。
# 加えて、自分より左側の A にある、自分より大きな数を全て数えることになる。
# 1 番目の A に含まれる Ai から K 番目の Ai までを順番に考えていく
# とすると、結果的に 0 ~ K-1 の合計、(K-1) * K // 2 個の A を
# 見ていくことになる。
# 右側を見ていく場合も全く同様。
from collections import Counter
def main():
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7
# A の中での転倒数を求める。
# O(N logN) で求める方法もあるが、ここでは愚直に求めている。
inv_a = 0
for i in range(N-1):
for j in range(i+1, N):
if A[i] > A[j]:
inv_a += 1
# それぞれの A の内側での転倒数を加える
result = (inv_a * K) % MOD
# それぞれの数が何回現れているのかをカウントしておく
cnt = Counter(A)
# A に含まれる Ai より大きな数や小さな数、つまり Ai と異なる数は
# 全て (K-1) * K // 2 回数えられることになるので、まとめて
# しまってもよい。ただし、小→大と大→小の2回数えられているので注意。
# ある数が n 回現れるとして、(N - n) を n 回数えることになる
rest = 0
for n in cnt.values():
rest += (N - n) * n
mult = (K - 1) * K // 2
result = (result + rest * mult // 2) % MOD
print(result)
main()
関連
