โปรแกรมนับวิธีเลือก subsequence จาก Ajob Sequence ใน Python

มีภาษา Ajob ที่มีอักษรอันนานต์ คำที่ 1 ยาว 1 ตัวอักษร คำที่ 2 ยาว 2 ตัวอักษร ... ทุกคำมีตัวอักษรไม่ซ้ำกัน เลือกคำหนึ่งใน n คำแรก แล้วสร้าง subsequence ยาว L-k (L คือความยาวคำที่เลือก) หาจำนวนวิธี modulo p (p เป็นจำนวนเฉพาะ)

ตัวอย่าง: n=6, k=5, p=11 ผลลัพธ์คือ 7

ขั้นตอนการแก้ปัญหา

ใช้ทฤษฎี Lucas Theorem และคำนวณแฟกทอเรียล modulo p ล่วงหน้า:

1. สร้างตารางแฟกทอเรียล fact และ inv_fact modulo p
2. ใช้ Lucas Theorem คำนวณ C(n+1, k+1) mod p

ตัวอย่างโค้ด 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))  # ผลลัพธ์: 7

อินพุตตัวอย่าง

6, 5, 11

เอาต์พุตตัวอย่าง

7