สมมุติว่ามีภาษาแปลกๆ เรียกว่า ภาษาอาจ๊อบ มีจำนวนตัวอักษรไม่สิ้นสุด เรารู้ n คำในภาษานี้ คำแรกมีความยาวอักขระหนึ่งตัว คำที่สองยาวสองอักขระ เป็นต้น และตัวอักษรทั้งหมดในคำก็มีเอกลักษณ์เฉพาะตัว หากเราเลือกคำใดคำหนึ่งจาก n คำและสร้างลำดับจากคำนั้น ความยาวของลำดับรองควรน้อยกว่าความยาวของคำต้นฉบับ k ตัวอย่างเช่น หากความยาวของคำที่เลือกคือ L ความยาวของคำที่ตามมาควรเป็น (L - k) หากคำใดมีความยาวน้อยกว่า k คุณต้องไม่เลือกคำนั้น และสองส่วนย่อยจะแตกต่างกันเมื่อความยาวของมันต่างกันหรือมีอักขระต่างกันในตำแหน่งเดียวกัน เราต้องหาผลลัพธ์ modulo p และ p i a ไพรม์
ดังนั้น หากอินพุตเป็น n =6, k =5, p =11 เอาต์พุตจะเป็น 7
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างบันทึกพจนานุกรมเปล่าหนึ่งรายการ
- n :=n + 1, k :=k + 1
- ข้อเท็จจริง :=รายการที่มีองค์ประกอบ 1 อย่าง
- สำหรับ i ในช่วง 1 ถึง p - 1 ทำ
- แทรก (องค์ประกอบสุดท้ายของข้อเท็จจริง * i mod p) ที่ส่วนท้ายของข้อเท็จจริง
- ถ้า p มีอยู่ในบันทึกช่วยจำ
- inv_fact :=บันทึก[p]
- มิฉะนั้น
- inv :=รายการที่มีสององค์ประกอบ 0 และ 1
- สำหรับฉันในช่วง 2 ถึง p - 1 ทำ
- แทรก (p - ชั้นของ p/i * inv[p mod i] mod p) ที่ส่วนท้ายของ inv
- inv_fact :=รายการที่มีองค์ประกอบ 1 อย่าง
- สำหรับ i ในช่วง 1 ถึง p - 1 ทำ
- แทรก (องค์ประกอบสุดท้ายของ inv_fact * inv[i] mod p) ที่ส่วนท้ายของ inv_fact
- บันทึก[p] :=inv_fact
- ret :=1
- ในขณะที่ n> 0, ทำ
- n1 :=n mod p
- k1 :=k mod p
- ถ้า k1> n1 แล้ว
- คืน 0
- ret :=ret * fact[n1] * inv_fact[k1] * inv_fact[n1 - k1] mod p
- n :=ชั้นของ (n/p)
- k :=ชั้นของ k/p
- คืนสินค้า
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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)) อินพุต
6, 5, 11
ผลลัพธ์
7
