資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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 次瀏覽
廣告