3129. Find All Possible Stable Binary Arrays I

Description

You are given 3 positive integers zero, one, and limit.

A binary array arr is called stable if:

• The number of occurrences of 0 in arr is exactly zero.
• The number of occurrences of 1 in arr is exactly one.
• Each subarray of arr with a size greater than limit must contain both 0 and 1.

Return the total number of stable binary arrays.

Since the answer may be very large, return it modulo 109 + 7.

Example 1:

Input: zero = 1, one = 1, limit = 2

Output: 2

Explanation:

The two possible stable binary arrays are [1,0] and [0,1], as both arrays have a single 0 and a single 1, and no subarray has a length greater than 2.

Example 2:

Input: zero = 1, one = 2, limit = 1

Output: 1

Explanation:

The only possible stable binary array is [1,0,1].

Note that the binary arrays [1,1,0] and [0,1,1] have subarrays of length 2 with identical elements, hence, they are not stable.

Example 3:

Input: zero = 3, one = 3, limit = 2

Output: 14

Explanation:

All the possible stable binary arrays are [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], and [1,1,0,1,0,0].

Constraints:

• 1 <= zero, one, limit <= 200

Solutions

We design a function $dfs(i, j, k)$ to represent the number of stable binary arrays that satisfy the problem conditions when there are $i$ $0$s and $j$ $1$s left, and the next number to be filled is $k$. The answer is $dfs(zero, one, 0) + dfs(zero, one, 1)$.

The calculation process of the function $dfs(i, j, k)$ is as follows:

• If $i < 0$ or $j < 0$, return $0$.
• If $i = 0$, return $1$ when $k = 1$ and $j \leq \text{limit}$, otherwise return $0$.
• If $j = 0$, return $1$ when $k = 0$ and $i \leq \text{limit}$, otherwise return $0$.
• If $k = 0$, we consider the case where the previous number is $0$, $dfs(i - 1, j, 0)$, and the case where the previous number is $1$, $dfs(i - 1, j, 1)$. If the previous number is $0$, it may cause more than $\text{limit}$ $0$s in the subarray, i.e., the situation where the $\text{limit} + 1$
• class Solution {
private final int mod = (int) 1e9 + 7;
private Long[][][] f;
private int limit;

public int numberOfStableArrays(int zero, int one, int limit) {
f = new Long[zero + 1][one + 1][2];
this.limit = limit;
return (int) ((dfs(zero, one, 0) + dfs(zero, one, 1)) % mod);
}

private long dfs(int i, int j, int k) {
if (i < 0 || j < 0) {
return 0;
}
if (i == 0) {
return k == 1 && j <= limit ? 1 : 0;
}
if (j == 0) {
return k == 0 && i <= limit ? 1 : 0;
}
if (f[i][j][k] != null) {
return f[i][j][k];
}
if (k == 0) {
f[i][j][k]
= (dfs(i - 1, j, 0) + dfs(i - 1, j, 1) - dfs(i - limit - 1, j, 1) + mod) % mod;
} else {
f[i][j][k]
= (dfs(i, j - 1, 0) + dfs(i, j - 1, 1) - dfs(i, j - limit - 1, 0) + mod) % mod;
}
return f[i][j][k];
}
}

• using ll = long long;

class Solution {
public:
int numberOfStableArrays(int zero, int one, int limit) {
this->limit = limit;
f = vector<vector<array<ll, 2>>>(zero + 1, vector<array<ll, 2>>(one + 1, {-1, -1}));
return (dfs(zero, one, 0) + dfs(zero, one, 1)) % mod;
}

private:
const int mod = 1e9 + 7;
int limit;
vector<vector<array<ll, 2>>> f;

ll dfs(int i, int j, int k) {
if (i < 0 || j < 0) {
return 0;
}
if (i == 0) {
return k == 1 && j <= limit;
}
if (j == 0) {
return k == 0 && i <= limit;
}
ll& res = f[i][j][k];
if (res != -1) {
return res;
}
if (k == 0) {
res = (dfs(i - 1, j, 0) + dfs(i - 1, j, 1) - dfs(i - limit - 1, j, 1) + mod) % mod;
} else {
res = (dfs(i, j - 1, 0) + dfs(i, j - 1, 1) - dfs(i, j - limit - 1, 0) + mod) % mod;
}
return res;
}
};

• class Solution:
def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
@cache
def dfs(i: int, j: int, k: int) -> int:
if i == 0:
return int(k == 1 and j <= limit)
if j == 0:
return int(k == 0 and i <= limit)
if k == 0:
return (
dfs(i - 1, j, 0)
+ dfs(i - 1, j, 1)
- (0 if i - limit - 1 < 0 else dfs(i - limit - 1, j, 1))
)
return (
dfs(i, j - 1, 0)
+ dfs(i, j - 1, 1)
- (0 if j - limit - 1 < 0 else dfs(i, j - limit - 1, 0))
)

mod = 10**9 + 7
ans = (dfs(zero, one, 0) + dfs(zero, one, 1)) % mod
dfs.cache_clear()
return ans


• func numberOfStableArrays(zero int, one int, limit int) int {
const mod int = 1e9 + 7
f := make([][][2]int, zero+1)
for i := range f {
f[i] = make([][2]int, one+1)
for j := range f[i] {
f[i][j] = [2]int{-1, -1}
}
}
var dfs func(i, j, k int) int
dfs = func(i, j, k int) int {
if i < 0 || j < 0 {
return 0
}
if i == 0 {
if k == 1 && j <= limit {
return 1
}
return 0
}
if j == 0 {
if k == 0 && i <= limit {
return 1
}
return 0
}
res := &f[i][j][k]
if *res != -1 {
return *res
}
if k == 0 {
*res = (dfs(i-1, j, 0) + dfs(i-1, j, 1) - dfs(i-limit-1, j, 1) + mod) % mod
} else {
*res = (dfs(i, j-1, 0) + dfs(i, j-1, 1) - dfs(i, j-limit-1, 0) + mod) % mod
}
return *res
}
return (dfs(zero, one, 0) + dfs(zero, one, 1)) % mod
}