DeepSeek LeetCode 3336. 最大公约数相等的子序列数量 Java实现

根据搜索结果，LeetCode 3336 有两种主流解法，这里提供对应的 Java 实现及说明。

方法一：多维 DP（记忆化搜索）

这种解法最直观，用“选或不选”的思维为每个元素做三种决策。

```java
class Solution {
private static final int MOD = 1_000_000_007;
private int[][][] memo;
private int[] nums;

public int subsequencePairCount(int[] nums) {
int n = nums.length;
this.nums = nums;
// 值域上限 200，多开一位存0（代表空序列的GCD）
memo = new int[n][201][201];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 201; j++) {
Arrays.fill(memo[i][j], -1);
}
}
// 从第一个元素开始，两个子序列初始GCD均为0
// 最后 -1 是为了排除两个子序列同时为空的情况
return (dfs(0, 0, 0) - 1 + MOD) % MOD;
}

private int dfs(int i, int g1, int g2) {
if (i == nums.length) {
// 两个子序列都必须非空且GCD相等
return (g1 != 0 && g2 != 0 && g1 == g2) ? 1 : 0;
}
if (memo[i][g1][g2] != -1) return memo[i][g1][g2];

int x = nums[i];
// 三种决策：不选 / 放入第一个 / 放入第二个
long skip = dfs(i + 1, g1, g2);
long put1 = dfs(i + 1, gcd(g1, x), g2);
long put2 = dfs(i + 1, g1, gcd(g2, x));

long ans = (skip + put1 + put2) % MOD;
memo[i][g1][g2] = (int) ans;
return memo[i][g1][g2];
}

private int gcd(int a, int b) {
while (b != 0) {
int tmp = a % b;
a = b;
b = tmp;
}
return a;
}
}
```

方法二：倍数容斥 AC

利用值域（≤200）和容斥原理优化计数，性能更优。

```java
class Solution {
private static final int MOD = 1_000_000_007;
private static final int MX = 201;
private static int[][] lcms = new int[MX][MX];
private static long[] pow2 = new long[MX];
private static long[] pow3 = new long[MX];
private static int[] mu = new int[MX];

static {
// 预处理：LCM、2/3的幂、莫比乌斯函数
for (int i = 1; i < MX; i++) {
for (int j = 1; j < MX; j++) {
lcms[i][j] = lcm(i, j);
}
}
pow2[0] = pow3[0] = 1;
for (int i = 1; i < MX; i++) {
pow2[i] = pow2[i-1] * 2 % MOD;
pow3[i] = pow3[i-1] * 3 % MOD;
}
mu[1] = 1;
for (int i = 1; i < MX; i++) {
for (int j = i*2; j < MX; j += i) {
mu[j] -= mu[i];
}
}
}

public int subsequencePairCount(int[] nums) {
int m = Arrays.stream(nums).max().orElse(0);
int[] cnt = new int[m+1];
for (int x : nums) cnt[x]++;

// cnt[i]：nums中i的倍数的个数
for (int i = 1; i <= m; i++) {
for (int j = i*2; j <= m; j += i) {
cnt[i] += cnt[j];
}
}

// f[g1][g2]：粗略计数
long[][] f = new long[m+1][m+1];
for (int g1 = 1; g1 <= m; g1++) {
for (int g2 = 1; g2 <= m; g2++) {
int l = lcms[g1][g2];
int c = (l <= m) ? cnt[l] : 0;
int c1 = cnt[g1], c2 = cnt[g2];
long val = pow3[c] * pow2[c1 + c2 - 2*c] % MOD;
val = (val - pow2[c1] - pow2[c2] + 1) % MOD;
f[g1][g2] = (val + MOD) % MOD;
}
}

// 倍数容斥求精确答案
long ans = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= m/i; j++) {
for (int k = 1; k <= m/i; k++) {
ans += (long) mu[j] * mu[k] * f[j*i][k*i];
ans %= MOD;
}
}
}
return (int) ((ans % MOD + MOD) % MOD);
}

private static int gcd(int a, int b) {
while (b != 0) { int t = a % b; a = b; b = t; }
return a;
}
private static int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
}
```

复杂度对比

· 多维 DP：O(n * 200 * 200) 时间与空间。
· 倍数容斥：O(m^3) 时间（m≤200），O(m^2) 空间。