上海网络营销网站建设,成都网站建设_创新互联,百度惠生活商家入驻,响应式 网站 开发1. 题目截图 2.题目分析
需要把其分为多个段进行填充 长为k的段#xff0c;从两端往中间填充的方案数有2 ** (k - 1)种 组合数就是选哪几个数填哪几个段即可
3.组合数含逆元模版
MOD 1_000_000_007
MX 100_000# 组合数模板
fac [0] * MX
fac[0] 1
for i in range(1, MX…1. 题目截图 2.题目分析
需要把其分为多个段进行填充 长为k的段从两端往中间填充的方案数有2 ** (k - 1)种 组合数就是选哪几个数填哪几个段即可
3.组合数含逆元模版
MOD 1_000_000_007
MX 100_000# 组合数模板
fac [0] * MX
fac[0] 1
for i in range(1, MX):fac[i] fac[i - 1] * i % MODinv_fac [0] * MX
inv_fac[MX - 1] pow(fac[MX - 1], -1, MOD)
for i in range(MX - 1, 0, -1):inv_fac[i - 1] inv_fac[i] * i % MODdef comb(n: int, k: int) - int: # 啥时候填return fac[n] * inv_fac[k] % MOD * inv_fac[n - k] % MODac code
MOD 1_000_000_007
MX 100_000# 组合数模板
fac [0] * MX
fac[0] 1
for i in range(1, MX):fac[i] fac[i - 1] * i % MODinv_fac [0] * MX
inv_fac[MX - 1] pow(fac[MX - 1], -1, MOD)
for i in range(MX - 1, 0, -1):inv_fac[i - 1] inv_fac[i] * i % MODdef comb(n: int, k: int) - int: # 啥时候填return fac[n] * inv_fac[k] % MOD * inv_fac[n - k] % MODclass Solution:def numberOfSequence(self, n: int, a: List[int]) - int:m len(a)total n - mans comb(total, a[0]) * comb(total - a[0], n - a[-1] - 1) % MODtotal - a[0] n - a[-1] - 1e 0for p, q in pairwise(a):k q - p - 1if k:e k - 1 # 长度为k的连续序列填满的种数有2 ** (k - 1)ans ans * comb(total, k) % MODtotal - kreturn ans * pow(2, e, MOD) % MOD
