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