Python程序：查找从Ajob序列中选择序列的方法数

假设有一种叫做Ajob的奇怪语言。它有无限数量的字母。我们知道这种语言中的n个单词。第一个单词是一个字符长，第二个单词是两个字符长，依此类推。并且一个单词中的所有字母都是唯一的。如果我们选择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，执行以下操作：
    • 在fact的末尾插入（fact的最后一个元素 * i mod p）
  • 如果memo中存在p，则
    • inv_fact := memo[p]
  • 否则，
    • inv := 一个包含两个元素0和1的列表
    • 对于i从2到p - 1，执行以下操作：
      • 在inv的末尾插入（p - floor of p/i * inv[p mod i] mod p）
    • inv_fact := 一个包含一个元素1的列表
    • 对于i从1到p - 1，执行以下操作：
      • 在inv_fact的末尾插入（inv_fact的最后一个元素 * inv[i] mod p）
    • memo[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 := floor of (n/p)
    • k := floor of k/p
  • 返回ret

示例

让我们看看以下实现，以获得更好的理解：

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

更新于: 2021年10月23日

159 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告