AcWing 214. Devu和鲜花-python
原题链接
中等
作者:
viclao
,
2023-11-13 16:27:52
,
所有人可见
,
阅读 50
# 容斥原理 M个物品分给N个人的方案数%MOD
# 费马小定理+快速幂求逆元
from functools import lru_cache
def inv(a, p):
res = 1
k = p - 2
while k:
if k & 1:
res = res * a % p
a = a * a % p
k >>= 1
return res
@lru_cache(None)
def fact(n):
res = 1
for i in range(1, n + 1):
res = res * i % MOD
return res
# a!/b!(a - b)!
# 返回comb(a,b) % MOD
def comb(a, b):
if a < b:
return 0
up = 1
for i in range(a, a - b, -1):
up = i % MOD * up % MOD
return up * down % MOD
MOD = 10 ** 9 + 7
n, m = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(1 << n):
x, y = m + n - 1, n - 1
sign = 1
down = inv(fact(n - 1), MOD)
for j in range(n):
if i >> j & 1:
sign *= -1
x -= a[j] + 1
ans = (ans + comb(x,y)*sign) % MOD
print(ans)