题目描述

给你一个整数数组 nums。

请你统计所有满足一下条件的 非空 子序列 对 (seq1, seq2) 的数量：

子序列 seq1 和 seq2 不相交，意味着 nums 中 不存在 同时出现在两个序列中的下标。

seq1 元素的 GCD 等于 seq2 元素的 GCD。

返回满足条件的子序列对的总数。

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

样例

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

输出： 10

解释：

元素 GCD 等于 1 的子序列对有：

([1, 2, 3, 4], [1, 2, 3, 4])
([1, 2, 3, 4], [1, 2, 3, 4])
([1, 2, 3, 4], [1, 2, 3, 4])
([1, 2, 3, 4], [1, 2, 3, 4])
([1, 2, 3, 4], [1, 2, 3, 4])
([1, 2, 3, 4], [1, 2, 3, 4])
([1, 2, 3, 4], [1, 2, 3, 4])
([1, 2, 3, 4], [1, 2, 3, 4])
([1, 2, 3, 4], [1, 2, 3, 4])
([1, 2, 3, 4], [1, 2, 3, 4])

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

输出： 2

解释：

元素 GCD 等于 10 的子序列对有：

([10, 20, 30], [10, 20, 30])
([10, 20, 30], [10, 20, 30])
示例 3：

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

输出： 50

限制

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

算法

(动态规划) $O(nU^2)$

1. 设状态 $f(i, j, k)$ 表示遍历了前 $i$ 个字符，第一个子序列的最大公约数为 $j$，且第二个子序列的最大公约数为 $k$ 的方案数。
2. 初始时，$f(0, 0, 0) = 1$，其余待定。
3. 转移时，对于当前状态 $f(i, j, k)$ 和数字 $x$，转移 $f(i + 1, j, k) = f(i, j, k)$，$f(i + 1, gcd(j, x), k) = f(i + 1, gcd(j, x), k) + f(i, j, k)$，$f(i + 1, j, gcd(k, x)) = f(i + 1, j, gcd(k, x)) + f(i, j, k)$。
4. 最终答案为 $\sum f(n, i, i)$。

时间复杂度

• 预处理 GCD 数组的时间复杂度为 $O(U^2)$。其中 $U$ 为最大的数字。
• 动态规划的状态数为 $O(nU^2)$，转移时间为常数。
• 故总时间复杂度为 $O(nU^2)$。

空间复杂度

• 可以通过滚动数组优化动态规划第一维的状态表示。
• 需要 $O(U^2)$ 的额外空间存储预处理的 GCD 数组和动态规划的状态。

C++ 代码

const int N = 201;

int g[N][N];

auto init = []{
    for (int x = 0; x < N; x++)
        for (int y = 0; y < N; y++)
            g[x][y] = gcd(x, y);

    return 0;
}();

class Solution {
private:
    int f1[N][N], f2[N][N];

public:
    int subsequencePairCount(vector<int>& nums) {
        const int n = nums.size();
        const int mod = 1000000007;

        memset(f1, 0, sizeof(f1));

        int m = 0;
        f1[0][0] = 1;

        for (int i = 0; i < n; i++) {
            int x = nums[i];
            m = max(m, x);

            for (int j = 0; j <= m; j++)
                for (int k = 0; k <= m; k++)
                    f2[j][k] = f1[j][k];

            for (int j = 0; j <= m; j++)
                for (int k = 0; k <= m; k++) {
                    f2[g[j][x]][k] = (f2[g[j][x]][k] + f1[j][k]) % mod;
                    f2[j][g[k][x]] = (f2[j][g[k][x]] + f1[j][k]) % mod;
                }

            for (int j = 0; j <= m; j++)
                for (int k = 0; k <= m; k++)
                    f1[j][k] = f2[j][k];
        }

        int ans = 0;
        for (int i = 1; i <= m; i++)
            ans = (ans + f1[i][i]) % mod;

        return ans;
    }
};