Pythonで階段の登り方の総数を求めるプログラム ― 上位K桁と下位K桁を効率的に計算する方法

問題の概要

N段の階段を考えます。一段ずつ上がることもできれば、各段で最大N段までジャンプすることもできます。このとき、最上階までたどり着く方法が全部で何通りあるのかを求めるのが目的です。

ただし、Nは非常に大きな値になる可能性があります。そこで、答え全体ではなく「上位K桁」と「下位K桁」だけを求めればよいことになっています。

例を見てみましょう。入力が N = 10、k = 2 のとき、出力は 63 になります。10段の階段に対して、頂上への登り方がS通りあるとし、そのSを wxyz という4桁の数と考えると、wx(上位2桁)と yz(下位2桁)の合計が 63 になるのです。

背後にある数学

実は、この問題の答えは 2^(N−1) 通りになります。理由はこうです。N個の段の間には N−1 個の「境目」があり、それぞれの境目で「同じジャンプで越えるか、そこで新たに一歩踏み出すか」の2択を選べます。すべての組み合わせを数えると 2×2×…×2(N−1 回)= 2^(N−1) 通りとなります。

N = 10 の場合、2⁹ = 512 となり、上位2桁「51」と下位2桁「12」を足すと 51 + 12 = 63 となり、確かに期待どおりの結果です。

しかし N が巨大になると、2^(N−1) を正確に計算するのは現実的ではありません。そこで次のような工夫を行います。

• 下位K桁:冪乗の計算を 10^K で割った余り(モジュロ演算)で求めます。
• 上位K桁:繰り返し二乗法(バイナリ法)で冪乗を計算しながら、各ステップで先頭の c 桁だけを切り出して保持します。これにより、巨大な数を直接扱わずに済みます。

アルゴリズムの手順

この問題を解くために、以下の手順に従います。

• N := N − 1 とする(求めたいのは 2^(N−1) のため)
• c := 2 × ceil(k + log₁₀N)(精度を保つために保持する桁数)
• e := N、b := 2、s := 1 で初期化
• e > 0 の間、以下を繰り返す
  • e が奇数なら、s := (s × b) の先頭 c 桁(p を s×b の桁数とする)
  • e := ⌊e / 2⌋
  • b := (b × b) の先頭 c 桁(p を b×b の桁数とする)
• s := s の先頭 k 桁(p を s の桁数とする)
• r := s + (2^N mod 10^k)
• r を返す

Pythonでの実装例

それでは、実際の実装を見て理解を深めましょう。

from math import log10, ceil

def solve(N, k):
    N -= 1
    c = 2 * ceil(k + log10(N))
    e = N
    b = 2
    s = 1
    while e > 0:
        if e % 2 == 1:
            s = int(str(s * b)[:c])
        e //= 2
        b = int(str(b * b)[:c])
    s = str(s)[:k]
    r = int(s) + pow(2, N, 10**k)
    return r

N = 10
k = 2
print(solve(N, k))

入力

10, 2

出力

63

まとめ

このプログラムでは、繰り返し二乗法とモジュロ演算を組み合わせることで、Nが非常に大きい場合でも、階段の登り方の総数の上位K桁と下位K桁を効率的に求めることができます。計算量は O(log N) 程度に抑えられ、巨大な指数を持つ冪乗の問題に対する実用的なアプローチといえます。