Exponential Sorted Substrings

解説

${A_i}^{A_j} < {A_j}^{A_i}$ を満たすような $A_i,A_j$ の値の条件は、以下の条件のうちいづれかを満たすときです。(長いので証明は追記に載せます)

• $A_i=1$ かつ $A_i < A_j$
• $3 \leq A_j < A_i$
• $(A_i,A_j) = (2,3)$
• $A_i \neq 2,3,4$ かつ $A_j=2$

これらの条件を利用して、数列 $A$ の構築を考えます。(以降の説明において、条件より $A_i \neq A_j$ であることを断りなく用いています。)

1. $A$ が $3$ 以上の整数からのみなるとき

$3 \leq A_j < A_i$ より、$A$ は $3 \leq A_N$ となるような狭義単調減少数列です。このような $A$ の個数は、$3$ ~ $M$ の中から $N$ 個の整数を選ぶ組み合わせの総数に等しく $_{M-2}C_{N}$ となります。

2. $A$ が $2$ を含み $1$ を含まないとき

• $A_N = 2$ のとき、 $A_i \neq 2,3,4$ かつ $A_j=2$ , $3 \leq A_j < A_i$ より $A$ は $5 \leq A_{N-1}$ となる狭義単調減少数列となります。このような $A$ の個数は、$5$ ~ $M$ の中から $N-1$ 個の整数を選ぶ組み合わせの総数に等しく $_{M-4}C_{N-1}$ となります。
• $A_{N-1} = 2$ のとき、$(A_i,A_j) = (2,3)$ より $A_{N} = 3$ となります。残りの $N-2$ 個の要素は $3 \leq A_j < A_i$ と $A_i \neq 2,3,4$ かつ $A_j=2$ より $5 \leq A_{N-2}$ となる狭義単調減少数列となります。このような $A$ の個数は$5 \leq M$ においてのみ、$5$ ~ $M$ の中から $N-2$ 個の整数を選ぶ組み合わせの総数に等しく $_{M-4}C_{N-2}$ となります。$M<5$ のときは $0$ 個です。
• $A_{N-2}$ 以前の要素が $2$ になることはあり得ません。なぜなら、$A_i = 2$ のときに条件を満たせるような $A_j$ は $3$ しかなく、$A$ に同じ数字を複数回入れることはできないからです。

3. $A$ が $1$ を含み $2$ を含まないとき

• $A_1 = 1$ のとき、$A_i=1$ かつ $A_i < A_j$ より $A_2$ 以降の要素は必ず $3$ 以上となります。よって $3 \leq A_j < A_i$ から、残り $N-1$ 個の要素は $3 \leq A_{N}$ となる狭義単調減少数列となります。このような $A$ の個数は、$3 \leq M$ においてのみ、 $3$ ~ $M$ の中から $N-1$ 個の整数を選ぶ組み合わせの総数に等しく $_{M-2}C_{N-1}$ となります。$M < 3$ のときは $0$ 個です。
• $A_2$ 以降が $1$ となることはあり得ません。$A_j=1$ のときに条件を満たせるような整数 $A_i$ は存在しないからです。

4. $A$ が $1$ も $2$ も含むとき

2.や3.の考察により、

• $A_1 = 1$
• $A_{N} = 2$ または $A_{N-1},A_{N} = 2,3$

の両方が成り立たなければなりません。

• $A_N = 2$ のとき、 $A_i \neq 2,3,4$ かつ $A_j=2$ , $3 \leq A_j < A_i$ より $A$ は $5 \leq A_{N-1}$ となる狭義単調減少数列となります。このような $A$ の個数は、$5$ ~ $M$ の中から $N-2$ 個の整数を選ぶ組み合わせの総数に等しく $_{M-4}C_{N-2}$ となります。

• $A_{N-1},A_{N} = 2,3$ のとき、残りの $N-3$ 個の要素は $3 \leq A_j < A_i$ と $A_i \neq 2,3,4$ かつ $A_j=2$ より $5 \leq A_{N-3}$ となる狭義単調減少数列となります。このような $A$ の個数は、$5$ ~ $M$ の中から $N-3$ 個の整数を選ぶ組み合わせの総数に等しく $_{M-4}C_{N-3}$ となります。

