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

这是 LeetCode 3336. 最大公约数相等的子序列数量 的 Python3 实现。---题目概述给定整数数组 nums求满足以下条件的非空子序列对 (seq1, seq2) 的数量- seq1 和 seq2 不相交没有共同下标- gcd(seq1) gcd(seq2)结果对 10^9 7 取模。---解题思路三维动态规划压缩为字典定义 dp[(g1, g2)] 为处理完部分元素后seq1 的 GCD 为 g1、seq2 的 GCD 为 g2 的方案数。其中 g10 或 g20 表示对应子序列为空。对于每个元素 num有三种选择1. 放入 seq1g1 更新为 gcd(g1, num)若 g10 则变为 num2. 放入 seq2g2 更新为 gcd(g2, num)若 g20 则变为 num3. 不放入任何子序列状态不变最终答案为所有 g1 g2 ! 0 的状态之和。 由于 nums[i] ≤ 200GCD 的可能取值有限使用 defaultdict 可以有效压缩状态空间避免遍历大量无效状态。---Python3 代码pythonfrom math import gcdfrom collections import defaultdictfrom typing import ListMOD 10 ** 9 7class Solution:def subsequencePairCount(self, nums: List[int]) - int:动态规划dp[(g1, g2)] 表示已处理元素中seq1的gcd为g1seq2的gcd为g2的方案数。g10 或 g20 表示对应子序列为空。对于每个num有三种选择1. 放入seq1更新g1 gcd(g1, num)若g10则变为num2. 放入seq2更新g2 gcd(g2, num)若g20则变为num3. 不放入任何子序列状态不变最终答案为所有 g1 g2 ! 0 的状态之和。dp defaultdict(int)dp[(0, 0)] 1 # 初始状态两个子序列都为空for num in nums:# 遍历当前所有状态避免迭代时修改字典items list(dp.items())for (g1, g2), cnt in items:# 选择1num放入seq1ng1 num if g1 0 else gcd(g1, num)dp[(ng1, g2)] (dp[(ng1, g2)] cnt) % MOD# 选择2num放入seq2ng2 num if g2 0 else gcd(g2, num)dp[(g1, ng2)] (dp[(g1, ng2)] cnt) % MOD# 选择3num不放入任何子序列状态已保留无需操作ans 0for (g1, g2), cnt in dp.items():if g1 ! 0 and g1 g2:ans (ans cnt) % MODreturn 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