这是 LeetCode 3336. 最大公约数相等的子序列数量 的 Python3 实现。

---

题目概述

给定整数数组 `nums`，求满足以下条件的非空子序列对 `(seq1, seq2)` 的数量：
- `seq1` 和 `seq2` 不相交（没有共同下标）
- `gcd(seq1) == gcd(seq2)`

结果对 10^9 + 7 取模。

---

解题思路

三维动态规划（压缩为字典）

定义 `dp[(g1, g2)]` 为：处理完部分元素后，`seq1` 的 GCD 为 `g1`、`seq2` 的 GCD 为 `g2` 的方案数。其中 `g1=0` 或 `g2=0` 表示对应子序列为空。

对于每个元素 `num`，有三种选择：
1. 放入 `seq1`：`g1` 更新为 `gcd(g1, num)`（若 `g1=0` 则变为 `num`）
2. 放入 `seq2`：`g2` 更新为 `gcd(g2, num)`（若 `g2=0` 则变为 `num`）
3. 不放入任何子序列：状态不变

最终答案为所有 `g1 == g2 != 0` 的状态之和。

> 由于 `nums[i] ≤ 200`，GCD 的可能取值有限，使用 `defaultdict` 可以有效压缩状态空间，避免遍历大量无效状态。

---

Python3 代码

```python
from math import gcd
from collections import defaultdict
from typing import List

MOD = 10 ** 9 + 7

class Solution:
    def subsequencePairCount(self, nums: List[int]) -> int:
        """
        动态规划：
        dp[(g1, g2)] 表示已处理元素中，seq1的gcd为g1，seq2的gcd为g2的方案数。
        g1=0 或 g2=0 表示对应子序列为空。
        
        对于每个num，有三种选择：
        1. 放入seq1：更新g1 = gcd(g1, num)（若g1=0则变为num）
        2. 放入seq2：更新g2 = gcd(g2, num)（若g2=0则变为num）
        3. 不放入任何子序列：状态不变
        
        最终答案为所有 g1 == g2 != 0 的状态之和。
        """
        dp = defaultdict(int)
        dp[(0, 0)] = 1  # 初始状态：两个子序列都为空
        
        for num in nums:
            # 遍历当前所有状态，避免迭代时修改字典
            items = list(dp.items())
            for (g1, g2), cnt in items:
                # 选择1：num放入seq1
                ng1 = num if g1 == 0 else gcd(g1, num)
                dp[(ng1, g2)] = (dp[(ng1, g2)] + cnt) % MOD
                
                # 选择2：num放入seq2
                ng2 = num if g2 == 0 else gcd(g2, num)
                dp[(g1, ng2)] = (dp[(g1, ng2)] + cnt) % MOD
                
                # 选择3：num不放入任何子序列（状态已保留，无需操作）
        
        ans = 0
        for (g1, g2), cnt in dp.items():
            if g1 != 0 and g1 == g2:
                ans = (ans + cnt) % MOD
        return ans
```

---

复杂度分析

项目    复杂度    说明    
时间    O(N \cdot S)    N \leq 200 为数组长度，S 为状态数（实际运行中由于 GCD 取值有限，状态数远小于理论上限）    
空间    O(S)    使用 `defaultdict` 存储有效状态    

已通过全部示例验证：
- `nums = [1,2,3,4]` → 10
- `nums = [10,20,30]` → 2
- `nums = [1,1,1,1]` → 50