力扣第 129 场双周赛第 4 题
题目
给你 3 个正整数 zero ，one 和 limit 。
一个 二进制数组 arr 如果满足以下条件，那么我们称它是 稳定的 ：
- 0 在
arr 中出现次数 恰好 为 zero 。
- 1 在
arr 中出现次数 恰好 为 one 。
arr 中每个长度超过 limit 的 子数组 都 同时 包含 0 和 1 。
请你返回 稳定 二进制数组的 总 数目。
由于答案可能很大，将它对 109 + 7 取余 后返回。
示例 1：
输入：zero = 1, one = 1, limit = 2
输出：2
解释：
两个稳定的二进制数组为 [1,0] 和 [0,1] ，两个数组都有一个 0 和一个 1 ，且没有子数组长度大于 2 。
示例 2：
输入：zero = 1, one = 2, limit = 1
输出：1
解释：
唯一稳定的二进制数组是 [1,0,1] 。
二进制数组 [1,1,0] 和 [0,1,1] 都有长度为 2 且元素全都相同的子数组，所以它们不稳定。
示例 3：
输入：zero = 3, one = 3, limit = 2
输出：14
解释：
所有稳定的二进制数组包括 [0,0,1,0,1,1] ，[0,0,1,1,0,1] ，[0,1,0,0,1,1] ，[0,1,0,1,0,1] ，[0,1,0,1,1,0] ，[0,1,1,0,0,1] ，[0,1,1,0,1,0] ，[1,0,0,1,0,1] ，[1,0,0,1,1,0] ，[1,0,1,0,0,1] ，[1,0,1,0,1,0] ，[1,0,1,1,0,0] ，[1,1,0,0,1,0] 和 [1,1,0,1,0,0] 。
提示：
1 <= zero, one, limit <= 1000
相似问题：
分析
#1
同 3129
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
mod = 10**9+7
f = [[[0,0] for _ in range(one+1)] for _ in range(zero+1)]
for i in range(1,min(limit,zero)+1):
f[i][0][0] = 1
for j in range(1,min(limit,one)+1):
f[0][j][1] = 1
for i in range(1,zero+1):
for j in range(1,one+1):
f[i][j][0] = (sum(f[i-1][j])-(f[i-1-limit][j][1] if i>limit else 0))%mod
f[i][j][1] = (sum(f[i][j-1])-(f[i][j-1-limit][0] if j>limit else 0))%mod
return sum(f[-1][-1])%mod
|
4475 ms
#2
还可以利用容斥原理，思路见 从 DP 到组合数学。
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
mod = 10**9+7
ma = 1001
fac,inv = [1]*ma,[1]*ma
for i in range(1,ma):
fac[i] = fac[i-1]*i%mod
inv[i] = pow(fac[i],-1,mod)
def comb(m,n):
return fac[m]*inv[n]*inv[m-n]%mod
class Solution:
def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
n = min(zero+1,one)
f = [0]*(n+2)
for i in range((zero-1)//limit+1,min(one+1,zero)+1):
f[i] = comb(zero-1,i-1)
for j in range(1,(zero-i)//limit+1):
f[i] += (-1 if j%2 else 1)*comb(i,j)*comb(zero-j*limit-1,i-1)
f[i] %= mod
res = 0
for i in range((one-1)//limit+1,n+1):
g = comb(one-1,i-1)
for j in range(1,(one-i)//limit+1):
g += (-1 if j%2 else 1)*comb(i,j)*comb(one-j*limit-1,i-1)
res += g*(f[i-1]+f[i]*2+f[i+1])
res %= mod
return res
|
105 ms