用于查找我们可以从 Python 中的 Ajob 序列中选择序列的多种方法的程序

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

因此，如果输入像 n = 6、k = 5、p = 11，那么输出将是 7。

示例

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

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