LC 3336. 最大公约数相等的子序列数量
https://leetcode.cn/problems/find-the-number-of-subsequences-with-equal-gcd/description/
初看起来不太好做，后来想到可以映射到DP上： `dp[i][g1][g2]` 表示处理到i个元素的时候，左边是g1, 右边是g2的子序列组合有多少个。时间复杂度就是O(n * G1 * G2). 空间复杂度上可以用滚动数组。
class Solution:
def subsequencePairCount(self, nums: List[int]) -> int:
M = max(nums) + 1
dp = [[0] * M for _ in range(M)]
dp[0][0] = 1
def gcd(a, b):
while b:
a, b = b, a % b
return a
MOD = 10 ** 9 + 7
for i in range(len(nums)):
ndp = [[0] * M for _ in range(M)]
for g1 in range(M):
for g2 in range(M):
if dp[g1][g2] == 0: continue
ndp[g1][g2] += dp[g1][g2]
# nums[i] -> g1 or g2
g = gcd(g1, nums[i])
ndp[g][g2] += dp[g1][g2]
g = gcd(g2, nums[i])
ndp[g1][g] += dp[g1][g2]
for g1 in range(M):
for g2 in range(M):
dp[g1][g2] %= MOD
dp = ndp
ans = 0
for g in range(1, M):
ans += dp[g][g]
return ans % MOD