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일 때 수행
- e가 홀수이면
  - s :=(s*b)의 첫 번째 p-c 자릿수 여기서 p는 s*b의 자릿수입니다.
- :=e/2의 바닥
- b :=(b*b)의 첫 번째 p-c 자릿수 여기서 p는 b*b의 자릿수입니다.
s :=s의 첫 번째 p - k 자리 수, 여기서 p는 s의 자릿수
r :=s + (2^N) 모드 10^k
반환 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