B - Kleene Inversion

この問題を最近見つけたのでやってみましたが、どうやって解いたらいいかわからなかったので複数の解説されているサイトを見てACになるコードを提出しました。
ただ、個人的にはなんか悔しいので自分なりにまとめてみようと思った次第です。

1. 解説

結論から述べると、Bの転倒数を求めるには、

(Aの転倒数) * K + (全探索したときのA[i] > A[j]の個数) * K * (K-1) / 2

を1000000007で割りその余りを計算する必要があります。

1. (Aの転倒数) * Kを求める

まず、+よりも前の部分を計算していくことにします。Aの転倒数を求める方法は、iの範囲は(0<=i<N)、jの範囲は(i+1<=j<N)で全探索し、その中で

A[i] > A[j]

となるケースを数えていくことです。
その後にK倍して、1000000007で割り余りを求めます。
実装例は以下の通りです。

solution1

long long s = 0;
for(int i=0; i<N; i++) {
    for(int j=i+1; j<N; j++) {
        if(A[i] > A[j]) {
            s++;
        }
    }
}
s *= K;
s %= 1000000007;

K倍する理由

さて、最後になぜK倍するのかという疑問がわくと思います。これについて解説していきます。まず数列BというのはAがK個繰り返してできたものです。ならば以上のような実装をK回して求めることができるだろうと考えると思います。ただ、Kが大きいと配列が大きくなりすぎるのと、K回求めることは非効率的だと考えられます。そこで簡単に求める方法がないかを考えます。するとK回同じようなことが起きるなら、先程求めた値をK倍してあげればいいという考えに至るでしょう。

2. (全探索したときのA[i] > A[j]の個数) * K * (K-1) / 2を求める

これは具体的に考えていきましょう。
数列を以下のように設定します(これを数列1と呼ぶことにします)

8, 3, 2, 5

それをもう一つ用意して(これを数列2と呼ぶことにします)

8, 3, 2, 5, 8, 3, 2, 5

とします。
数列が2回繰り返された場合はどうでしょう。転倒数をそのまま愚直に求めるのも一つの手段ですが、Kが大きいと求めにくくなります。なので別の方法で求めていくことにします。前半の数列と後半の数列おのおのについての転倒数は先程解説した方法で求められます。前半の数列の各項と後半の数列の項はどうなるでしょうか。数列2で実際に確かめると、

(8,3), (8,2), (8,5), (3,2), (5,3), (5,2)

になるでしょう。
これはつまり数列1を、iの範囲(0<=i<N)、jの範囲(0<=j<N)で全探索して、

A[i] > A[j]

となるケースを求めることと同じだとお気づきでしょうか。
これを最初では少し簡素に(全探索したときのA[i] > A[j]の個数)と表現しました。
ということであとはK個あるうちの2個を取り出す組み合わせを求めてあげればいいので、(全探索したときのA[i] > A[j]の個数)にK*(K-1)/2をかけます。最後に1000000007で割り余りを求めます。
実装例は以下の通りです。

solution1

long long t = 0;
for(int i=0; i<N; i++) {
    for(int j=0; j<N; j++) {
        if(A[i] > A[j]) {
            t++;
        }
    }
}
t *= K * (K-1) / 2;
t %= 1000000007;

2. 提出したコード

1.で解説したコードを組み合わせて必要な部分を書き加えることで以下のようなコードができます。

sample_code

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

int main() {
    
    ll N,K;
    cin >> N >> K;
    vector<ll> A(N);
    for(int i=0; i<N; i++) {
        cin >> A[i];
    }
    ll s = 0;
    ll t = 0;
    ll ans = 0;
    for(int i=0; i<N; i++) {
        for(int j=i+1; j<N; j++) {
            if(A[i] > A[j]) {
                s++;
            }
        }
    }
    s *= K;
    s %= 1000000007;
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            if(A[i] > A[j]) {
                t++;
            }
        }
    }
    t *= K * (K-1) / 2 % 1000000007;
    ans = s + t;
    ans %= 1000000007;
    cout << ans << endl;
    return 0;

}

3. 参考文献・調べたサイト

参考にさせていただきました。これらのおかげでACとなるコードを書くことができました。ありがとうございます。

まとめ及び感想

最後になぜこのような記事を書こうかと思ったかというと冒頭でも述べたとおり、ACとなるコードは書けたものの自分で説明出来なきゃ意味がないし、なんとなく悔しさを感じていた部分もありました。この記事を書くことでストレス発散になりました。
この記事の中の説明が拙い部分もあるかと思いますが、これから説明する力を養っていければ良いかなと思っています。

余談

来週テストがあるのですが、その勉強の休憩として書いてました。1つわからない問題をずっと考えているのですがこれを書いている時もまだ解決していません。ただいろんな方法を調べて解きたいと思ってます。

以上で
最後まで読んで頂きありがとうございました。
日本語がおかしいとかこの説明こうした方がいいというのがありましたらコメントでお待ちしております。