この解説では、\(0\) 以上 \(B^{L}\) 未満の整数 \(c\) に対して、 \(c\) を \(B\) 進 \(L\) 桁で表した際の \(B^{i}\) の位を \(N_{c}[i]\) と表します。

以下の補題を \(0\) 以上 \(L\) 未満の整数からなる組 \((x, y)\) について求めることを考えます。

補題

\(0\) 以上 \(B^{L}\) 未満の数の組 \((a, b)\) であって以下を全て満たすものを考えます。

• \(a < b\)
• \(N_{a}[i] \neq N_{b}[i]\) となるような \(i\) の最大値が \(x\)
• \(N_{a}[i] \neq N_{b}[i]\) となるような \(i\) のうち、\(P[i]\) が最大であるものが \(y\)

\(A[a] > A[b]\) であるような組の個数から \(A[a] < A[b]\) であるような組の個数を引いたものを求めてください。

\(x\neq y\) のとき

\(a, b\) の \(B^{y}\) 桁目を入れ替えたものを \(a', b'\) とします。形式的には、整数 \(a', b'\) を以下のように定めます。

• \(a' = a - B^{y}\cdot (N_{a}[y] - N_{b}[y])\)
• \(b' = b - B^{y}\cdot (N_{b}[y] - N_{a}[y])\)

このとき、 \((a, b)\) の組と \((a', b')\) の組は一対一対応します。また、 \(a ' < b'\) が成り立ちます。この \(2\) つの組 \((a, b), (a' , b')\) について、\(A[a] < A[b]\) と \(A[a'] < A[b']\) の \(2\) つのうち、ちょうど \(1\) つが成り立ちます。よって、補題の答えは \(0\) となります。

\(x = y\) のとき

\(i <x\) かつ \(P[i] < P[x]\) を満たす整数 \(i\) の個数を \(z\) とします。また、 \(V_{y}\) の転倒数を \(I\) とします。このとき、以下の \(2\) つが成り立ちます。

• 組 \((a, b)\) の個数は \(\dfrac{B^{L + z}(B - 1)}{2}\)
• \(A[a] > A[b]\) が成り立つ組 \((a, b)\)の個数は \(B^{L - 1 + z}I\)

よって、補題の答えは \(\dfrac{B^{L - 1 + z}(4I - B(B - 1))}{2}\) となります。

本題の答え

全ての \((x, y)\) に対する補題の総和を \(S\) としたとき、答えは以下のように求まります。

\(\dfrac{1}{2}\left(S + \dfrac{ B^{L}(B^{L} - 1)}{2}\right)\)

よって、 \(x = y\) を満たす全ての \((x, y)\) に対して、補題の答えを求めることができれば答えが求まります。

\(i <x\) かつ \(P[i] < P[x]\) を満たす整数 \(i\) の個数を \(0\) 以上 \(L\) 未満の全ての整数 \(x\) に対して求めるのにかかる時間計算量は \(O(L\log(L))\) です。

\(V_{0}, V_{1}, \dots V_{L - 1}\) の転倒数を全て求めるのにかかる時間計算量は \(O(BL\log(B))\) です。

これらが時間計算量のボトルネックであるため、全体の時間計算量は \(O(L(B\log(B) + \log(L))\) です。