# B - Kleene Inversion

# 概要

  • 長さNNの整数列AAKK回繰り返した整数列をBBとする
  • BBの転倒数を109+710^9 + 7で割ったあまりを求めよ

# 思考

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

ここで30分終了

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

# 解法

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

# 提出

  • https://atcoder.jp/contests/jsc2019-qual/submissions/7331697
Last Updated: 2019-9-3 23:11:34