以上の考察から、答えは $3 \leq N , 5 \leq M$ ...s において $_{M-2}C_{N} +( _{M-4}C_{N-1} + _{M-4}C_{N-2} )+ _{M-2}C_{N-1} + (_{M-4}C_{N-2} + _{M-4}C_{N-3})$ です。 $N,M$ の値がsを満たさない場合について考えます。

• $N=2$ の場合、$1$ ~ $M$ の中から $2$ つ選んで取り出し、適切に並び変えることで $\{2,4\}$ 以外の組み合わせにおいては条件を満たす数列を構築できます。答えは $M=2,3$ のとき $_MC_{2}$ 、$4 \leq M$ のとき $_MC_{2}-1$ です。
• $3 \leq N \leq M < 5$ の場合、$A$ として考えられる数列 $M^N$ 通りを全列挙し、そのそれぞれについて条件を満たすかどうか判定すればよいです。(条件を利用することでもっと候補を絞り込めるので、手計算で各 $(N,M)=(3,3),(3,4),(4,4)$ について答えを求めても良いです。)

計算量について考えます。

• $N,M$ がsを満たす場合については、 答えは階乗とその逆元の値を前計算しておくことで $O(1)$ で求めることができます。よって、全体として時間計算量は前計算がボトルネックとなり $O(\max(N,M))=O(M)$ であるため、実行時間制限に間に合います。

• $N,M$ がsを満たさない場合について、

  • $N=2$ の場合、$_MC_{2}$ は $O(1)$ で計算できるので、全体としても $O(1)$ で求めることができます。

  • $3 \leq N \leq M < 5$ の場合、 $A$ として考えられる数列 $M^N$ 通りを全列挙し、そのそれぞれについて条件を満たすかどうか $O(N^2)$ で判定すればよいです。全体の計算量は $O(M^NN^2)$ ですが、$N \leq M \leq 4$ より 余裕で実行時間制限に間に合います。手計算で各 $N,M$ について答えを求めてコードに埋め込めば $O(1)$ でいけます。

追記

• $a^b < b^a$ を満たすような $a,b$ の値の条件

とりあえず、与えられた不等式を変形してみます。$a,b$ の少なくともどちらか一方が $1$ のときや、$a = b$ のときの大小関係は明らか($a=1$ かつ $a \neq b$ のときのみ不等式成立)であるため、$a \neq b , 2 \leq a,b$ の場合を考えます。

$\displaystyle a^b < b^a \longleftrightarrow b\log a < a\log b \longleftrightarrow \frac{b}{\log b} < \frac{a}{\log a}$

ここで、 $\displaystyle f(x) = \frac{x}{\log x}$ とおくと $a^b < b^a \longleftrightarrow f(b) < f(a)$ が成り立てば良いと分かります。

また、 $f(x)$ のグラフを微分して描いてみると、$0 < x$ の部分においてグラフは下に凸の形をしており $x=e \fallingdotseq 2.71$ のとき極小値をとることが分かります。よって、$(e <) 3 \leq b < a$ のときは不等式が成り立ちます。

では、$a,b$ のどちらか一方が $2$ のときはどうなるのでしょうか。まず、$a=2$ のときを考えてみます。

$2^b < b^2 \longleftrightarrow 2^b-b^2 < 0$

ここで、$b>0$ において $2^b-b^2 = 0$ の解は $b=2,4$ であり、$2^b-b^2 < 0$ を満たす正整数 $b$ は $b=3$ のみであるため、$(a,b) = (2,3)$ のときのみ不等式が成り立ちます。

$b=2$ のときは、$a^2 < 2^a \longleftrightarrow 2^a-a^2 > 0$ より、$a=2$ のときと同様にして考えると $a$ が $2,3,4$ 以外の正整数であれば不等式が成り立ちます。

これまでの考察をまとめます。 不等式が成り立つのは、$(a,b)$ が以下の条件のうちいづれかを満たすときです。

• $a=1$ かつ $a < b$
• $3 \leq b < a$
• $(a,b) = (2,3)$
• $a \neq 2,3,4$ かつ $b=2$

実装例