用于查找我们可以从 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