这是spoj
问题链接http://www.spoj.com/problems/GOODB/。给你N, WA, TLE, RE
这样
N = WA+TLE+RE
N
满足他们的预测的不正确结果(分别是WA,TLE或RE)有多少种不同的有序组合?
这是我在python中的工作解决方案
import math
mod=10**9+7
def nck(n,k):
return math.factorial(n)/(math.factorial(n-k) * math.factorial(k))
n,w,t,r = map(int, raw_input().split())
print (nck(n,w) * nck(n-w, t)) % mod
这是针对同一问题的第二种方法,其假设是连续排列n1 a1,n2 a2,…,nk ak的方式的数目为
n!/(n1! n2! .... nk !)
, 在哪里
n = n1 + n2 +...+ nk
这是我第二种方法的代码
def modexp(x, y, mod):
res = 1
if x==0 or x==1:
return 1
while y != 0:
if y & 1 == 1:
'if y is odd'
res = (res * x) % mod
x = (x * x) % mod
y >>= 1
return res
def modfact(n, mod):
res = 1
while n >= 1:
res = (res * n) % mod
n -= 1
return res
mod = 10 ** 9 + 7
n, w, t, r = map(int, input().split())
resn = modfact(n, mod)
resw = modexp(modfact(w, mod), mod - 2, mod)
rest = modexp(modfact(t, mod), mod - 2, mod)
resr = modexp(modfact(r, mod), mod - 2, mod)
res = (resn*resw*rest*resr)%mod
print(res)
我只是不知道为什么我的第二种方法是错误的,有人可以提供我要去哪里的任何见解。
这行是可疑的:
res = resn//(resw*rest*resr)
resw
和朋友是阶乘的模逆,因此应该乘而不是除。最终结果应修改为10 ** 9 + 7。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句