在Python中查找从Ajob序列选择序列的方法数量

假设有一种叫做Ajob语言的奇怪语言。它有无限数量的字母。我们知道该语言中的n个单词。第一个单词是一个字符长，第二个单词是两个字符长，依此类推。每个单词中的所有字母都是唯一的。如果我们从其中选择任何一个单词并形成一个子序列。子序列的长度应该比原始单词的长度小k。例如，如果所选单词的长度为L，则子序列的长度应为(L-k)。如果长度小于k的单词，则不应选择该单词。当它们的长度不同时或它们在相同位置包含不同字符时，两个子序列彼此不同。我们必须找到p作为模数的结果，其中p是一个素数。

因此，如果输入类似于n = 6，k = 5，p = 11，则输出将为7。

为此，我们将按照以下步骤进行操作 –

创建一个空字典memo
n：= n + 1，k：= k + 1
fact：=具有一个元素1的列表
对于i在范围1到p – 1中，执行
- 将（事实的最后一个元素* i mod p）插入事实的末尾
如果memo中存在p，则
- inv_fact：= memo[p]
否则，
- inv：=具有两个元素0和1的列表
- 对于i在范围2到p – 1中，执行
  - 将（p – floor of p/i * inv[p mod i] mod p）插入inv的末尾
- inv_fact：=具有一个元素1的列表
- 对于i在范围1到p – 1中，执行
  - 将（inv_fact的最后一个元素* inv[i] mod p）插入inv_fact的末尾
- memo[p]：= inv_fact
结果：= 1
当n> 0时，
- n1：= n mod p
- k1：= k mod p
- 如果k1 > n1，则
  - 返回0
- 结果：=结果事实[n1] inv_fact[k1]* inv_fact[n1-k1] mod p
- n：=（n/p的底数）
- k：= floor of 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))