Hard

题目描述

给定一个整数数组 nums。

你的任务是找到满足以下条件的非空子序列对 (seq1, seq2) 的数量：

  • 子序列 seq1 和 seq2 是不相交的，即它们之间没有共同的 nums 索引。
  • seq1 元素的最大公约数等于 seq2 元素的最大公约数。

返回此类对的总数。

由于答案可能非常大，请返回对 10^9 + 7 取模的结果。

示例 1：

输入：nums = [1,2,3,4]
输出：10

示例 2：

输入：nums = [10,20,30]
输出：2

示例 3：

输入：nums = [1,1,1,1]
输出：50

约束条件：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 200

提示：

  • 使用动态规划存储到索引 i 为止，GCD 为 g1 和 g2 的子序列数量。

解题思路

这道题目需要我们找到两个不相交的子序列，使得它们的最大公约数相等。

核心思路：

  1. 动态规划状态设计：使用三维DP，dp[i][g1][g2] 表示考虑前 i 个元素时，第一个子序列GCD为 g1，第二个子序列GCD为 g2 的方案数。

  2. 状态转移：对于每个元素 nums[i]，有三种选择：

    • 不选择该元素：dp[i+1][g1][g2] += dp[i][g1][g2]
    • 加入第一个子序列：dp[i+1][gcd(g1, nums[i])][g2] += dp[i][g1][g2]
    • 加入第二个子序列：dp[i+1][g1][gcd(g2, nums[i])] += dp[i][g1][g2]

  3. 初始状态：dp[0][0][0] = 1，表示没有选择任何元素时有一种方案（空方案）。

  4. 答案统计：遍历所有可能的GCD值 g，累加 dp[n][g][g] 的值。

  5. 优化技巧：

    • 由于数组元素最大为200，所以GCD最大也是200
    • 使用滚动数组可以优化空间复杂度
    • 预计算GCD值避免重复计算

这个方法的时间复杂度是 O(n × max_val²)，空间复杂度是 O(max_val²)，在给定约束下完全可行。

代码实现

