描述：
給定兩個正整數 N 和 R，有多少種不同的方法可以將長度為 N 的桿切成 R 段，使得每段的長度都是正整數？以 1,000,000,007 為模輸出此答案。
例子：
當 N = 7 且 R = 3 時，有 15 種方法可以將長度為 7 的桿切成 3 段： (1,1,5) , (1,5,1), (5,1,1) , (1 ,2,4) , (1,4,2) (2,1,4), (2,4,1) , (4,1,2), (4,2,1) , (1,3, 3), (3,1,3), (3,3,1), (2,2,3), (2,3,2), (3,2,2)。
約束：
1 <= R <= N <= 200,000
測驗用例：
N R Output
7 3 15
36 6 324632
81 66 770289477
96 88 550930798
我的做法：
我知道答案是(N-1 choose R-1) mod 1000000007。我已經嘗試了所有不同的方法來計算它，但是 10 個測驗用例中總是有 7 個超出了時間限制。這是我的代碼，誰能告訴我我可以使用什么其他方法來實作O(1)時間復雜度。
from math import factorial
def new(n, r):
D = factorial(n - 1) // (factorial(r - 1) * factorial(n - r))
return (D % 1000000007)
if __name__ == '__main__':
N = [7, 36, 81, 96]
R = [3, 6, 66, 88]
answer = [new(n, r) for n,r in zip(N,R)]
print(answer)
uj5u.com熱心網友回復：
我認為有兩個重大優化問題正在尋找您利用。第一個是快取 的中間值factorial()以節省大批量 (large T) 的計算作業量。第二個優化是逐步減少您的價值 mod 1000000007，因此您的數字保持較小，乘法保持恒定時間。我已經更新了下面的示例以使用自定義函式和 預先計算階乘表itertools.accumulate，而不僅僅是在遞回實作中快取呼叫（這將消除您看到的遞回深度問題）。
from itertools import accumulate
MOD_BASE = 1000000007
N_BOUND = 200000
def modmul(m):
def mul(x, y):
return x * y % m
return mul
FACTORIALS = [1] list(accumulate(range(1, N_BOUND 1), modmul(MOD_BASE)))
def nck(n, k, m):
numerator = FACTORIALS[n]
denominator = FACTORIALS[k] * FACTORIALS[n-k]
return numerator * pow(denominator, -1, m) % m
def solve(n, k):
return nck(n-1, k-1, MOD_BASE)
針對示例運行此命令：
>>> pairs = [(36, 6), (81, 66), (96, 88)]
>>> print([solve(n, k) for n, k in pairs])
[324632, 770289477, 550930798]
uj5u.com熱心網友回復：
我從Ivaylo Strandjev 接受的答案中逐字翻譯了代碼，它的運行速度要快得多：
def get_degree(n, p):# { // returns the degree with which p is in n!
degree_num = 0
u = p
temp = n
while (u <= temp):
degree_num = temp // u
u *= p
return degree_num
def degree(a, k, p):
res = 1
cur = a
while (k):
if (k % 2):
res = (res * cur) % p
k //= 2
cur = (cur * cur) % p
return res
def CNKmodP( n, k, p):
num_degree = get_degree(n, p) - get_degree(n - k, p)
den_degree = get_degree(k, p)
if (num_degree > den_degree):
return 0
res = 1
for i in range(n, n - k, -1):
ti = i
while(ti % p == 0):
ti //= p
res = (res * ti) % p
denom = 1
for i in range(1, k 1):
ti = i
while(ti % p == 0):
ti //= p
denom = (denom * ti) % p
res = (res * degree(denom, p-2, p)) % p
return res
要應用這種方法，您只需要呼叫
result = CNKmodP(n-1, r-1, 1000000007)
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/382595.html