Problem statement

You are given an integer array nums.

Count the pairs of non-empty subsequences (seq1, seq2) of nums such that:

• seq1 and seq2 are disjoint — no index of nums is used by both, and
• the GCD of the elements of seq1 equals the GCD of the elements of seq2.

The pairs are ordered: (seq1, seq2) and (seq2, seq1) count separately when they are different. Return the count modulo 10^9 + 7.

Example 1

Input: nums = [1,2,3,4]
Output: 10
Explanation: Every pair of disjoint subsequences with GCD 1 on both sides, e.g. ([1], [3]) or ([2,3], [1,4]).

Example 2

Input: nums = [10,20,30]
Output: 2
Explanation: ([10], [20,30]) and ([20,30], [10]) — both sides have GCD 10.

Example 3

Input: nums = [1,1,1,1]
Output: 50

Constraints

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

Hints for Find the Number of Subsequences With Equal GCD

1. Hint 1

   Each index has three fates: it joins seq1, joins seq2, or is left out. Brute force over all 3^n choices is far too slow — what do you actually need to remember?

2. Hint 2

   Only the running GCD of each side matters. With values up to 200 there are at most 201 × 201 states (use 0 for an empty side, since gcd(0, x) = x).

3. Hint 3

   dp[g1][g2] counts assignments of the prefix with those GCDs. For each new x, add each state's count to itself, to (gcd(g1, x), g2) and to (g1, gcd(g2, x)). The answer is Σ dp[g][g] for g >= 1.

How to solve Find the Number of Subsequences With Equal GCD

Scan the array once, deciding for every element whether it joins the first subsequence, the second, or neither. The future only depends on the two running GCDs, and since all values are at most 200, a 201 × 201 table of counts captures everything.

Approach

1. Let M = max(nums). Start with dp[0][0] = 1, where GCD 0 means "empty so far".
2. For each x: copy dp into ndp (leave x out); for every state (g1, g2) with count c, add c to ndp[gcd(g1, x)][g2] and to ndp[g1][gcd(g2, x)].
3. After all elements, return Σ_{g = 1..M} dp[g][g] modulo 10^9 + 7.

Why it works

Each assignment of the elements to (first, second, neither) is followed by exactly one path through the states, and the final state records both GCDs. Requiring g >= 1 excludes empty sides (an empty side has GCD 0), and diagonal states are exactly the pairs with equal GCDs.

Complexity

• Time — O(n · M^2)
• Space — O(M^2)

Pitfalls

• Write into a copy of the table — updating in place would let one element join a side twice.
• Ordered pairs are intended: the DP naturally counts (A, B) and (B, A) separately, so do not divide by 2.
• Precompute gcd(g, x) or keep the helper cheap; it is called O(n · M^2) times.

Reference solution

Python

from typing import List
from math import gcd

def subsequencePairCount(nums: List[int]) -> int:
    MOD = 10**9 + 7
    M = max(nums)
    dp = [[0] * (M + 1) for _ in range(M + 1)]
    dp[0][0] = 1
    for x in nums:
        g = [gcd(v, x) for v in range(M + 1)]
        nd = [row[:] for row in dp]
        for g1 in range(M + 1):
            row = dp[g1]
            a = g[g1]
            for g2 in range(M + 1):
                c = row[g2]
                if c:
                    nd[a][g2] = (nd[a][g2] + c) % MOD
                    b = g[g2]
                    nd[g1][b] = (nd[g1][b] + c) % MOD
        dp = nd
    return sum(dp[v][v] for v in range(1, M + 1)) % MOD

Java

static int gcd(int a, int b) { while (b != 0) { int t = a % b; a = b; b = t; } return a; }

public static int subsequencePairCount(int[] nums) {
    final int MOD = 1000000007;
    int M = 0;
    for (int x : nums) M = Math.max(M, x);
    int[][] dp = new int[M + 1][M + 1];
    dp[0][0] = 1;
    int[] g = new int[M + 1];
    for (int x : nums) {
        for (int v = 0; v <= M; v++) g[v] = gcd(v, x);
        int[][] nd = new int[M + 1][];
        for (int r = 0; r <= M; r++) nd[r] = dp[r].clone();
        for (int g1 = 0; g1 <= M; g1++) {
            int a = g[g1];
            for (int g2 = 0; g2 <= M; g2++) {
                int c = dp[g1][g2];
                if (c == 0) continue;
                nd[a][g2] = (nd[a][g2] + c) % MOD;
                int b = g[g2];
                nd[g1][b] = (nd[g1][b] + c) % MOD;
            }
        }
        dp = nd;
    }
    long total = 0;
    for (int d = 1; d <= M; d++) total += dp[d][d];
    return (int) (total % MOD);
}

C++

int subsequencePairCount(vector<int>& nums) {
    const int MOD = 1000000007;
    int M = *max_element(nums.begin(), nums.end());
    vector<vector<int>> dp(M + 1, vector<int>(M + 1, 0));
    dp[0][0] = 1;
    vector<int> g(M + 1);
    for (int x : nums) {
        for (int v = 0; v <= M; v++) g[v] = __gcd(v, x);
        vector<vector<int>> nd = dp;
        for (int g1 = 0; g1 <= M; g1++) {
            int a = g[g1];
            for (int g2 = 0; g2 <= M; g2++) {
                int c = dp[g1][g2];
                if (c == 0) continue;
                nd[a][g2] = (nd[a][g2] + c) % MOD;
                int b = g[g2];
                nd[g1][b] = (nd[g1][b] + c) % MOD;
            }
        }
        dp = nd;
    }
    long long total = 0;
    for (int d = 1; d <= M; d++) total += dp[d][d];
    return (int) (total % MOD);
}

JavaScript

var subsequencePairCount = function(nums) {
    var MOD = 1000000007;
    var gcd = function(a, b) { while (b) { var t = a % b; a = b; b = t; } return a; };
    var M = 0;
    for (var i = 0; i < nums.length; i++) if (nums[i] > M) M = nums[i];
    var dp = [];
    for (var r = 0; r <= M; r++) dp.push(new Array(M + 1).fill(0));
    dp[0][0] = 1;
    for (var k = 0; k < nums.length; k++) {
        var x = nums[k];
        var g = [];
        for (var v = 0; v <= M; v++) g.push(gcd(v, x));
        var nd = [];
        for (var r2 = 0; r2 <= M; r2++) nd.push(dp[r2].slice());
        for (var g1 = 0; g1 <= M; g1++) {
            var a = g[g1];
            for (var g2 = 0; g2 <= M; g2++) {
                var c = dp[g1][g2];
                if (c === 0) continue;
                nd[a][g2] = (nd[a][g2] + c) % MOD;
                var b = g[g2];
                nd[g1][b] = (nd[g1][b] + c) % MOD;
            }
        }
        dp = nd;
    }
    var total = 0;
    for (var d = 1; d <= M; d++) total = (total + dp[d][d]) % MOD;
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard