用 Python 编写程序，找出从 Ajob 序列中选择序列的方法数量

pythonserver side programmingprogramming更新于 2026/1/31 12:28:17

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

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

要解决这个问题，我们将遵循以下步骤 −

创建一个空字典备忘录
n := n + 1, k := k + 1
事实 := 一个包含一个元素 1 的列表
对于范围为 1 到 p - 1 的 i，执行
- 在事实末尾插入(事实的最后一个元素 * i mod p)
如果备忘录中存在 p，则
- inv_fact := memo[p]
否则，
- inv := 一个有两个元素 0 和 1 的列表
- 对于范围在 2 到 p - 1 内的 i，执行
  - 在 inv 末尾插入 (p - p/i 的下限 * inv[p mod i] mod p)
- inv_fact := 一个只有一个元素 1 的列表
- 对于范围在 1 到 p - 1 内的 i，执行
  - 在 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))