class Solution {
public:
int countOfPairs(vector<int>& nums) {
}
};
100396. 单调数组对的数目 II
给你一个长度为 n 的 正 整数数组 nums 。
如果两个 非负 整数数组 (arr1, arr2) 满足以下条件，我们称它们是 单调 数组对：
n 。arr1 是单调 非递减 的，换句话说 arr1[0] <= arr1[1] <= ... <= arr1[n - 1] 。arr2 是单调 非递增 的，换句话说 arr2[0] >= arr2[1] >= ... >= arr2[n - 1] 。0 <= i <= n - 1 都有 arr1[i] + arr2[i] == nums[i] 。请你返回所有 单调 数组对的数目。
由于答案可能很大，请你将它对 109 + 7 取余 后返回。
示例 1：
输入：nums = [2,3,2]
输出：4
解释：
单调数组对包括：
([0, 1, 1], [2, 2, 1])([0, 1, 2], [2, 2, 0])([0, 2, 2], [2, 1, 0])([1, 2, 2], [1, 1, 0])示例 2：
输入：nums = [5,5,5,5]
输出：126
提示：
1 <= n == nums.length <= 20001 <= nums[i] <= 1000原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 4.3 MB, 提交时间: 2024-08-12 09:54:50
const mod = 1_000_000_007
const mx = 3001 // MAX_N + MAX_M = 2000 + 1000 = 3000
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 countOfPairs(nums []int) int {
n := len(nums)
m := nums[n-1]
for i := 1; i < n; i++ {
m -= max(nums[i]-nums[i-1], 0)
if m < 0 {
return 0
}
}
return comb(m+n, n)
}
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
}
java 解法, 执行用时: 103 ms, 内存消耗: 44.1 MB, 提交时间: 2024-08-12 09:54:26
class Solution {
public int countOfPairs1(int[] nums) {
final int MOD = 1_000_000_007;
int n = nums.length;
int m = Arrays.stream(nums).max().getAsInt();
long[][] f = new long[n][m + 1];
long[] s = new long[m + 1];
Arrays.fill(f[0], 0, nums[0] + 1, 1);
for (int i = 1; i < n; i++) {
s[0] = f[i - 1][0];
for (int k = 1; k <= m; k++) {
s[k] = (s[k - 1] + f[i - 1][k]) % MOD; // f[i-1] 的前缀和
}
for (int j = 0; j <= nums[i]; j++) {
int maxK = j + Math.min(nums[i - 1] - nums[i], 0);
f[i][j] = maxK >= 0 ? s[maxK] % MOD : 0;
}
}
return (int) (Arrays.stream(f[n - 1], 0, nums[n - 1] + 1).sum() % MOD);
}
public int countOfPairs2(int[] nums) {
final int MOD = 1_000_000_007;
int n = nums.length;
int m = nums[n - 1];
int[] f = new int[m + 1];
Arrays.fill(f, 0, Math.min(nums[0], m) + 1, 1);
for (int i = 1; i < n; i++) {
for (int j = 1; j <= m; j++) {
f[j] = (f[j] + f[j - 1]) % MOD; // 计算前缀和
}
int j0 = Math.max(nums[i] - nums[i - 1], 0);
for (int j = Math.min(nums[i], m); j >= j0; j--) {
f[j] = f[j - j0];
}
Arrays.fill(f, 0, Math.min(j0, m + 1), 0);
}
long ans = 0;
for (int v : f) {
ans += v;
}
return (int) (ans % MOD);
}
public int countOfPairs(int[] nums) {
final int MOD = 1_000_000_007;
int n = nums.length;
int m = nums[n - 1];
int[] f = new int[m + 1];
Arrays.fill(f, 0, Math.min(nums[0], m) + 1, 1);
for (int i = 1; i < n; i++) {
int j0 = Math.max(nums[i] - nums[i - 1], 0);
int m2 = Math.min(nums[i], m);
if (j0 > m2) {
return 0;
}
for (int j = 1; j <= m2 - j0; j++) {
f[j] = (f[j] + f[j - 1]) % MOD; // 计算前缀和
}
System.arraycopy(f, 0, f, j0, m2 - j0 + 1);
Arrays.fill(f, 0, j0, 0);
}
long ans = 0;
for (int v : f) {
ans += v;
}
return (int) (ans % MOD);
}
}
cpp 解法, 执行用时: 11 ms, 内存消耗: 30.5 MB, 提交时间: 2024-08-12 09:51:32
const int MOD = 1'000'000'007;
const int MX = 3001; // MAX_N + MAX_M = 2000 + 1000 = 3000
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 countOfPairs(vector<int>& nums) {
int n = nums.size(), m = nums.back();
for (int i = 1; i < n; i++) {
m -= max(nums[i] - nums[i - 1], 0);
if (m < 0) {
return 0;
}
}
return comb(m + n, n);
}
};
python3 解法, 执行用时: 48 ms, 内存消耗: 16.8 MB, 提交时间: 2024-08-12 09:50:51
# 前缀和优化dp
class Solution:
def countOfPairs1(self, nums: List[int]) -> int:
MOD = 1_000_000_007
n = len(nums)
m = max(nums)
f = [[0] * (m + 1) for _ in range(n)]
for j in range(nums[0] + 1):
f[0][j] = 1
for i in range(1, n):
s = list(accumulate(f[i - 1])) # f[i-1] 的前缀和
for j in range(nums[i] + 1):
max_k = j + min(nums[i - 1] - nums[i], 0)
f[i][j] = s[max_k] % MOD if max_k >= 0 else 0
return sum(f[-1][:nums[-1] + 1]) % MOD
# 空间优化
def countOfPairs2(self, nums: List[int]) -> int:
MOD = 1_000_000_007
m = nums[-1]
f = [0] * (m + 1)
for j in range(min(nums[0], m) + 1):
f[j] = 1
for pre, cur in pairwise(nums):
for j in range(1, m + 1):
f[j] += f[j - 1] # 计算前缀和
j0 = max(cur - pre, 0)
for j in range(min(cur, m), j0 - 1, -1):
f[j] = f[j - j0] % MOD
for j in range(min(j0, m + 1)):
f[j] = 0
return sum(f) % MOD
# 进一步优化
def countOfPairs3(self, nums: List[int]) -> int:
MOD = 1_000_000_007
m = nums[-1]
f = [0] * (m + 1)
for j in range(min(nums[0], m) + 1):
f[j] = 1
for pre, cur in pairwise(nums):
j0 = max(cur - pre, 0)
m2 = min(cur, m)
if j0 > m2:
return 0
for j in range(1, m2 - j0 + 1):
f[j] = (f[j] + f[j - 1]) % MOD # 计算前缀和
f[j0: m2 + 1] = f[:m2 - j0 + 1]
f[:j0] = [0] * j0
return sum(f) % MOD
# 组合数学
def countOfPairs(self, nums: List[int]) -> int:
MOD = 1_000_000_007
m = nums[-1]
for x, y in pairwise(nums):
m -= max(y - x, 0)
return comb(m + len(nums), m) % MOD if m >= 0 else 0