Pythonの階段を使用して次の階に到達できる方法の数を見つけるためのプログラム

N段の階段があるとします。ステップバイステップで進むことも、各ステップで最大Nステップのジャンプを行うこともできます。最上階に行く方法をいくつも見つけなければなりません。 N値は大きい可能性があり、多数のウェイの最初と最後のK桁にのみ関心があります。

したがって、入力がN =10 k =2の場合、10のステップがあるため、出力は63になります。トップに移動できる方法がS個ある場合、Sはwxyzの形式であると見なします。したがって、wx+yzの合計は63です。

これを解決するには、次の手順に従います-

• N：=N-1
• c：=2 *（k + log（N）; base10）の上限
• e：=N、b：=2、s：=1
• e> 0の場合、do
  • eが奇数の場合、
    • s：=（s * b）の最初のp-c桁数ここで、pはs*bの桁数です
  • e：=e/2のフロア
  • b：=（b * b）の最初のp-c桁数ここで、pはb*bの桁数です
• s：=最初のp-sのk桁の数字。ここで、pはsの桁数です
• r：=s +（2 ^ N）mod 10 ^ k
• return r

例

理解を深めるために、次の実装を見てみましょう-

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