N有多少种不同的有序组合

阿卡什尚德拉卡

这是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] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章