Chương trình tìm số cách chúng ta có thể chọn trình tự từ Trình tự Ajob trong Python

Giả sử có một ngôn ngữ lạ gọi là ngôn ngữ Ajob. Nó có vô số chữ cái. Chúng tôi biết n từ trong ngôn ngữ này. Từ đầu tiên dài một ký tự, từ thứ hai dài hai ký tự, v.v. Và tất cả các chữ cái trong một từ là duy nhất. Nếu chúng ta chọn bất kỳ một trong n từ nào và tạo thành một dãy con từ nó. Độ dài của dãy con phải nhỏ hơn k độ dài của từ gốc. Ví dụ, nếu độ dài của từ được chọn là L, thì độ dài của dãy con phải là (L - k). Nếu từ nào có độ dài nhỏ hơn k thì bạn không được chọn từ đó. Và hai dãy con khác nhau khi độ dài của chúng khác nhau hoặc chúng chứa các ký tự khác nhau ở cùng một vị trí. Chúng ta phải tìm kết quả modulo p và p i là một số nguyên tố.

Vì vậy, nếu đầu vào là n =6, k =5, p =11, thì đầu ra sẽ là 7.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• tạo một bản ghi nhớ từ điển trống
• n:=n + 1, k:=k + 1
• fact:=danh sách có một phần tử 1
• đối với tôi trong phạm vi từ 1 đến p - 1, thực hiện
  • chèn (phần tử cuối cùng của thực tế * i mod p) vào cuối dữ liệu
• nếu p có trong bản ghi nhớ, thì
  • inv_fact:=memo [p]
• nếu không,
  • inv:=một danh sách có hai phần tử 0 và 1
  • đối với tôi trong phạm vi từ 2 đến p - 1, thực hiện
    • insert (p - tầng của p / i * inv [p mod i] mod p) vào cuối inv
  • inv_fact:=danh sách có một phần tử 1
  • đối với tôi trong phạm vi từ 1 đến p - 1, thực hiện
    • chèn (phần tử cuối cùng của inv_fact * inv [i] mod p) vào cuối inv_fact
  • memo [p]:=inv_fact
• ret:=1
• while n> 0, do
  • n1:=n mod p
  • k1:=k mod p
  • nếu k1> n1, thì
    • trả về 0
  • ret:=ret * fact [n1] * inv_fact [k1] * inv_fact [n1 - k1] mod p
  • n:=tầng của (n / p)
  • k:=tầng của k / p
• trả lời lại

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

6, 5, 11

Đầu ra

7