Số cách chọn dãy con từ dãy Ajob trong Python

Ngôn ngữ Ajob có vô hạn ký tự. Biết n từ, từ thứ i dài i ký tự, tất cả ký tự trong một từ đều khác nhau. Chọn một từ, lấy dãy con độ dài L - k (L là độ dài từ chọn). Từ có độ dài < k không được chọn. Hai dãy con khác nhau nếu độ dài khác nhau hoặc ký tự tại cùng vị trí khác nhau. Tính kết quả modulo p (p là số nguyên tố).

Ví dụ: n=6, k=5, p=11 → kết quả 7.

Giải thuật

• Sử dụng định lý Lucas để tính tổ hợp modulo số nguyên tố p.
• Tính giai thừa và nghịch đảo giai thừa modulo p.
• Áp dụng định lý Lucas cho n+1 và k+1.

Ví dụ mã Python

memo = {}

def solve(n, k, p):
    n += 1
    k += 1
    fact = [1]
    for i in range(1, p):
        fact.append(fact[-1] * i % p)
    if p in memo:
        inv_fact = memo[p]
    else:
        inv = [0, 1]
        for i in range(2, p):
            inv.append(p - p // i * inv[p % i] % p)
        inv_fact = [1]
        for i in range(1, p):
            inv_fact.append(inv_fact[-1] * inv[i] % p)
        memo[p] = inv_fact
    ret = 1
    while n > 0:
        n1 = n % p
        k1 = k % p
        if k1 > n1:
            return 0
        ret = ret * fact[n1] * inv_fact[k1] * inv_fact[n1 - k1] % p
        n //= p
        k //= p
    return ret

n = 6
k = 5
p = 11
print(solve(n, k, p))  # Output: 7

Đầu vào

6, 5, 11

Đầu ra

7