class Solution {
public:
int subsequencePairCount(vector<int>& nums) {
}
};
3336. 最大公约数相等的子序列数量
给你一个整数数组 nums。
请你统计所有满足一下条件的 非空 子序列对 (seq1, seq2) 的数量：
seq1 和 seq2 不相交，意味着 nums 中 不存在 同时出现在两个序列中的下标。seq1 元素的 GCD 等于 seq2 元素的 GCD。返回满足条件的子序列对的总数。
由于答案可能非常大，请返回其对 109 + 7 取余 的结果。
gcd(a, b) 表示 a 和 b 的 最大公约数。
子序列 是指可以从另一个数组中删除某些或不删除元素得到的数组，并且删除操作不改变其余元素的顺序。
示例 1：
输入： nums = [1,2,3,4]
输出： 10
解释：
元素 GCD 等于 1 的子序列对有：
([1, 2, 3, 4], [1, 2, 3, 4])([1, 2, 3, 4], [1, 2, 3, 4])([1, 2, 3, 4], [1, 2, 3, 4])([1, 2, 3, 4], [1, 2, 3, 4])([1, 2, 3, 4], [1, 2, 3, 4])([1, 2, 3, 4], [1, 2, 3, 4])([1, 2, 3, 4], [1, 2, 3, 4])([1, 2, 3, 4], [1, 2, 3, 4])([1, 2, 3, 4], [1, 2, 3, 4])([1, 2, 3, 4], [1, 2, 3, 4])示例 2：
输入： nums = [10,20,30]
输出： 2
解释：
元素 GCD 等于 10 的子序列对有：
([10, 20, 30], [10, 20, 30])([10, 20, 30], [10, 20, 30])示例 3：
输入： nums = [1,1,1,1]
输出： 50
提示：
1 <= nums.length <= 2001 <= nums[i] <= 200相似题目
原站题解
java 解法, 执行用时: 1049 ms, 内存消耗: 101.9 MB, 提交时间: 2024-11-09 00:12:01
class Solution {
public int subsequencePairCount(int[] nums) {
final int MOD = 1_000_000_007;
int n = nums.length;
int m = 0;
for (int x : nums) {
m = Math.max(m, x);
}
int[][][] f = new int[n + 1][m + 1][m + 1];
for (int j = 1; j <= m; j++) {
f[0][j][j] = 1;
}
for (int i = 0; i < n; i++) {
int x = nums[i];
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= m; k++) {
f[i + 1][j][k] = (int) (((long) f[i][j][k] + f[i][gcd(j, x)][k] + f[i][j][gcd(k, x)]) % MOD);
}
}
}
return f[n][0][0];
}
private int gcd(int a, int b) {
while (a != 0) {
int tmp = a;
a = b % a;
b = tmp;
}
return b;
}
}
golang 解法, 执行用时: 1354 ms, 内存消耗: 127.8 MB, 提交时间: 2024-11-09 00:11:44
func subsequencePairCount(nums []int) int {
const mod = 1_000_000_007
n := len(nums)
m := slices.Max(nums)
f := make([][][]int, n+1)
for i := range f {
f[i] = make([][]int, m+1)
for j := range f[i] {
f[i][j] = make([]int, m+1)
}
}
for j := 1; j <= m; j++ {
f[0][j][j] = 1
}
for i, x := range nums {
for j := 0; j <= m; j++ {
for k := 0; k <= m; k++ {
f[i+1][j][k] = (f[i][j][k] + f[i][gcd(j, x)][k] + f[i][j][gcd(k, x)]) % mod
}
}
}
return f[n][0][0]
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
python3 解法, 执行用时: 219 ms, 内存消耗: 18.5 MB, 提交时间: 2024-11-09 00:11:24
MOD = 1_000_000_007
MX = 201
lcms = [[lcm(i, j) for j in range(MX)] for i in range(MX)]
pow2 = [1] * MX
pow3 = [1] * MX
for i in range(1, MX):
pow2[i] = pow2[i - 1] * 2 % MOD
pow3[i] = pow3[i - 1] * 3 % MOD
mu = [0] * MX
mu[1] = 1
for i in range(1, MX):
for j in range(i * 2, MX, i):
mu[j] -= mu[i]
class Solution:
def subsequencePairCount(self, nums: List[int]) -> int:
m = max(nums)
# cnt[i] 表示 nums 中的 i 的倍数的个数
cnt = [0] * (m + 1)
for x in nums:
cnt[x] += 1
for i in range(1, m + 1):
for j in range(i * 2, m + 1, i):
cnt[i] += cnt[j] # 统计 i 的倍数的个数
f = [[0] * (m + 1) for _ in range(m + 1)]
for g1 in range(1, m + 1):
for g2 in range(1, m + 1):
l = lcms[g1][g2]
c = cnt[l] if l <= m else 0
c1, c2 = cnt[g1], cnt[g2]
f[g1][g2] = (pow3[c] * pow2[c1 + c2 - c * 2] - pow2[c1] - pow2[c2] + 1) % MOD
# 倍数容斥
return sum(mu[j] * mu[k] * f[j * i][k * i]
for i in range(1, m + 1)
for j in range(1, m // i + 1)
for k in range(1, m // i + 1)) % MOD
python3 解法, 执行用时: 9788 ms, 内存消耗: 322.8 MB, 提交时间: 2024-11-09 00:11:12
class Solution:
def subsequencePairCount1(self, nums: List[int]) -> int:
MOD = 1_000_000_007
@cache # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
def dfs(i: int, j: int, k: int) -> int:
if i < 0:
return 1 if j == k else 0
return (dfs(i - 1, j, k) + dfs(i - 1, gcd(j, nums[i]), k) + dfs(i - 1, j, gcd(k, nums[i]))) % MOD
return (dfs(len(nums) - 1, 0, 0) - 1) % MOD
# 递推
def subsequencePairCount(self, nums: List[int]) -> int:
MOD = 1_000_000_007
n = len(nums)
m = max(nums)
f = [[[0] * (m + 1) for _ in range(m + 1)] for _ in range(n + 1)]
for j in range(1, m + 1):
f[0][j][j] = 1
for i, x in enumerate(nums):
for j in range(m + 1):
for k in range(m + 1):
f[i + 1][j][k] = (f[i][j][k] + f[i][gcd(j, x)][k] + f[i][j][gcd(k, x)]) % MOD
return f[n][0][0]