class Solution {
public:
    int subsequencePairCount(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        int n = nums.size();
        int maxVal = 200;
        
        // dp[g1][g2] = number of ways with gcd g1 and g2
        vector<vector<long long>> dp(maxVal + 1, vector<long long>(maxVal + 1, 0));
        vector<vector<long long>> newDp(maxVal + 1, vector<long long>(maxVal + 1, 0));
        
        dp[0][0] = 1; // empty subsequences
        
        for (int num : nums) {
            // Reset newDp
            for (int i = 0; i <= maxVal; i++) {
                for (int j = 0; j <= maxVal; j++) {
                    newDp[i][j] = dp[i][j]; // don't take current number
                }
            }
            
            for (int g1 = 0; g1 <= maxVal; g1++) {
                for (int g2 = 0; g2 <= maxVal; g2++) {
                    if (dp[g1][g2] == 0) continue;
                    
                    // Add to first subsequence
                    int newG1 = (g1 == 0) ? num : __gcd(g1, num);
                    newDp[newG1][g2] = (newDp[newG1][g2] + dp[g1][g2]) % MOD;
                    
                    // Add to second subsequence
                    int newG2 = (g2 == 0) ? num : __gcd(g2, num);
                    newDp[g1][newG2] = (newDp[g1][newG2] + dp[g1][g2]) % MOD;
                }
            }
            
            dp = newDp;
        }
        
        long long result = 0;
        for (int g = 1; g <= maxVal; g++) {
            result = (result + dp[g][g]) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def subsequencePairCount(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        max_val = 200
        
        # dp[g1][g2] = number of ways with gcd g1 and g2
        dp = [[0] * (max_val + 1) for _ in range(max_val + 1)]
        dp[0][0] = 1  # empty subsequences
        
        def gcd(a, b):
            while b:
                a, b = b, a % b
            return a
        
        for num in nums:
            new_dp = [row[:] for row in dp]  # copy current state
            
            for g1 in range(max_val + 1):
                for g2 in range(max_val + 1):
                    if dp[g1][g2] == 0:
                        continue
                    
                    # Add to first subsequence
                    new_g1 = num if g1 == 0 else gcd(g1, num)
                    new_dp[new_g1][g2] = (new_dp[new_g1][g2] + dp[g1][g2]) % MOD
                    
                    # Add to second subsequence
                    new_g2 = num if g2 == 0 else gcd(g2, num)
                    new_dp[g1][new_g2] = (new_dp[g1][new_g2] + dp[g1][g2]) % MOD
            
            dp = new_dp
        
        result = 0
        for g in range(1, max_val + 1):
            result = (result + dp[g][g]) % MOD
        
        return result

public class Solution {
    public int SubsequencePairCount(int[] nums) {
        const int MOD = 1000000007;
        int maxVal = 200;
        
        // dp[g1][g2] = number of ways with gcd g1 and g2
        long[,] dp = new long[maxVal + 1, maxVal + 1];
        long[,] newDp = new long[maxVal + 1, maxVal + 1];
        
        dp[0, 0] = 1; // empty subsequences
        
        foreach (int num in nums) {
            // Copy current state
            for (int i = 0; i <= maxVal; i++) {
                for (int j = 0; j <= maxVal; j++) {
                    newDp[i, j] = dp[i, j];
                }
            }
            
            for (int g1 = 0; g1 <= maxVal; g1++) {
                for (int g2 = 0; g2 <= maxVal; g2++) {
                    if (dp[g1, g2] == 0) continue;
                    
                    // Add to first subsequence
                    int newG1 = (g1 == 0) ? num : GCD(g1, num);
                    newDp[newG1, g2] = (newDp[newG1, g2] + dp[g1, g2]) % MOD;
                    
                    // Add to second subsequence
                    int newG2 = (g2 == 0) ? num : GCD(g2, num);
                    newDp[g1, newG2] = (newDp[g1, newG2] + dp[g1, g2]) % MOD;
                }
            }
            
            dp = newDp;
            newDp = new long[maxVal + 1, maxVal + 1];
        }
        
        long result = 0;
        for (int g = 1; g <= maxVal; g++) {
            result = (result + dp[g, g]) % MOD;
        }
        
        return (int)result;
    }
    
    private int GCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

var subsequencePairCount = function(nums) {
    const MOD = 1000000007;
    const n = nums.length;
    
    function gcd(a, b) {
        return b === 0 ? a : gcd(b, a % b);
    }
    
    // dp[mask][g] = number of ways to choose subsequence represented by mask with GCD g
    const dp = new Map();
    
    // Generate all possible subsequences and their GCDs
    for (let mask = 1; mask < (1 << n); mask++) {
        let g = 0;
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                g = g === 0 ? nums[i] : gcd(g, nums[i]);
            }
        }
        
        if (!dp.has(g)) dp.set(g, new Map());
        if (!dp.get(g).has(mask)) dp.get(g).set(mask, 0);
        dp.get(g).set(mask, dp.get(g).get(mask) + 1);
    }
    
    let result = 0;
    
    // For each possible GCD value
    for (let [g, masks] of dp) {
        const maskList = Array.from(masks.keys());
        
        // Count pairs of disjoint subsequences with same GCD
        for (let i = 0; i < maskList.length; i++) {
            for (let j = i; j < maskList.length; j++) {
                const mask1 = maskList[i];
                const mask2 = maskList[j];
                
                // Check if masks are disjoint
                if ((mask1 & mask2) === 0) {
                    if (i === j) {
                        result = (result + 1) % MOD;
                    } else {
                        result = (result + 2) % MOD;
                    }
                }
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × V²) 其中 n 是数组长度，V 是数组中的最大值（200）。对于每个元素，需要遍历所有可能的 GCD 对
空间复杂度O(V²) 存储动态规划状态，需要一个二维数组来记录所有可能的 GCD 组合

相关题目