No.271

階乗進数を考える. これは $i$ 桁目の重みが $i!$ であるような表現法である.

置換 $[1,2,3,4,5]$ を階乗進数で $0000$ として置換を辞書順に並べると以下のようになる.

$$\begin{array}{cc} [1,2,3,4,5] & 0000 \\ [1,2,3,5,4] & 0001 \\ [1,2,4,3,5] & 0010 \\ [1,2,4,5,3] & 0011 \\ [1,2,5,3,4] & 0020 \\ [1,2,5,4,3] & 0021 \\ [1,3,2,4,5] & 0100 \\ [1,3,2,5,4] & 0101 \\ \vdots & \vdots \\ [1,5,4,3,2] & 0321 \\ [2,1,3,4,5] & 1000 \\ \end{array}$$

上から $i$ 桁目の数字は, 置換において左から $i$ 番目より右側にある $i$ 番目の数字より小さい数字の個数となる. よって, 階乗進数の各桁の和は置換の転倒数と等しい.

置換から階乗進数を求めるのも上記の性質から Binary Indexed Tree を用いて左の桁から計算していけばいい.

$A_K$ の階乗進数は $A_0$ の階乗進数に単純に $K$ を足したものとなる. 階乗進数の右から $i$ 桁目は $i+1$ で繰り上がるので足し算の実装は容易である.

ここで, $B(p)$ を $p$ を階乗進数で表したときの数値未満の転倒数の和とする. そうすると, 答えは

$$B(A_K) - B(A_0) + LB(q+1)$$

となる. $L$ は辞書順で最後の置換から最初の置換に戻った回数 (これは $A_K$ の計算時に求められる), $q$ は辞書順で最後の置換である.

$B(p)$ は桁 DP の要領で求めればいい.

$k$ 桁目まで見たときの最大値でない数の転倒数の和を $C(k)$, 最大値の転倒数の和を $D(k)$, 最大値でない数の組み合わせの数を $E(k)$ とすると,

$$\begin{align} C(k) &= C(k-1)(g_k+1) + E(k-1)\frac{g_k(g_k+1)}{2} + D(k-1)h_k + \frac{h_k(h_k-1)}{2} \\ D(k) &= D(k-1) + h_k \\ E(k) &= E(k-1)(g_k+1) + h_k \end{align}$$

となる. ただし, $g_k$ は $k$ 桁目にとりうる最大の数, $h_k$ は $p$ を階乗進数に変換したときの $k$ 桁目の数である.