纯小白
勿笑
###python3
登录
class Solution:
def bitwiseComplement(self, N: int) -> int:
N = bin(N)[2:]
N = N.replace("0","2")
N = N.replace("1","0")
N = N.replace('2','1')
return int(N,2)
题目让我们把 $n$ 取反。
例如二进制 $n=11001$，取反后是 $00110$，即十进制的 $6$。
看上去，计算 ~n 就好了？
但这样做会把更高位的 $0$ 也取反，对于 $32$ 位整数来说，$11001$ 实际是 $00000000000000000000000000011001$，取反后是 $11111111111111111111111111100110$。
所以对于这个例子，要只把 $n$ 的低 $5$ 位取反，也就是计算 $n$ 和 $11111$ 的异或。
$11111$ 怎么算？设 $w=5$ 是 $n$ 的二进制长度，计算 1 << w 可以得到 $100000$，再减去 $1$，得到 $11111$。
特殊情况：根据题意，$n=0$ 反转后是 $1$，如果用库函数算 $n=0$ 的二进制长度，会算出 $0$，这会导致 $n$ 取反后的值是 $0$。所以特判 $n=0$ 的情况，返回 $1$。
###py
class Solution:
def bitwiseComplement(self, n: int) -> int:
if n == 0:
return 1
w = n.bit_length()
return ((1 << w) - 1) ^ n
###java
class Solution {
public int bitwiseComplement(int n) {
if (n == 0) {
return 1;
}
int w = 32 - Integer.numberOfLeadingZeros(n);
return ((1 << w) - 1) ^ n;
}
}
###cpp
class Solution {
public:
int bitwiseComplement(int n) {
if (n == 0) {
return 1;
}
int w = bit_width((uint32_t) n);
return ((1 << w) - 1) ^ n;
}
};
###c
int bitwiseComplement(int n) {
if (n == 0) {
return 1;
}
int w = 32 - __builtin_clz(n);
return ((1 << w) - 1) ^ n;
}
###go
func bitwiseComplement(n int) int {
if n == 0 {
return 1
}
w := bits.Len(uint(n))
return 1<<w - 1 ^ n
}
###js
var bitwiseComplement = function(n) {
if (n === 0) {
return 1;
}
const w = 32 - Math.clz32(n);
return ((1 << w) - 1) ^ n;
};
###rust
impl Solution {
pub fn bitwise_complement(n: i32) -> i32 {
if n == 0 {
return 1;
}
let w = n.ilog2() + 1;
((1 << w) - 1) ^ n
}
}
见下面位运算题单的「一、基础题」。
欢迎关注 B站@灵茶山艾府
每个非负整数 N 都有其二进制表示。例如， 5 可以被表示为二进制 "101"，11 可以用二进制 "1011" 表示，依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。
二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。
给你一个十进制数 N，请你返回其二进制表示的反码所对应的十进制整数。
示例 1：
输入：5 输出：2 解释：5 的二进制表示为 "101"，其二进制反码为 "010"，也就是十进制中的 2 。
示例 2：
输入：7 输出：0 解释：7 的二进制表示为 "111"，其二进制反码为 "000"，也就是十进制中的 0 。
示例 3：
输入：10 输出：5 解释：10 的二进制表示为 "1010"，其二进制反码为 "0101"，也就是十进制中的 5 。
提示：
0 <= N < 10^9拿到题目先不要急，注意观察。
示例1：
输入：5 101
输出：2 010
所以本质是 111（7） - 101（5） = 010（2）
问题转化为：求输入数字N的二进制数长度
求得N的二进制数长度length后，就可以用长为length,各位均为1的数字减去N，即可得到最终结果
由于是二进制，所以可以使用 (int) log2(N) + 1来求其长度
比如5（101）的计算结果为：
(int) log2(N) + 1 = 2 + 1 = 3
而长为length，各位均为1的二进制数字的大小是 2 ^ length - 1
比如111 的大小即为 2^3 - 1 = 7
所以最终结果便是 2 ^ length - 1 - N
###java
class Solution {
public int bitwiseComplement(int N) {
//对于0需要单独讨论，因为log(x) 的定义域不包括0
if(N == 0) return 1;
//java中没有log2(x)函数，默认log以e为底，log10以10为底
//所以要用换底公式loga(x) / loga(y) = logy(x)
//所以loge(N) / loge(2) = log2(N)
int length = (int)(Math.log(N) / Math.log(2)) + 1;
return (int)(Math.pow(2, length)) - 1 - N;
}
}
方法1： 异或运算法
class Solution {
public:
int bitwiseComplement(int N) {
if(N==0)
return 1;
int temp1 = 1;
int temp2 = N;
while(temp2>0){//不停用temp1对原整数进行异或运算，每次运算结束后将temp1朝左移动1位
N ^= temp1;
temp1 = temp1 << 1;
temp2 = temp2 >> 1;
}
return N;
}
};
方法2： 高位差值法
方法2是看评论学会的，很巧妙～
class Solution {
public:
int bitwiseComplement(int N) {
int temp = 2;
while(temp<=N){
temp = temp << 1;
}
return temp - N - 1;
}
};
给你 3 个正整数 zero ，one 和 limit 。
一个 二进制数组 arr 如果满足以下条件，那么我们称它是 稳定的 ：
arr 中出现次数 恰好 为 zero 。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思路
根据稳定数组的前两个条件，可知稳定数组的长度为 $\textit{zero} + \textit{one}$。第三个条件可知，稳定数组不存在长度为 $\textit{limit} + 1$ 的全 $0$ 或全 $1$ 子数组。
接下来我们分解问题，包含 $\textit{zero}$ 个 $0$ 和 $\textit{one}$ 个 $1$ 的稳定数组，末位元素可能为 $1$，也可能为 $0$。
这样一来，我们就将问题分解为子问题了，可以用动态规划求解。用函数 $\textit{dp}(\textit{zero},\textit{one},\textit{lastBit})$，来求解包含 $\textit{zero}$ 个 $0$ 和 $\textit{one}$ 个 $1$，并且末位元素为 $\textit{lastBit}$ 的稳定数组的个数，其中 $\textit{lastBit}$ 为 $0$ 或 $1$。根据上面的讨论，可以得到递推公式：
另外考虑边界情况。如果 $\textit{zero}$ 为 $0$，那么当 $\textit{lastBit}$ 为 $1$ 或者 $\textit{one}$ 大于 $\textit{limit}$ 时，不存在这样的稳定数组，返回 $0$，否则返回 $1$。如果 $\textit{zero}$ 为 $1$，也有对应的结论。
我们用记忆化搜索的方式来计算结果，记录所有的中间状态，最终返回 $\textit{dp}(\textit{zero},\textit{one},0)$ + $\textit{dp}(\textit{zero},\textit{one},1)$ 取模后的结果。
代码
###Python
class Solution:
def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
mod = 10 ** 9 + 7
@cache
def dp(zero, one, lastBit):
if zero == 0:
if lastBit == 0 or one > limit:
return 0
else:
return 1
elif one == 0:
if lastBit == 1 or zero > limit:
return 0
else:
return 1
if lastBit == 0:
res = dp(zero - 1, one, 0) + dp(zero - 1, one, 1)
if zero > limit:
res -= dp(zero - limit - 1, one, 1)
else:
res = dp(zero, one - 1, 0) + dp(zero, one - 1, 1)
if one > limit:
res -= dp(zero, one - limit - 1, 0)
return res % mod
res = (dp(zero, one, 0) + dp(zero, one, 1)) % mod
dp.cache_clear()
return res
###C++
class Solution {
public:
int numberOfStableArrays(int zero, int one, int limit) {
int mod = 1e9 + 7;
vector<vector<vector<int>>> memo(zero + 1, vector<vector<int>>(one + 1, vector<int>(2, -1)));
function<int(int, int, int)> dp = [&](int zero, int one, int lastBit) -> int {
if (zero == 0) {
return (lastBit == 0 || one > limit) ? 0 : 1;
} else if (one == 0) {
return (lastBit == 1 || zero > limit) ? 0 : 1;
}
if (memo[zero][one][lastBit] == -1) {
int res = 0;
if (lastBit == 0) {
res = (dp(zero - 1, one, 0) + dp(zero - 1, one, 1)) % mod;
if (zero > limit) {
res = (res - dp(zero - limit - 1, one, 1) + mod) % mod;
}
} else {
res = (dp(zero, one - 1, 0) + dp(zero, one - 1, 1)) % mod;
if (one > limit) {
res = (res - dp(zero, one - limit - 1, 0) + mod) % mod;
}
}
memo[zero][one][lastBit] = res % mod;
}
return memo[zero][one][lastBit];
};
return (dp(zero, one, 0) + dp(zero, one, 1)) % mod;
}
};
###Java
class Solution {
static final int MOD = 1000000007;
int[][][] memo;
int limit;
public int numberOfStableArrays(int zero, int one, int limit) {
this.memo = new int[zero + 1][one + 1][2];
for (int i = 0; i <= zero; i++) {
for (int j = 0; j <= one; j++) {
Arrays.fill(memo[i][j], -1);
}
}
this.limit = limit;
return (dp(zero, one, 0) + dp(zero, one, 1)) % MOD;
}
public int dp(int zero, int one, int lastBit) {
if (zero == 0) {
return (lastBit == 0 || one > limit) ? 0 : 1;
} else if (one == 0) {
return (lastBit == 1 || zero > limit) ? 0 : 1;
}
if (memo[zero][one][lastBit] == -1) {
int res = 0;
if (lastBit == 0) {
res = (dp(zero - 1, one, 0) + dp(zero - 1, one, 1))% MOD;
if (zero > limit) {
res = (res - dp(zero - limit - 1, one, 1) + MOD) % MOD;
}
} else {
res = (dp(zero, one - 1, 0) + dp(zero, one - 1, 1)) % MOD;
if (one > limit) {
res = (res - dp(zero, one - limit - 1, 0) + MOD) % MOD;
}
}
memo[zero][one][lastBit] = res % MOD;
}
return memo[zero][one][lastBit];
}
}
###C#
public class Solution {
const int MOD = 1000000007;
int[][][] memo;
int limit;
public int NumberOfStableArrays(int zero, int one, int limit) {
this.memo = new int[zero + 1][][];
for (int i = 0; i <= zero; i++) {
memo[i] = new int[one + 1][];
for (int j = 0; j <= one; j++) {
memo[i][j] = new int[2];
Array.Fill(memo[i][j], -1);
}
}
this.limit = limit;
return (DP(zero, one, 0) + DP(zero, one, 1)) % MOD;
}
public int DP(int zero, int one, int lastBit) {
if (zero == 0) {
return (lastBit == 0 || one > limit) ? 0 : 1;
} else if (one == 0) {
return (lastBit == 1 || zero > limit) ? 0 : 1;
}
if (memo[zero][one][lastBit] == -1) {
int res = 0;
if (lastBit == 0) {
res = (DP(zero - 1, one, 0) + DP(zero - 1, one, 1))% MOD;
if (zero > limit) {
res = (res - DP(zero - limit - 1, one, 1) + MOD) % MOD;
}
} else {
res = (DP(zero, one - 1, 0) + DP(zero, one - 1, 1)) % MOD;
if (one > limit) {
res = (res - DP(zero, one - limit - 1, 0) + MOD) % MOD;
}
}
memo[zero][one][lastBit] = res % MOD;
}
return memo[zero][one][lastBit];
}
}
###C
#define MOD 1000000007
int ***createMemo(int zero, int one) {
int ***memo = malloc((zero + 1) * sizeof(int **));
for (int i = 0; i <= zero; ++i) {
memo[i] = malloc((one + 1) * sizeof(int *));
for (int j = 0; j <= one; ++j) {
memo[i][j] = malloc(2 * sizeof(int));
memo[i][j][0] = -1;
memo[i][j][1] = -1;
}
}
return memo;
}
void freeMemo(int zero, int one, int ***memo) {
for (int i = 0; i <= zero; ++i) {
for (int j = 0; j <= one; ++j) {
free(memo[i][j]);
}
free(memo[i]);
}
free(memo);
}
int dp(int zero, int one, int lastBit, int limit, int ***memo) {
if (zero == 0) {
return (lastBit == 0 || one > limit) ? 0 : 1;
} else if (one == 0) {
return (lastBit == 1 || zero > limit) ? 0 : 1;
}
if (memo[zero][one][lastBit] == -1) {
int res = 0;
if (lastBit == 0) {
res = (dp(zero - 1, one, 0, limit, memo) + dp(zero - 1, one, 1, limit, memo)) % MOD;
if (zero > limit) {
res = (res - dp(zero - limit - 1, one, 1, limit, memo) + MOD) % MOD;
}
} else {
res = (dp(zero, one - 1, 0, limit, memo) + dp(zero, one - 1, 1, limit, memo)) % MOD;
if (one > limit) {
res = (res - dp(zero, one - limit - 1, 0, limit, memo) + MOD) % MOD;
}
}
memo[zero][one][lastBit] = res % MOD;
}
return memo[zero][one][lastBit];
}
int numberOfStableArrays(int zero, int one, int limit) {
int ***memo = createMemo(zero, one);
int result = (dp(zero, one, 0, limit, memo) + dp(zero, one, 1, limit, memo)) % MOD;
freeMemo(zero, one, memo);
return result;
}
###Go
const MOD = 1000000007
func numberOfStableArrays(zero int, one int, limit int) int {
memo := make([][][]int, zero + 1)
for i := range memo {
memo[i] = make([][]int, one + 1)
for j := range memo[i] {
memo[i][j] = []int{-1, -1}
}
}
var dp func(int, int, int) int
dp = func(zero, one, lastBit int) int {
if zero == 0 {
if lastBit == 0 || one > limit {
return 0
} else {
return 1
}
} else if one == 0 {
if lastBit == 1 || zero > limit {
return 0
} else {
return 1
}
}
if memo[zero][one][lastBit] == -1 {
res := 0
if lastBit == 0 {
res = (dp(zero-1, one, 0) + dp(zero - 1, one, 1)) % MOD
if zero > limit {
res = (res - dp(zero - limit - 1, one, 1) + MOD) % MOD
}
} else {
res = (dp(zero, one - 1, 0) + dp(zero, one - 1, 1)) % MOD
if one > limit {
res = (res - dp(zero, one - limit - 1, 0) + MOD) % MOD
}
}
memo[zero][one][lastBit] = res % MOD
}
return memo[zero][one][lastBit]
}
return (dp(zero, one, 0) + dp(zero, one, 1)) % MOD
}
###JavaScript
const MOD = 1000000007;
var numberOfStableArrays = function(zero, one, limit) {
const memo = Array.from({ length: zero + 1 }, () =>
Array.from({ length: one + 1 }, () => [-1, -1])
);
function dp(zero, one, lastBit) {
if (zero === 0) {
return lastBit === 0 || one > limit ? 0 : 1;
} else if (one === 0) {
return lastBit === 1 || zero > limit ? 0 : 1;
}
if (memo[zero][one][lastBit] === -1) {
let res = 0;
if (lastBit === 0) {
res = (dp(zero - 1, one, 0) + dp(zero - 1, one, 1)) % MOD;
if (zero > limit) {
res = (res - dp(zero - limit - 1, one, 1) + MOD) % MOD;
}
} else {
res = (dp(zero, one - 1, 0) + dp(zero, one - 1, 1)) % MOD;
if (one > limit) {
res = (res - dp(zero, one - limit - 1, 0) + MOD) % MOD;
}
}
memo[zero][one][lastBit] = res % MOD;
}
return memo[zero][one][lastBit];
}
return (dp(zero, one, 0) + dp(zero, one, 1)) % MOD;
};
###TypeScript
const MOD = 1000000007;
function numberOfStableArrays(zero: number, one: number, limit: number): number {
const memo: number[][][] = Array.from({ length: zero + 1 }, () =>
Array.from({ length: one + 1 }, () => [-1, -1])
);
function dp(zero: number, one: number, lastBit: number): number {
if (zero === 0) {
return lastBit === 0 || one > limit ? 0 : 1;
} else if (one === 0) {
return lastBit === 1 || zero > limit ? 0 : 1;
}
if (memo[zero][one][lastBit] === -1) {
let res = 0;
if (lastBit === 0) {
res = (dp(zero - 1, one, 0) + dp(zero - 1, one, 1)) % MOD;
if (zero > limit) {
res = (res - dp(zero - limit - 1, one, 1) + MOD) % MOD;
}
} else {
res = (dp(zero, one - 1, 0) + dp(zero, one - 1, 1)) % MOD;
if (one > limit) {
res = (res - dp(zero, one - limit - 1, 0) + MOD) % MOD;
}
}
memo[zero][one][lastBit] = res % MOD;
}
return memo[zero][one][lastBit];
}
return (dp(zero, one, 0) + dp(zero, one, 1)) % MOD;
};
###Rust
const MOD: i32 = 1000000007;
impl Solution {
pub fn number_of_stable_arrays(zero: i32, one: i32, limit: i32) -> i32 {
let mut memo = vec![vec![vec![-1; 2]; (one + 1) as usize]; (zero + 1) as usize];
fn dp(zero: usize, one: usize, last_bit: usize, limit: usize, memo: &mut Vec<Vec<Vec<i32>>>) -> i32 {
if zero == 0 {
return if last_bit == 0 || one > limit { 0 } else { 1 };
} else if one == 0 {
return if last_bit == 1 || zero > limit { 0 } else { 1 };
}
if memo[zero][one][last_bit] == -1 {
let mut res = 0;
if last_bit == 0 {
res = (dp(zero - 1, one, 0, limit, memo) + dp(zero - 1, one, 1, limit, memo)) % MOD;
if zero > limit {
res = (res - dp(zero - limit - 1, one, 1, limit, memo) + MOD) % MOD;
}
} else {
res = (dp(zero, one - 1, 0, limit, memo) + dp(zero, one - 1, 1, limit, memo)) % MOD;
if one > limit {
res = (res - dp(zero, one - limit - 1, 0, limit, memo) + MOD) % MOD;
}
}
memo[zero][one][last_bit] = res % MOD;
}
memo[zero][one][last_bit]
}
let zero = zero as usize;
let one = one as usize;
let limit = limit as usize;
(dp(zero, one, 0, limit, &mut memo) + dp(zero, one, 1, limit, &mut memo)) % MOD
}
}
复杂度分析
时间复杂度：$O(\textit{zero}\times\textit{one})$，动态规划的状态一共有 $O(\textit{zero}\times\textit{one})$ 种，每个状态消耗 $O(1)$ 时间消耗。
空间复杂度：$O(\textit{zero}\times\textit{one})$。
思路
方法一用的是记忆化搜索，状态的求解是自顶向下的。方法二中我们使用动态规划，从而自底向上来求出所有状态，并用数组保存结果。状态方程的关系和方法一一致。
代码
###Python
class Solution:
def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
mod = 10 ** 9 + 7
dp = [[[0, 0] for _ in range(one + 1)] for _ in range(zero + 1)]
for i in range(zero+1):
for j in range(one+1):
for lastBit in range(2):
if i == 0:
if lastBit == 0 or j > limit:
dp[i][j][lastBit] = 0
else:
dp[i][j][lastBit] = 1
elif j == 0:
if lastBit == 1 or i > limit:
dp[i][j][lastBit] = 0
else:
dp[i][j][lastBit] = 1
elif lastBit == 0:
dp[i][j][lastBit] = dp[i-1][j][0] + dp[i-1][j][1]
if i > limit:
dp[i][j][lastBit] -= dp[i-limit-1][j][1]
else:
dp[i][j][lastBit] = dp[i][j-1][0] + dp[i][j-1][1]
if j > limit:
dp[i][j][lastBit] -= dp[i][j-limit-1][0]
dp[i][j][lastBit] %= mod
return (dp[-1][-1][0] + dp[-1][-1][1]) % mod
###C++
class Solution {
public:
constexpr static int MOD = 1000000007;
int numberOfStableArrays(int zero, int one, int limit) {
vector<vector<vector<int>>> dp(zero + 1, vector<vector<int>>(one + 1, vector<int>(2)));
for (int i = 0; i <= zero; i++) {
for (int j = 0; j <= one; j++) {
for (int lastBit = 0; lastBit <= 1; lastBit++) {
if (i == 0) {
if (lastBit == 0 || j > limit) {
dp[i][j][lastBit] = 0;
} else {
dp[i][j][lastBit] = 1;
}
} else if (j == 0) {
if (lastBit == 1 || i > limit) {
dp[i][j][lastBit] = 0;
} else {
dp[i][j][lastBit] = 1;
}
} else if (lastBit == 0) {
dp[i][j][lastBit] = dp[i - 1][j][0] + dp[i - 1][j][1];
if (i > limit) {
dp[i][j][lastBit] -= dp[i - limit - 1][j][1];
}
} else {
dp[i][j][lastBit] = dp[i][j - 1][0] + dp[i][j -1 ][1];
if (j > limit) {
dp[i][j][lastBit] -= dp[i][j - limit - 1][0];
}
}
dp[i][j][lastBit] %= MOD;
if (dp[i][j][lastBit] < 0) {
dp[i][j][lastBit] += MOD;
}
}
}
}
return (dp[zero][one][0] + dp[zero][one][1]) % MOD;
}
};
###Java
class Solution {
public int numberOfStableArrays(int zero, int one, int limit) {
final int MOD = 1000000007;
int[][][] dp = new int[zero + 1][one + 1][2];
for (int i = 0; i <= zero; i++) {
for (int j = 0; j <= one; j++) {
for (int lastBit = 0; lastBit <= 1; lastBit++) {
if (i == 0) {
if (lastBit == 0 || j > limit) {
dp[i][j][lastBit] = 0;
} else {
dp[i][j][lastBit] = 1;
}
} else if (j == 0) {
if (lastBit == 1 || i > limit) {
dp[i][j][lastBit] = 0;
} else {
dp[i][j][lastBit] = 1;
}
} else if (lastBit == 0) {
dp[i][j][lastBit] = dp[i - 1][j][0] + dp[i - 1][j][1];
if (i > limit) {
dp[i][j][lastBit] -= dp[i - limit - 1][j][1];
}
} else {
dp[i][j][lastBit] = dp[i][j - 1][0] + dp[i][j -1 ][1];
if (j > limit) {
dp[i][j][lastBit] -= dp[i][j - limit - 1][0];
}
}
dp[i][j][lastBit] %= MOD;
if (dp[i][j][lastBit] < 0) {
dp[i][j][lastBit] += MOD;
}
}
}
}
return (dp[zero][one][0] + dp[zero][one][1]) % MOD;
}
}
###C#
public class Solution {
public int NumberOfStableArrays(int zero, int one, int limit) {
const int MOD = 1000000007;
int[][][] dp = new int[zero + 1][][];
for (int i = 0; i <= zero; i++) {
dp[i] = new int[one + 1][];
for (int j = 0; j <= one; j++) {
dp[i][j] = new int[2];
for (int lastBit = 0; lastBit <= 1; lastBit++) {
if (i == 0) {
if (lastBit == 0 || j > limit) {
dp[i][j][lastBit] = 0;
} else {
dp[i][j][lastBit] = 1;
}
} else if (j == 0) {
if (lastBit == 1 || i > limit) {
dp[i][j][lastBit] = 0;
} else {
dp[i][j][lastBit] = 1;
}
} else if (lastBit == 0) {
dp[i][j][lastBit] = dp[i - 1][j][0] + dp[i - 1][j][1];
if (i > limit) {
dp[i][j][lastBit] -= dp[i - limit - 1][j][1];
}
} else {
dp[i][j][lastBit] = dp[i][j - 1][0] + dp[i][j -1 ][1];
if (j > limit) {
dp[i][j][lastBit] -= dp[i][j - limit - 1][0];
}
}
dp[i][j][lastBit] %= MOD;
if (dp[i][j][lastBit] < 0) {
dp[i][j][lastBit] += MOD;
}
}
}
}
return (dp[zero][one][0] + dp[zero][one][1]) % MOD;
}
}
###Go
const MOD = 1000000007
func numberOfStableArrays(zero int, one int, limit int) int {
dp := make([][][]int, zero + 1)
for i := range dp {
dp[i] = make([][]int, one + 1)
for j := range dp[i] {
dp[i][j] = make([]int, 2)
}
}
for i := 0; i <= zero; i++ {
for j := 0; j <= one; j++ {
for lastBit := 0; lastBit <= 1; lastBit++ {
if i == 0 {
if lastBit == 0 || j > limit {
dp[i][j][lastBit] = 0
} else {
dp[i][j][lastBit] = 1
}
} else if j == 0 {
if lastBit == 1 || i > limit {
dp[i][j][lastBit] = 0
} else {
dp[i][j][lastBit] = 1
}
} else if lastBit == 0 {
dp[i][j][lastBit] = dp[i - 1][j][0] + dp[i - 1][j][1]
if i > limit {
dp[i][j][lastBit] -= dp[i - limit - 1][j][1]
}
} else {
dp[i][j][lastBit] = dp[i][j - 1][0] + dp[i][j - 1][1]
if j > limit {
dp[i][j][lastBit] -= dp[i][j - limit - 1][0]
}
}
dp[i][j][lastBit] %= MOD
if dp[i][j][lastBit] < 0 {
dp[i][j][lastBit] += MOD
}
}
}
}
return (dp[zero][one][0] + dp[zero][one][1]) % MOD
}
###C
#define MOD 1000000007
int numberOfStableArrays(int zero, int one, int limit) {
int dp[zero + 1][one + 1][2];
memset(dp, 0, sizeof(dp));
for (int i = 0; i <= zero; i++) {
for (int j = 0; j <= one; j++) {
for (int lastBit = 0; lastBit <= 1; lastBit++) {
if (i == 0) {
if (lastBit == 0 || j > limit) {
dp[i][j][lastBit] = 0;
} else {
dp[i][j][lastBit] = 1;
}
} else if (j == 0) {
if (lastBit == 1 || i > limit) {
dp[i][j][lastBit] = 0;
} else {
dp[i][j][lastBit] = 1;
}
} else if (lastBit == 0) {
dp[i][j][lastBit] = dp[i - 1][j][0] + dp[i - 1][j][1];
if (i > limit) {
dp[i][j][lastBit] -= dp[i - limit - 1][j][1];
}
} else {
dp[i][j][lastBit] = dp[i][j - 1][0] + dp[i][j - 1][1];
if (j > limit) {
dp[i][j][lastBit] -= dp[i][j - limit - 1][0];
}
}
dp[i][j][lastBit] %= MOD;
if (dp[i][j][lastBit] < 0) {
dp[i][j][lastBit] += MOD;
}
}
}
}
return (dp[zero][one][0] + dp[zero][one][1]) % MOD;
}
###JavaScript
const MOD = 1000000007;
var numberOfStableArrays = function(zero, one, limit) {
let dp = Array.from({ length: zero + 1 }, () =>
Array.from({ length: one + 1 }, () => [0, 0])
);
for (let i = 0; i <= zero; i++) {
for (let j = 0; j <= one; j++) {
for (let lastBit = 0; lastBit <= 1; lastBit++) {
if (i === 0) {
if (lastBit === 0 || j > limit) {
dp[i][j][lastBit] = 0;
} else {
dp[i][j][lastBit] = 1;
}
} else if (j === 0) {
if (lastBit === 1 || i > limit) {
dp[i][j][lastBit] = 0;
} else {
dp[i][j][lastBit] = 1;
}
} else if (lastBit === 0) {
dp[i][j][lastBit] = dp[i - 1][j][0] + dp[i - 1][j][1];
if (i > limit) {
dp[i][j][lastBit] -= dp[i - limit - 1][j][1];
}
} else {
dp[i][j][lastBit] = dp[i][j - 1][0] + dp[i][j - 1][1];
if (j > limit) {
dp[i][j][lastBit] -= dp[i][j - limit - 1][0];
}
}
dp[i][j][lastBit] %= MOD;
if (dp[i][j][lastBit] < 0) {
dp[i][j][lastBit] += MOD;
}
}
}
}
return (dp[zero][one][0] + dp[zero][one][1]) % MOD;
};
###TypeScript
const MOD = 1000000007;
function numberOfStableArrays(zero: number, one: number, limit: number): number {
let dp: number[][][] = Array.from({ length: zero + 1 }, () =>
Array.from({ length: one + 1 }, () => [0, 0])
);
for (let i = 0; i <= zero; i++) {
for (let j = 0; j <= one; j++) {
for (let lastBit = 0; lastBit <= 1; lastBit++) {
if (i === 0) {
if (lastBit === 0 || j > limit) {
dp[i][j][lastBit] = 0;
} else {
dp[i][j][lastBit] = 1;
}
} else if (j === 0) {
if (lastBit === 1 || i > limit) {
dp[i][j][lastBit] = 0;
} else {
dp[i][j][lastBit] = 1;
}
} else if (lastBit === 0) {
dp[i][j][lastBit] = dp[i - 1][j][0] + dp[i - 1][j][1];
if (i > limit) {
dp[i][j][lastBit] -= dp[i - limit - 1][j][1];
}
} else {
dp[i][j][lastBit] = dp[i][j - 1][0] + dp[i][j - 1][1];
if (j > limit) {
dp[i][j][lastBit] -= dp[i][j - limit - 1][0];
}
}
dp[i][j][lastBit] %= MOD;
if (dp[i][j][lastBit] < 0) {
dp[i][j][lastBit] += MOD;
}
}
}
}
return (dp[zero][one][0] + dp[zero][one][1]) % MOD;
};
###Rust
const MOD: i32 = 1000000007;
impl Solution {
pub fn number_of_stable_arrays(zero: i32, one: i32, limit: i32) -> i32 {
let mut dp = vec![vec![vec![0; 2]; one as usize + 1]; zero as usize + 1];
for i in 0..=zero as usize {
for j in 0..=one as usize {
for last_bit in 0..=1 {
if i == 0 {
if last_bit == 0 || j > limit as usize {
dp[i][j][last_bit] = 0;
} else {
dp[i][j][last_bit] = 1;
}
} else if j == 0 {
if last_bit == 1 || i > limit as usize {
dp[i][j][last_bit] = 0;
} else {
dp[i][j][last_bit] = 1;
}
} else if last_bit == 0 {
dp[i][j][last_bit] = dp[i - 1][j][0] + dp[i - 1][j][1];
if i > limit as usize {
dp[i][j][last_bit] -= dp[i - (limit as usize) - 1][j][1];
}
} else {
dp[i][j][last_bit] = dp[i][j - 1][0] + dp[i][j - 1][1];
if j > limit as usize {
dp[i][j][last_bit] -= dp[i][j - (limit as usize) - 1][0];
}
}
dp[i][j][last_bit] %= MOD;
if dp[i][j][last_bit] < 0 {
dp[i][j][last_bit] += MOD;
}
}
}
}
return (dp[zero as usize][one as usize][0] + dp[zero as usize][one as usize][1]) % MOD;
}
}
复杂度分析
时间复杂度：$O(\textit{zero}\times\textit{one})$，动态规划的状态一共有 $O(\textit{zero}\times\textit{one})$ 种，每个状态消耗 $O(1)$ 时间消耗。
空间复杂度：$O(\textit{zero}\times\textit{one})$。
前置知识：动态规划入门：从记忆化搜索到递推，其中包含如何把记忆化搜索 1:1 翻译成递推的技巧。
先解释 $\textit{limit}$，意思是数组中至多有连续 $\textit{limit}$ 个 $0$，且至多有连续 $\textit{limit}$ 个 $1$。
看示例 3，$\textit{zero}=3,\ \textit{one}=3,\ \textit{limit}=2$。
考虑稳定数组的最后一个位置填 $0$ 还是 $1$：
看上去，定义 $\textit{dfs}(i,j)$ 表示用 $i$ 个 $0$ 和 $j$ 个 $1$ 构造稳定数组的方案数？但这样定义不方便计算 $\textit{limit}$ 带来的影响。
比如 $\textit{limit}=3$，如果在以 $1000$ 结尾的稳定数组的后面，再添加一个 $0$，得到以 $10000$ 结尾的数组，这是不合法的。我们需要把这种不合法的情况减掉。
为了减去不合法的情况，我们需要知道稳定数组的最后一个数是 $0$ 还是 $1$。
改成定义 $\textit{dfs}(i,j,k)$ 表示用 $i$ 个 $0$ 和 $j$ 个 $1$ 构造长为 $i+j$ 的稳定数组的方案数，其中最后一个位置（第 $i+j$ 个位置）已经填入了 $k$，其中 $k$ 为 $0$ 或 $1$。
以 $k=0$ 为例，考虑 $\textit{dfs}(i,j,0)$ 怎么算。现在最后一个位置（第 $i+j$ 个位置）已经填入了 $0$，消耗了一个 $0$，还剩下 $i-1$ 个 $0$。问题变成用 $i-1$ 个 $0$ 和 $j$ 个 $1$ 构造长为 $i+j-1$ 的稳定数组的方案数。对于这个子问题，枚举最后一个位置（第 $i+j-1$ 个位置）填入 $k=0$ 还是 $k=1$，对应的方案数为 $\textit{dfs}(i-1,j,0)$ 和 $\textit{dfs}(i-1,j,1)$。
看上去，把这两种情况加起来，我们就得到了
$$
\textit{dfs}(i,j,0) = \textit{dfs}(i-1,j,0) + \textit{dfs}(i-1,j,1)
$$
但是，这会产生不合法的情况。
以 $\textit{limit}=3$ 为例说明。$\textit{dfs}(i-1,j,0)$ 是一些以 $0$ 结尾的稳定数组（合法数组），讨论末尾 $0$ 的个数：
若要通过 $\textit{dfs}(i-1,j,0)$ 计算 $\textit{dfs}(i,j,0)$，相当于往这 $\textit{dfs}(i-1,j,0)$ 个稳定数组的末尾再加一个 $0$：
一般地，在 $\textit{dfs}(i-1,j,0)$ 个稳定数组的末尾添加一个 $0$，会得到 $\textit{dfs}(i-\textit{limit}-1,j,1)$ 个不合法的数组。从上文的状态转移方程中减掉 $\textit{dfs}(i-\textit{limit}-1,j,1)$，得
$$
\textit{dfs}(i,j,0) = \textit{dfs}(i-1,j,0) + \textit{dfs}(i-1,j,1) - \textit{dfs}(i-\textit{limit}-1,j,1)
$$
同理得
$$
\textit{dfs}(i,j,1) = \textit{dfs}(i,j-1,0) + \textit{dfs}(i,j-1,1) - \textit{dfs}(i,j-\textit{limit}-1,0)
$$
递归边界：
递归入口：$\textit{dfs}(\textit{zero},\textit{one},0)+\textit{dfs}(\textit{zero},\textit{one},1)$，即答案。
请看 视频讲解 第四题，欢迎点赞关注~
###py
class Solution:
def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
MOD = 1_000_000_007
@cache # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
def dfs(i: int, j: int, k: int) -> int:
if i == 0:
return 1 if k == 1 and j <= limit else 0
if j == 0:
return 1 if k == 0 and i <= limit else 0
if k == 0:
return (dfs(i - 1, j, 0) + dfs(i - 1, j, 1) - (dfs(i - limit - 1, j, 1) if i > limit else 0)) % MOD
else: # else 可以去掉，这里仅仅是为了代码对齐
return (dfs(i, j - 1, 0) + dfs(i, j - 1, 1) - (dfs(i, j - limit - 1, 0) if j > limit else 0)) % MOD
ans = (dfs(zero, one, 0) + dfs(zero, one, 1)) % MOD
dfs.cache_clear() # 防止爆内存
return ans
###java
class Solution {
private static final int MOD = 1_000_000_007;
public int numberOfStableArrays(int zero, int one, int limit) {
int[][][] memo = new int[zero + 1][one + 1][2];
for (int[][] m : memo) {
for (int[] m2 : m) {
Arrays.fill(m2, -1); // -1 表示没有计算过
}
}
return (dfs(zero, one, 0, limit, memo) + dfs(zero, one, 1, limit, memo)) % MOD;
}
private int dfs(int i, int j, int k, int limit, int[][][] memo) {
if (i == 0) { // 递归边界
return k == 1 && j <= limit ? 1 : 0;
}
if (j == 0) { // 递归边界
return k == 0 && i <= limit ? 1 : 0;
}
if (memo[i][j][k] != -1) { // 之前计算过
return memo[i][j][k];
}
if (k == 0) {
// + MOD 保证答案非负
memo[i][j][k] = (int) (((long) dfs(i - 1, j, 0, limit, memo) + dfs(i - 1, j, 1, limit, memo) +
(i > limit ? MOD - dfs(i - limit - 1, j, 1, limit, memo) : 0)) % MOD);
} else {
memo[i][j][k] = (int) (((long) dfs(i, j - 1, 0, limit, memo) + dfs(i, j - 1, 1, limit, memo) +
(j > limit ? MOD - dfs(i, j - limit - 1, 0, limit, memo) : 0)) % MOD);
}
return memo[i][j][k];
}
}
###cpp
class Solution {
public:
int numberOfStableArrays(int zero, int one, int limit) {
const int MOD = 1'000'000'007;
vector memo(zero + 1, vector<array<int, 2>>(one + 1, {-1, -1})); // -1 表示没有计算过
auto dfs = [&](this auto&& dfs, int i, int j, int k) -> int {
if (i == 0) { // 递归边界
return k == 1 && j <= limit;
}
if (j == 0) { // 递归边界
return k == 0 && i <= limit;
}
int& res = memo[i][j][k]; // 注意这里是引用
if (res != -1) { // 之前计算过
return res;
}
if (k == 0) {
// + MOD 保证答案非负
res = ((long long) dfs(i - 1, j, 0) + dfs(i - 1, j, 1) +
(i > limit ? MOD - dfs(i - limit - 1, j, 1) : 0)) % MOD;
} else {
res = ((long long) dfs(i, j - 1, 0) + dfs(i, j - 1, 1) +
(j > limit ? MOD - dfs(i, j - limit - 1, 0) : 0)) % MOD;
}
return res;
};
return (dfs(zero, one, 0) + dfs(zero, one, 1)) % MOD;
}
};
###go
func numberOfStableArrays(zero, one, limit int) int {
const mod = 1_000_000_007
memo := make([][][2]int, zero+1)
for i := range memo {
memo[i] = make([][2]int, one+1)
for j := range memo[i] {
memo[i][j] = [2]int{-1, -1}
}
}
var dfs func(int, int, int) int
dfs = func(i, j, k int) (res int) {
if i == 0 { // 递归边界
if k == 1 && j <= limit {
return 1
}
return
}
if j == 0 { // 递归边界
if k == 0 && i <= limit {
return 1
}
return
}
p := &memo[i][j][k]
if *p != -1 { // 之前计算过
return *p
}
if k == 0 {
// +mod 保证答案非负
res = (dfs(i-1, j, 0) + dfs(i-1, j, 1)) % mod
if i > limit {
res = (res - dfs(i-limit-1, j, 1) + mod) % mod
}
} else {
res = (dfs(i, j-1, 0) + dfs(i, j-1, 1)) % mod
if j > limit {
res = (res - dfs(i, j-limit-1, 0) + mod) % mod
}
}
*p = res // 记忆化
return
}
return (dfs(zero, one, 0) + dfs(zero, one, 1)) % mod
}
和 $\textit{dfs}(i,j,k)$ 一样，定义 $f[i][j][k]$ 表示用 $i$ 个 $0$ 和 $j$ 个 $1$ 构造稳定数组的方案数，其中第 $i+j$ 个位置要填 $k$，其中 $k$ 为 $0$ 或 $1$。
状态转移方程：
$$
\begin{aligned}
f[i][j][0] &= f[i-1][j][0] + f[i-1][j][1] - f[i-\textit{limit}-1][j][1] \
f[i][j][1] &= f[i][j-1][0] + f[i][j-1][1] - f[i][j-\textit{limit}-1][0] \
\end{aligned}
$$
如果 $i\le \textit{limit}$ 则 $f[i-\textit{limit}-1][j][1]$ 视作 $0$，如果 $j\le \textit{limit}$ 则 $f[i][j-\textit{limit}-1][0]$ 视作 $0$。
初始值：$f[i][0][0] = f[0][j][1] = 1$，其中 $1\le i \le \min(\textit{limit}, \textit{zero}),\ 1\le j \le \min(\textit{limit}, \textit{one})$。翻译自递归边界。
答案：$f[\textit{zero}][\textit{one}][0] + f[\textit{zero}][\textit{one}][1]$。翻译自递归入口。
###py
class Solution:
def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
MOD = 1_000_000_007
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] = (f[i - 1][j][0] + f[i - 1][j][1] - (f[i - limit - 1][j][1] if i > limit else 0)) % MOD
f[i][j][1] = (f[i][j - 1][0] + f[i][j - 1][1] - (f[i][j - limit - 1][0] if j > limit else 0)) % MOD
return sum(f[-1][-1]) % MOD
###java
class Solution {
public int numberOfStableArrays(int zero, int one, int limit) {
final int MOD = 1_000_000_007;
int[][][] f = new int[zero + 1][one + 1][2];
for (int i = 1; i <= Math.min(limit, zero); i++) {
f[i][0][0] = 1;
}
for (int j = 1; j <= Math.min(limit, one); j++) {
f[0][j][1] = 1;
}
for (int i = 1; i <= zero; i++) {
for (int j = 1; j <= one; j++) {
// + MOD 保证答案非负
f[i][j][0] = (int) (((long) f[i - 1][j][0] + f[i - 1][j][1] + (i > limit ? MOD - f[i - limit - 1][j][1] : 0)) % MOD);
f[i][j][1] = (int) (((long) f[i][j - 1][0] + f[i][j - 1][1] + (j > limit ? MOD - f[i][j - limit - 1][0] : 0)) % MOD);
}
}
return (f[zero][one][0] + f[zero][one][1]) % MOD;
}
}
###cpp
class Solution {
public:
int numberOfStableArrays(int zero, int one, int limit) {
const int MOD = 1'000'000'007;
vector<vector<array<int, 2>>> f(zero + 1, vector<array<int, 2>>(one + 1));
for (int i = 1; i <= min(limit, zero); i++) {
f[i][0][0] = 1;
}
for (int j = 1; j <= min(limit, one); j++) {
f[0][j][1] = 1;
}
for (int i = 1; i <= zero; i++) {
for (int j = 1; j <= one; j++) {
// + MOD 保证答案非负
f[i][j][0] = ((long long) f[i - 1][j][0] + f[i - 1][j][1] + (i > limit ? MOD - f[i - limit - 1][j][1] : 0)) % MOD;
f[i][j][1] = ((long long) f[i][j - 1][0] + f[i][j - 1][1] + (j > limit ? MOD - f[i][j - limit - 1][0] : 0)) % MOD;
}
}
return (f[zero][one][0] + f[zero][one][1]) % MOD;
}
};
###go
func numberOfStableArrays(zero, one, limit int) (ans int) {
const mod = 1_000_000_007
f := make([][][2]int, zero+1)
for i := range f {
f[i] = make([][2]int, one+1)
}
for i := 1; i <= min(limit, zero); i++ {
f[i][0][0] = 1
}
for j := 1; j <= min(limit, one); j++ {
f[0][j][1] = 1
}
for i := 1; i <= zero; i++ {
for j := 1; j <= one; j++ {
f[i][j][0] = (f[i-1][j][0] + f[i-1][j][1]) % mod
if i > limit {
// + mod 保证答案非负
f[i][j][0] = (f[i][j][0] - f[i-limit-1][j][1] + mod) % mod
}
f[i][j][1] = (f[i][j-1][0] + f[i][j-1][1]) % mod
if j > limit {
f[i][j][1] = (f[i][j][1] - f[i][j-limit-1][0] + mod) % mod
}
}
}
return (f[zero][one][0] + f[zero][one][1]) % mod
}
回顾一个经典的组合数学问题：
这可以用隔板法解决，$n$ 个小球之间有 $n-1$ 个空隙，从中选择 $m-1$ 个空隙，插入 $m-1$ 个隔板，这样就把小球分成了 $m$ 组，并且每一组都是非空的，方案数就是 $n-1$ 选 $m-1$ 的组合数 $\dbinom {n-1} {m-1}$。
如何综合考虑 $0$ 和 $1$？要如何计算方案数？
例如 $10110001$，相当于把 $0$ 分成了 $2$ 组，把 $1$ 分成了 $3$ 组。
一般地，设 $1$ 分成了 $i$ 组，那么 $0$ 会分成多少组？有哪些情况？
有如下四种情况：
注意 $0$ 和 $1$ 内部的分组方案是互相独立的，例如
$$
\begin{aligned}
&11010001\
&10110001\
&10100011
\end{aligned}
$$
这些例子的 $0$ 的组数不变，$1$ 的组数不变，$0$ 的分组方式也不变（都是一个 $0$ 和三个 $0$），只有 $1$ 的分组方式在变。
根据乘法原理，综合考虑 $0$ 和 $1$，把 $1$ 分成 $i$ 组总的方案数，等于上面说的四种情况（只考虑 $0$，把 $0$ 分成 $i-1,i,i+1$ 组）的方案数之和，乘以只考虑 $1$，把 $1$ 分成 $i$ 组的方案数，即
$$
(f_0[i-1] + 2\cdot f_0[i] + f_0[i+1])\cdot f_1[i]
$$
接下来，考虑 $\textit{limit}$ 带来的影响。推荐先看 2929. 给小朋友们分糖果 II 以及 我的题解。
根据容斥原理，对于 $f_0[i] = \dbinom {\textit{zero}-1} {i-1}$，我们需要减去「至少 $1$ 组有超过 $\textit{limit}$ 个 $0$」的方案数，再加上「至少 $2$ 组有超过 $\textit{limit}$ 个 $0$」的方案数，再减去「至少 $3$ 组有超过 $\textit{limit}$ 个 $0$」的方案数，……，直到「至少 $j$ 组有超过 $\textit{limit}$ 个 $0$」的方案数，$j$ 的值见下文。
$$
\dbinom {i} {j} \dbinom {\textit{zero} - j\cdot \textit{limit}-1} {i-1}
$$
所以
$$
f_0[i] = \dbinom {\textit{zero}-1} {i-1} + \sum_{j} (-1)^j \dbinom {i} {j} \dbinom {\textit{zero} - j\cdot \textit{limit}-1} {i-1}
$$
其中 $j\ge 1$ 且需要满足 $\textit{zero} - j\cdot \textit{limit} \ge i$，即
$$
1\le j\le \left\lfloor\dfrac{zero - i}{\textit{limit}}\right\rfloor
$$
同理有
$$
f_1[i] = \dbinom {\textit{one}-1} {i-1} + \sum_{j} (-1)^j \dbinom {i} {j} \dbinom {\textit{one} - j\cdot \textit{limit}-1} {i-1}
$$
其中
$$
1\le j\le \left\lfloor\dfrac{one - i}{\textit{limit}}\right\rfloor
$$
最终答案为
$$
\sum_{i} (f_0[i-1] + 2\cdot f_0[i] + f_0[i+1])\cdot f_1[i]
$$
其中：
整理得
$$
\left\lceil\dfrac{\textit{one}}{\textit{limit}}\right\rceil \le i\le \min(\textit{one},\textit{zero}+1)
$$
代码实现时：
关于取模的知识点，见 模运算的世界：当加减乘除遇上取模。
###py
MOD = 1_000_000_007
MX = 1001
fac = [0] * MX # f[i] = i!
fac[0] = 1
for i in range(1, MX):
fac[i] = fac[i - 1] * i % MOD
inv_f = [0] * MX # inv_f[i] = i!^-1
inv_f[-1] = pow(fac[-1], -1, MOD)
for i in range(MX - 1, 0, -1):
inv_f[i - 1] = inv_f[i] * i % MOD
def comb(n: int, m: int) -> int:
return fac[n] * inv_f[m] * inv_f[n - m] % MOD
class Solution:
def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
if zero > one:
zero, one = one, zero # 保证空间复杂度为 O(min(zero, one))
f0 = [0] * (zero + 3)
for i in range((zero - 1) // limit + 1, zero + 1):
f0[i] = comb(zero - 1, i - 1)
for j in range(1, (zero - i) // limit + 1):
f0[i] = (f0[i] + (-1 if j % 2 else 1) * comb(i, j) * comb(zero - j * limit - 1, i - 1)) % MOD
ans = 0
for i in range((one - 1) // limit + 1, min(one, zero + 1) + 1):
f1 = comb(one - 1, i - 1)
for j in range(1, (one - i) // limit + 1):
f1 = (f1 + (-1 if j % 2 else 1) * comb(i, j) * comb(one - j * limit - 1, i - 1)) % MOD
ans = (ans + (f0[i - 1] + f0[i] * 2 + f0[i + 1]) * f1) % MOD
return ans
###java
class Solution {
private static final int MOD = 1_000_000_007;
private static final int MX = 1001;
private static final long[] F = new long[MX]; // f[i] = i!
private static final long[] INV_F = new long[MX]; // inv_f[i] = i!^-1
static {
F[0] = 1;
for (int i = 1; i < MX; i++) {
F[i] = F[i - 1] * i % MOD;
}
INV_F[MX - 1] = pow(F[MX - 1], MOD - 2);
for (int i = MX - 1; i > 0; i--) {
INV_F[i - 1] = INV_F[i] * i % MOD;
}
}
public int numberOfStableArrays(int zero, int one, int limit) {
if (zero > one) {
// swap，保证空间复杂度为 O(min(zero, one))
int t = zero;
zero = one;
one = t;
}
long[] f0 = new long[zero + 3];
for (int i = (zero - 1) / limit + 1; i <= zero; i++) {
f0[i] = comb(zero - 1, i - 1);
for (int j = 1; j <= (zero - i) / limit; j++) {
f0[i] = (f0[i] + (1 - j % 2 * 2) * comb(i, j) * comb(zero - j * limit - 1, i - 1)) % MOD;
}
}
long ans = 0;
for (int i = (one - 1) / limit + 1; i <= Math.min(one, zero + 1); i++) {
long f1 = comb(one - 1, i - 1);
for (int j = 1; j <= (one - i) / limit; j++) {
f1 = (f1 + (1 - j % 2 * 2) * comb(i, j) * comb(one - j * limit - 1, i - 1)) % MOD;
}
ans = (ans + (f0[i - 1] + f0[i] * 2 + f0[i + 1]) * f1) % MOD;
}
return (int) ((ans + MOD) % MOD); // 保证结果非负
}
private long comb(int n, int m) {
return F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD;
}
private static long pow(long x, int n) {
long res = 1;
for (; n > 0; n /= 2) {
if (n % 2 > 0) {
res = res * x % MOD;
}
x = x * x % MOD;
}
return res;
}
}
###cpp
const int MOD = 1'000'000'007;
const int MX = 1001;
long long F[MX]; // F[i] = i!
long long INV_F[MX]; // INV_F[i] = i!^-1
long long pow(long long x, int n) {
long long res = 1;
for (; n; n /= 2) {
if (n % 2) {
res = res * x % MOD;
}
x = x * x % MOD;
}
return res;
}
auto init = [] {
F[0] = 1;
for (int i = 1; i < MX; i++) {
F[i] = F[i - 1] * i % MOD;
}
INV_F[MX - 1] = pow(F[MX - 1], MOD - 2);
for (int i = MX - 1; i; i--) {
INV_F[i - 1] = INV_F[i] * i % MOD;
}
return 0;
}();
long long comb(int n, int m) {
return F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD;
}
class Solution {
public:
int numberOfStableArrays(int zero, int one, int limit) {
if (zero > one) {
swap(zero, one); // 保证空间复杂度为 O(min(zero, one))
}
vector<long long> f0(zero + 3);
for (int i = (zero - 1) / limit + 1; i <= zero; i++) {
f0[i] = comb(zero - 1, i - 1);
for (int j = 1; j <= (zero - i) / limit; j++) {
f0[i] = (f0[i] + (1 - j % 2 * 2) * comb(i, j) * comb(zero - j * limit - 1, i - 1)) % MOD;
}
}
long long ans = 0;
for (int i = (one - 1) / limit + 1; i <= min(one, zero + 1); i++) {
long long f1 = comb(one - 1, i - 1);
for (int j = 1; j <= (one - i) / limit; j++) {
f1 = (f1 + (1 - j % 2 * 2) * comb(i, j) * comb(one - j * limit - 1, i - 1)) % MOD;
}
ans = (ans + (f0[i - 1] + f0[i] * 2 + f0[i + 1]) * f1) % MOD;
}
return (ans + MOD) % MOD; // 保证结果非负
}
};
###go
const mod = 1_000_000_007
const mx = 1001
var f [mx]int // f[i] = i!
var invF [mx]int // invF[i] = i!^-1
func init() {
f[0] = 1
for i := 1; i < mx; i++ {
f[i] = f[i-1] * i % mod
}
invF[mx-1] = pow(f[mx-1], mod-2)
for i := mx - 1; i > 0; i-- {
invF[i-1] = invF[i] * i % mod
}
}
func comb(n, m int) int {
return f[n] * invF[m] % mod * invF[n-m] % mod
}
func numberOfStableArrays(zero, one, limit int) (ans int) {
if zero > one {
zero, one = one, zero // 保证空间复杂度为 O(min(zero, one))
}
f0 := make([]int, zero+3)
for i := (zero-1)/limit + 1; i <= zero; i++ {
f0[i] = comb(zero-1, i-1)
for j := 1; j <= (zero-i)/limit; j++ {
f0[i] = (f0[i] + (1-j%2*2)*comb(i, j)*comb(zero-j*limit-1, i-1)) % mod
}
}
for i := (one-1)/limit + 1; i <= min(one, zero+1); i++ {
f1 := comb(one-1, i-1)
for j := 1; j <= (one-i)/limit; j++ {
f1 = (f1 + (1-j%2*2)*comb(i, j)*comb(one-j*limit-1, i-1)) % mod
}
ans = (ans + (f0[i-1]+f0[i]*2+f0[i+1])*f1) % mod
}
return (ans + mod) % mod // 保证结果非负
}
func pow(x, n int) int {
res := 1
for ; n > 0; n /= 2 {
if n%2 > 0 {
res = res * x % mod
}
x = x * x % mod
}
return res
}
欢迎关注 B站@灵茶山艾府
给你 3 个正整数 zero ，one 和 limit 。
一个 二进制数组 arr 如果满足以下条件，那么我们称它是 稳定的 ：
arr 中出现次数 恰好 为 zero 。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 <= 200题目要求二进制数组 $\textit{arr}$ 中每个长度超过 $\textit{limit}$ 的子数组同时包含 $0$ 和 $1$，这个条件等价于二进制数组 $\textit{arr}$ 中每个长度等于 $\textit{limit} + 1$ 的子数组都同时包含 $0$ 和 $1$（读者可以思考一下证明过程）。
按照题目要求，我们需要将 $\textit{zero}$ 个 $0$ 和 $\textit{one}$ 个 $1$ 依次填入二进制数组 $\textit{arr}$，使用 $\textit{dp}_0[i][j]$ 表示已经填入 $i$ 个 $0$ 和 $\textit{j}$ 个 $1$，并且最后填入的数字为 $0$ 的可行方案数目，$\textit{dp}_1[i][j]$ 表示已经填入 $i$ 个 $0$ 和 $\textit{j}$ 个 $1$，并且最后填入的数字为 $1$ 的可行方案数目。对于 $\textit{dp}_0[i][j]$，我们分析一下它的转换方程：
当 $j = 0$ 且 $i \in [0, \min(\textit{zero}, \textit{limit})]$ 时：我们可以不断地填入 $0$，所以 $\textit{dp}_0[i][j] = 1$。
当 $i = 0$，或者 $j = 0$ 且 $i \notin [0, \min(\textit{zero}, \textit{limit})]$ 时：我们没法构造可行的方案，所以 $\textit{dp}_0[i][j] = 0$。
当 $i > 0$ 且 $j > 0$ 时：$\textit{dp}_0[i][j]$ 可以分别由 $\textit{dp}_0[i - 1][j]$ 和 $\textit{dp}_1[i - 1][j]$ 转移而来，分别考虑两种情况：
对于 $\textit{dp}_1[i - 1][j]$：显然可以通过在 $\textit{dp}_1[i - 1][j]$ 对应的所有填入方案后再填入一个 $0$ 得到对应的可行方案。
对于 $\textit{dp}_0[i - 1][j]$：当 $i \le \textit{limit}$ 时，显然可以通过在 $\textit{dp}_1[i - 1][j]$ 对应的所有填入方案后再填入一个 $0$ 得到对应的可行方案；当 $i \gt \textit{limit}$ 时，我们需要去除一些不可行的方案数。因为 $\textit{dp}_0[i - 1][j]$ 对应的所有填入方案都是可行的，而只有一种情况会在额外填入一个 $0$ 时，变成不可行，即先前已经连续填入 $\textit{limit}$ 个 $0$，对应的方案数为 $\textit{dp}_1[i - \textit{limit} - 1][j]$。
根据以上分析，我们有 $\textit{dp}_0[i][j]$ 的转移方程：
$$
\textit{dp}_0[i][j] = \begin{cases}
1, & i \in [0, \min(\textit{zero}, \textit{limit})], j = 0 \
\textit{dp}_1[i - 1][j] + \textit{dp}_0[i - 1][j] - \textit{dp}_1[i - \textit{limit} - 1][j], & i > limit, j > 0 \
\textit{dp}_1[i - 1][j] + \textit{dp}_0[i - 1][j], & i \in [0, limit], j > 0 \
0, & otherwise
\end{cases}
$$
同理，我们也可以获得 $\textit{dp}_1[i][j]$ 的转移方程：
$$
\textit{dp}_1[i][j] = \begin{cases}
1, & i = 0, j \in [0, \min(\textit{one}, \textit{limit})] \
\textit{dp}_0[i][j - 1] + \textit{dp}_1[i][j - 1] - \textit{dp}_0[i][j - \textit{limit} - 1], & i > 0, j > limit \
\textit{dp}_0[i][j - 1] + \textit{dp}_1[i][j - 1], & i > 0, j \in [0, limit] \
0, & otherwise
\end{cases}
$$
最后，稳定二进制数组的数目等于 $\textit{dp}_0[\textit{zero}][\textit{one}] + \textit{dp}_1[\textit{zero}][\textit{one}]$。
###C++
class Solution {
public:
int numberOfStableArrays(int zero, int one, int limit) {
vector<vector<vector<long long>>> dp(zero + 1, vector<vector<long long>>(one + 1, vector<long long>(2)));
long long mod = 1e9 + 7;
for (int i = 0; i <= min(zero, limit); i++) {
dp[i][0][0] = 1;
}
for (int j = 0; j <= min(one, limit); j++) {
dp[0][j][1] = 1;
}
for (int i = 1; i <= zero; i++) {
for (int j = 1; j <= one; j++) {
if (i > limit) {
dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1] - dp[i - limit - 1][j][1];
} else {
dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];
}
dp[i][j][0] = (dp[i][j][0] % mod + mod) % mod;
if (j > limit) {
dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0] - dp[i][j - limit - 1][0];
} else {
dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0];
}
dp[i][j][1] = (dp[i][j][1] % mod + mod) % mod;
}
}
return (dp[zero][one][0] + dp[zero][one][1]) % mod;
}
};
###Java
class Solution {
public int numberOfStableArrays(int zero, int one, int limit) {
final long MOD = 1000000007;
long[][][] dp = new long[zero + 1][one + 1][2];
for (int i = 0; i <= Math.min(zero, limit); i++) {
dp[i][0][0] = 1;
}
for (int j = 0; j <= Math.min(one, limit); j++) {
dp[0][j][1] = 1;
}
for (int i = 1; i <= zero; i++) {
for (int j = 1; j <= one; j++) {
if (i > limit) {
dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1] - dp[i - limit - 1][j][1];
} else {
dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];
}
dp[i][j][0] = (dp[i][j][0] % MOD + MOD) % MOD;
if (j > limit) {
dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0] - dp[i][j - limit - 1][0];
} else {
dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0];
}
dp[i][j][1] = (dp[i][j][1] % MOD + MOD) % MOD;
}
}
return (int) ((dp[zero][one][0] + dp[zero][one][1]) % MOD);
}
}
###C#
public class Solution {
public int NumberOfStableArrays(int zero, int one, int limit) {
const long MOD = 1000000007;
long[][][] dp = new long[zero + 1][][];
for (int i = 0; i <= zero; i++) {
dp[i] = new long[one + 1][];
for (int j = 0; j <= one; j++) {
dp[i][j] = new long[2];
}
}
for (int i = 0; i <= Math.Min(zero, limit); i++) {
dp[i][0][0] = 1;
}
for (int j = 0; j <= Math.Min(one, limit); j++) {
dp[0][j][1] = 1;
}
for (int i = 1; i <= zero; i++) {
for (int j = 1; j <= one; j++) {
if (i > limit) {
dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1] - dp[i - limit - 1][j][1];
} else {
dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];
}
dp[i][j][0] = (dp[i][j][0] % MOD + MOD) % MOD;
if (j > limit) {
dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0] - dp[i][j - limit - 1][0];
} else {
dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0];
}
dp[i][j][1] = (dp[i][j][1] % MOD + MOD) % MOD;
}
}
return (int) ((dp[zero][one][0] + dp[zero][one][1]) % MOD);
}
}
###Go
func numberOfStableArrays(zero int, one int, limit int) int {
dp := make([][][2]int, zero + 1)
mod := int(1e9 + 7)
for i := 0; i <= zero; i++ {
dp[i] = make([][2]int, one + 1)
}
for i := 0; i <= min(zero, limit); i++ {
dp[i][0][0] = 1
}
for j := 0; j <= min(one, limit); j++ {
dp[0][j][1] = 1
}
for i := 1; i <= zero; i++ {
for j := 1; j <= one; j++ {
if i > limit {
dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1] - dp[i - limit - 1][j][1]
} else {
dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1]
}
dp[i][j][0] = (dp[i][j][0] % mod + mod) % mod
if j > limit {
dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0] - dp[i][j - limit - 1][0]
} else {
dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0]
}
dp[i][j][1] = (dp[i][j][1] % mod + mod) % mod
}
}
return (dp[zero][one][0] + dp[zero][one][1]) % mod
}
###Python
class Solution:
def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
dp = [[[0, 0] for _ in range(one + 1)] for _ in range(zero + 1)]
mod = int(1e9 + 7)
for i in range(min(zero, limit) + 1):
dp[i][0][0] = 1
for j in range(min(one, limit) + 1):
dp[0][j][1] = 1
for i in range(1, zero + 1):
for j in range(1, one + 1):
if i > limit:
dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1] - dp[i - limit - 1][j][1]
else:
dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1]
dp[i][j][0] = (dp[i][j][0] % mod + mod) % mod
if j > limit:
dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0] - dp[i][j - limit - 1][0]
else:
dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0]
dp[i][j][1] = (dp[i][j][1] % mod + mod) % mod
return (dp[zero][one][0] + dp[zero][one][1]) % mod
###C
#define MOD 1000000007
int numberOfStableArrays(int zero, int one, int limit) {
long long dp[zero + 1][one + 1][2];
memset(dp, 0, sizeof(dp));
for (int i = 0; i <= (zero < limit ? zero : limit); ++i) {
dp[i][0][0] = 1;
}
for (int j = 0; j <= (one < limit ? one : limit); ++j) {
dp[0][j][1] = 1;
}
for (int i = 1; i <= zero; ++i) {
for (int j = 1; j <= one; ++j) {
if (i > limit) {
dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1] - dp[i - limit - 1][j][1];
} else {
dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];
}
dp[i][j][0] = (dp[i][j][0] % MOD + MOD) % MOD;
if (j > limit) {
dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0] - dp[i][j - limit - 1][0];
} else {
dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0];
}
dp[i][j][1] = (dp[i][j][1] % MOD + MOD) % MOD;
}
}
int result = (dp[zero][one][0] + dp[zero][one][1]) % MOD;
return result;
}
###JavaScript
const MOD = 1000000007;
var numberOfStableArrays = function(zero, one, limit) {
const dp = Array.from({ length: zero + 1 }, () =>
Array.from({ length: one + 1 }, () => [0, 0])
);
for (let i = 0; i <= Math.min(zero, limit); i++) {
dp[i][0][0] = 1;
}
for (let j = 0; j <= Math.min(one, limit); j++) {
dp[0][j][1] = 1;
}
for (let i = 1; i <= zero; i++) {
for (let j = 1; j <= one; j++) {
if (i > limit) {
dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1] - dp[i - limit - 1][j][1];
} else {
dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];
}
dp[i][j][0] = (dp[i][j][0] % MOD + MOD) % MOD;
if (j > limit) {
dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0] - dp[i][j - limit - 1][0];
} else {
dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0];
}
dp[i][j][1] = (dp[i][j][1] % MOD + MOD) % MOD;
}
}
return (dp[zero][one][0] + dp[zero][one][1]) % MOD;
};
###TypeScript
const MOD = 1000000007;
function numberOfStableArrays(zero: number, one: number, limit: number): number {
const dp: number[][][] = Array.from({ length: zero + 1 }, () =>
Array.from({ length: one + 1 }, () => [0, 0])
);
for (let i = 0; i <= Math.min(zero, limit); i++) {
dp[i][0][0] = 1;
}
for (let j = 0; j <= Math.min(one, limit); j++) {
dp[0][j][1] = 1;
}
for (let i = 1; i <= zero; i++) {
for (let j = 1; j <= one; j++) {
if (i > limit) {
dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1] - dp[i - limit - 1][j][1];
} else {
dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];
}
dp[i][j][0] = (dp[i][j][0] % MOD + MOD) % MOD;
if (j > limit) {
dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0] - dp[i][j - limit - 1][0];
} else {
dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0];
}
dp[i][j][1] = (dp[i][j][1] % MOD + MOD) % MOD;
}
}
return (dp[zero][one][0] + dp[zero][one][1]) % MOD;
};
###Rust
const MOD: i32 = 1000000007;
impl Solution {
pub fn number_of_stable_arrays(zero: i32, one: i32, limit: i32) -> i32 {
let mut dp = vec![vec![vec![0; 2]; one as usize + 1]; zero as usize + 1];
for i in 0..=zero.min(limit) as usize {
dp[i][0][0] = 1;
}
for j in 0..=one.min(limit) as usize {
dp[0][j][1] = 1;
}
for i in 1..=zero as usize {
for j in 1..=one as usize {
if i > limit as usize {
dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1] - dp[i - limit as usize - 1][j][1];
} else {
dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];
}
dp[i][j][0] = (dp[i][j][0] % MOD + MOD) % MOD;
if j > limit as usize {
dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0] - dp[i][j - limit as usize - 1][0];
} else {
dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0];
}
dp[i][j][1] = (dp[i][j][1] % MOD + MOD) % MOD;
}
}
(dp[zero as usize][one as usize][0] + dp[zero as usize][one as usize][1]) % MOD
}
}
复杂度分析
时间复杂度：$O(\textit{zero} \times \textit{one})$，其中 $\textit{zero}$ 和 $\textit{one}$ 分别为 $0$ 和 $1$ 的出现次数。
空间复杂度：$O(\textit{zero} \times \textit{one})$。
本题和双周赛第四题是一样的，请看 我的题解。
前记：读了读别人的题解，感觉 newhar 老师的思路更清晰易懂一点，推荐大家看 newhar 的题解，这里就记一下自己的解法。
以下题解中把 limit 简记为 $l$。
首先，题目要求序列中恰好出现 zero 个 $0$ 以及 one 个 $1$，显然序列的长度必须为 zero + one。记序列的长度为 $n$。
只要一个子数组包含 $0$ 和 $1$，那么所有完全包含它的子数组也会包含 $0$ 和 $1$。因此，题目中“arr 中每个长度超过 $l$ 的子数组都同时包含 $0$ 和 $1$”这一条件可以重写为：
arr中每个长度恰为 $(l + 1)$ 的子数组都同时包含 $0$ 和 $1$。
考虑任一下标 $i$，假设 $i$ 左边最近的 $0$ 到 $i$ 的距离是 $p_i$（$p_i = 0$ 说明 arr[i] == 0），$i$ 左边最近的 $1$ 到 $i$ 的距离是 $q_i$（$q_i = 0$ 说明 arr[i] == 1）。不妨假设下标 $i$ 是某个长度为 $(l + 1)$ 的子数组的右端点，因为这个子数组里既有 $0$ 又有 $1$，那么我们同时有 $p_i \le l$ 以及 $q_i \le l$。
由此可以设计出朴素的 DP 状态。设 $f(i, j, p, q)$ 表示考虑序列的前 $i$ 个元素中有 $j$ 个 $1$，且 $i$ 到最近的 $0$ 距离为 $p$，到最近的 $1$ 距离为 $q$ 的方案数。但这样状态总数为 $\mathcal{O}(n^2l^2)$，无论是 C 题还是 D 题都无法通过。
注意到元素要么是 $0$ 要么是 $1$，也就是说对于任意的 $i$，$p = 0$ 和 $q = 0$ 恰有一个成立。因此可以将 DP 状态压缩为 $f(i, j, t = 0/1, d)$ 表示考虑序列的前 $i$ 个元素中有 $j$ 个 $1$，且第 $i$ 个元素填的是 $t$，$i$ 到最近的另一种元素（即 $1 - t$）距离为 $d$ 的方案数。这样状态总数为 $\mathcal{O}(n^2l)$。
转移方程分为两部分。
f(i, j, 0, d) += f(i - 1, j, 0, d - 1)
f(i, j, 1, d) += f(i - 1, j - 1, 1, d - 1)
这一部分的含义是，让第 $i$ 个元素和第 $(i - 1)$ 个元素相同，那么到另一种元素的距离自然增加 $1$。
f(i, j, 0, 1) += f(i - 1, j, 1, *)
f(i, j, 1, 1) += f(i - 1, j - 1, 0, *)
这一部分的含义是，让第 $i$ 个元素和第 $(i - 1)$ 个元素不同，那么到另一种元素（也就是上一个元素）的距离就是 $1$。这里的星号通过维护前缀和即可 $\mathcal{O}(1)$ 计算。
初值就是枚举第一个元素填 $0$ 还是 $1$。对于第一个元素来说，另一种元素已经 $1$ 个位置没出现了，所以 $d = 1$，即 $f(1, 0, 0, 1) = f(1, 1, 1, 1) = 1$。
整体复杂度 $\mathcal{O}(n^2l)$，可以通过 C 题。
我们发现，DP 主要的运算复杂度来自转移方程的第一部分。第一部分的转移方程看起来很简单，好像只是把上一个位置所有 $(d - 1)$ 的 DP 值都照搬过来而已。由于 $d \le l$ 的限制，只是丢弃了 $f(i - 1, j, *, l)$ 的 DP 值。而 DP 方程的第二部分没有丢弃任何 DP 值，通过前缀和直接把所有情况照单全收。
这里其实在暗示我们：只要上个位置距离另一种元素的距离不到 $l$，那么当前位置无论填什么都是安全的。只有上个位置距离另一种元素的距离恰为 $l$ 时，当前位置必须填与上个位置不同的元素。也就是说：
（当前位置填元素 t 的方案数） = （上个位置的所有方案数） - （元素 1 - t 最近一次在 i - limit - 1 出现，从 i - limit 到 i 全部都是元素 t 的方案数）
设 $f(i, j, t = 0/1)$ 表示考虑序列的前 $i$ 个元素中有 $j$ 个 $1$，且第 $i$ 个元素填的是 $t$ 的方案数。“元素 $(1 - t)$ 最近一次在 $(i - l - 1)$ 出现，从 $(i - l)$ 到 $i$ 全部都是元素 $t$ 的方案数”怎么算呢？当然就是 $f(i - l - 1, j', 1 - t)$。这里 $j'$ 要看如果 $t = 0$ 那么 $j' = j$，否则如果 $t = 1$ 那么由于从 $(i - l)$ 到 $i$ 全部都是 $1$，则 $j' = j - l - 1$。
由此得到转移方程.
f(i, j, 0) = f(i - 1, j, 0) + f(i - 1, j, 1) - f(i - l - 1, j, 1)
f(i, j, 1) = f(i - 1, j - 1, 0) + f(i - 1, j - 1, 1) - f(i - l - 1, j - l - 1, 0)
整体复杂度 $\mathcal{O}(n^2)$，可以通过 D 题。
但是，实现过程中有一个初值的细节问题。当 $i = l + 1$ 时，我们要求 “元素 $(1 - t)$ 最近一次在下标 $0$ 出现的方案数”。空序列一定是合法的，所以有 $f(0, 0, 0) = f(0, 0, 1) = 1$。然而当 $i = 1$ 的时候，这样的初值设置会导致 $f(i - 1, j, 0) + f(i - 1, j, 1)$ 这部分的转移方程出现重复计算，所以我们直接继续设置初值 $f(1, 0, 0) = f(1, 1, 1) = 1$。
###c++
class Solution {
public:
int numberOfStableArrays(int zero, int one, int limit) {
const int MOD = 1e9 + 7;
int n = zero + one;
long long g[n + 1][one + 1][2];
memset(g, 0, sizeof(g));
g[0][0][0] = g[0][0][1] = g[1][0][0] = g[1][1][1] = 1;
auto update = [&](long long &x, long long y) {
x = (x + y) % MOD;
};
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= one; j++) {
update(g[i][j][0], g[i - 1][j][1] + g[i - 1][j][0]);
if (i > limit) update(g[i][j][0], MOD - g[i - 1 - limit][j][1]);
if (j > 0) update(g[i][j][1], g[i - 1][j - 1][0] + g[i - 1][j - 1][1]);
if (i > limit && j > limit) update(g[i][j][1], MOD - g[i - 1 - limit][j - 1 - limit][0]);
}
}
return (g[n][one][0] + g[n][one][1]) % MOD;
}
};
给你一个字符串数组 nums ，该数组由 n 个 互不相同 的二进制字符串组成，且每个字符串长度都是 n 。请你找出并返回一个长度为 n 且 没有出现 在 nums 中的二进制字符串。如果存在多种答案，只需返回 任意一个 即可。
示例 1：
输入：nums = ["01","10"] 输出："11" 解释："11" 没有出现在 nums 中。"00" 也是正确答案。
示例 2：
输入：nums = ["00","01"] 输出："11" 解释："11" 没有出现在 nums 中。"10" 也是正确答案。
示例 3：
输入：nums = ["111","011","001"] 输出："101" 解释："101" 没有出现在 nums 中。"000"、"010"、"100"、"110" 也是正确答案。
提示：
n == nums.length1 <= n <= 16nums[i].length == nnums[i] 为 '0' 或 '1'
nums 中的所有字符串 互不相同
第二道题。
给了咱几个二进制的字符串，要我们返回一个没有出现的等长二进制字符串。
想法比较简单，我们把出现的字符串都放进set里方便查找，然后遍历长度为n的二进制字符串，输出第一个没出现的即可。
因为遍历时要做二进制字符串的+1操作，涉及一点string的大数模拟，做过的应该都觉得蛮简单的。
才第二题，别想太多，写就完事了！
`
###c++
class Solution {
public:
int n;
string findDifferentBinaryString(vector<string>& nums) {
n = nums.size();
set<string> myhash; //字符串集合
for(auto s: nums) myhash.insert(s); //把每个字符串都放入set
string ans(n, '0');
while(myhash.find(ans) != myhash.end()) add(ans); //遍历到第一个找不到的字符串
return ans;
}
void add(string& s){
bool flag = true; //表示进位
for(int i = 0; i < n; ++i){
if(flag){
if(s[i] == '0'){ //0的进位处理
s[i] = '1';
flag = false;
}else s[i] = '0'; //1的进位处理
}else break; //没有进位，退出循环
}
}
};
只要和第i个串下标i的字符nums[i][i]不同，构造出来的串就和所有的串都不同。
只限于串数不超过串长的情况。
时间复杂度O(n)。
###cpp
class Solution {
public:
string findDifferentBinaryString(vector<string>& nums) {
string ans;
int n = nums.size();
for (int i = 0; i < n; i++) {
if (nums[i][i] == '0') {
ans += '1';
} else {
ans += '0';
}
}
return ans;
}
};
把 $\textit{nums}$ 中的字符串转成二进制整数，保存到一个哈希集合中。
枚举 $\textit{ans} = 0,1,2,\ldots$ 直到 $\textit{ans}$ 不在哈希集合中，即为答案。
方法二告诉我们，满足要求的答案是一定存在的。
class Solution:
def findDifferentBinaryString(self, nums: List[str]) -> str:
st = {int(s, 2) for s in nums}
ans = 0
while ans in st:
ans += 1
n = len(nums)
return f"{ans:0{n}b}"
class Solution {
public String findDifferentBinaryString(String[] nums) {
Set<Integer> set = new HashSet<>();
for (String s : nums) {
set.add(Integer.parseInt(s, 2));
}
int ans = 0;
while (set.contains(ans)) {
ans++;
}
String bin = Integer.toBinaryString(ans);
return "0".repeat(nums.length - bin.length()) + bin;
}
}
class Solution {
public:
string findDifferentBinaryString(vector<string>& nums) {
unordered_set<int> st;
for (auto& s : nums) {
st.insert(stoi(s, nullptr, 2));
}
int ans = 0;
while (st.contains(ans)) {
ans++;
}
int n = nums.size();
return bitset<32>(ans).to_string().substr(32 - n);
}
};
func findDifferentBinaryString(nums []string) string {
n := len(nums)
has := make(map[int]bool, n)
for _, s := range nums {
x, _ := strconv.ParseInt(s, 2, 64)
has[int(x)] = true
}
ans := 0
for has[ans] {
ans++
}
return fmt.Sprintf("%0*b", n, ans)
}
这个方法灵感来自数学家康托关于「实数是不可数无限」的证明。
例如 $\textit{nums} = [\texttt{111}, \texttt{011}, \texttt{000}]$。我们可以构造一个字符串 $\textit{ans}$，满足：
$\textit{ans} = \texttt{001}$ 和每个 $\textit{nums}[i]$ 都至少有一个字符不同，满足题目要求。
一般地，令 $\textit{ans}[i] = \textit{nums}[i][i]\oplus 1$，即可满足要求。其中 $\oplus$ 是异或运算。
class Solution:
def findDifferentBinaryString(self, nums: List[str]) -> str:
ans = [''] * len(nums)
for i, s in enumerate(nums):
ans[i] = '1' if s[i] == '0' else '0'
return ''.join(ans)
class Solution {
public String findDifferentBinaryString(String[] nums) {
int n = nums.length;
char[] ans = new char[n];
for (int i = 0; i < n; i++) {
ans[i] = (char) (nums[i].charAt(i) ^ 1);
}
return new String(ans);
}
}
class Solution {
public:
string findDifferentBinaryString(vector<string>& nums) {
int n = nums.size();
string ans(n, 0);
for (int i = 0; i < n; i++) {
ans[i] = nums[i][i] ^ 1;
}
return ans;
}
};
func findDifferentBinaryString(nums []string) string {
ans := make([]byte, len(nums))
for i, s := range nums {
ans[i] = s[i] ^ 1
}
return string(ans)
}
欢迎关注 B站@灵茶山艾府
注意 $s$ 不含前导零，那么只含一段连续 $\texttt{1}$ 的 $s$ 只有两种情况：
如果 $s$ 包含多段连续的 $\texttt{1}$，比如示例 1 的 $s = \texttt{1001}$，在 $\texttt{0}$ 的后面还有 $\texttt{1}$。所以检查 $s$ 是否包含 $\texttt{01}$ 即可。
注：只有一个 $\texttt{1}$ 也算一段连续的 $\texttt{1}$。
###py
class Solution:
def checkOnesSegment(self, s: str) -> bool:
return "01" not in s
###java
class Solution {
public boolean checkOnesSegment(String s) {
return !s.contains("01");
}
}
###cpp
class Solution {
public:
bool checkOnesSegment(string s) {
return s.find("01") == string::npos;
}
};
###c
bool checkOnesSegment(char* s) {
return strstr(s, "01") == NULL;
}
###go
func checkOnesSegment(s string) bool {
return !strings.Contains(s, "01")
}
###js
var checkOnesSegment = function(s) {
return !s.includes("01");
};
###rust
impl Solution {
pub fn check_ones_segment(s: String) -> bool {
!s.contains("01")
}
}
欢迎关注 B站@灵茶山艾府
给你一个二进制字符串 s ，该字符串 不含前导零 。
如果 s 包含 零个或一个由连续的 '1' 组成的字段 ，返回 true 。否则，返回 false 。
示例 1：
输入：s = "1001"
输出：false
解释：由连续若干个 '1' 组成的字段数量为 2，返回 false
示例 2：
输入：s = "110" 输出：true
提示：
1 <= s.length <= 100s[i] 为 '0' 或 '1'
s[0] 为 '1'
