Chương trình đếm cách leo cầu thang đến tầng trên trong Python

Cầu thang N bậc. Mỗi bước có thể lên 1 bậc hoặc nhảy tối đa N bậc. Tìm số cách leo lên, chỉ lấy K chữ số đầu và cuối.

Thuật toán

• Số cách = 2^{N-1} (mỗi bậc có/không có "nghỉ").
• Tính 2^{N-1} modulo 10^K cho K chữ số cuối.
• Tính K chữ số đầu bằng lũy thừa nhị phân giữ chữ số đầu (dùng log10).
• Cộng 2 phần.

Ví dụ

from math import log10, ceil

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

print(solve(10, 2))  # Output: 63

Giải thích

N=10 → 2^9=512. K=2: 2 chữ số đầu=51, 2 chữ số cuối=12 → 51+12=63.