Skip to content

3336. Find the Number of Subsequences With Equal GCD

Description

You are given an integer array nums.

Your task is to find the number of pairs of non-empty subsequences (seq1, seq2) of nums that satisfy the following conditions:

  • The subsequences seq1 and seq2 are disjoint, meaning no index of nums is common between them.
  • The GCD of the elements of seq1 is equal to the GCD of the elements of seq2.

Return the total number of such pairs.

Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: nums = [1,2,3,4]

Output: 10

Explanation:

The subsequence pairs which have the GCD of their elements equal to 1 are:

  • ([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])

Example 2:

Input: nums = [10,20,30]

Output: 2

Explanation:

The subsequence pairs which have the GCD of their elements equal to 10 are:

  • ([10, 20, 30], [10, 20, 30])
  • ([10, 20, 30], [10, 20, 30])

Example 3:

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

Output: 50

 

Constraints:

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

Solutions

Solution 1: Memoization

Thinking

We count pairs of disjoint subsequences with equal GCD. With \(n,M \le 200\), memoizing on index and the two running GCDs has about \(n M^2\) states.

Each value is skipped, folded into the first GCD, or folded into the second; an empty subsequence has GCD \(0\).

A finished state is valid when the two GCDs are equal. The initial call includes two empty subsequences, so we subtract \(1\) before reducing modulo \(10^9+7\).

We define a function \(\textit{dfs}(i, j, k)\) as the number of ways when considering elements with indices \(0 \sim i\), where the current GCD of the first subsequence is \(j\) and that of the second subsequence is \(k\). By convention, the GCD of an empty subsequence is \(0\), and \(\gcd(x, 0) = x\).

For the element at index \(i\), there are three choices:

  1. Skip it: transition to \(\textit{dfs}(i - 1, j, k)\);
  2. Put it into the first subsequence: transition to \(\textit{dfs}(i - 1, \gcd(\textit{nums}[i], j), k)\);
  3. Put it into the second subsequence: transition to \(\textit{dfs}(i - 1, j, \gcd(\textit{nums}[i], k))\).

Base case: when \(i \lt 0\), return \(1\) if \(j = k\), otherwise return \(0\).

The initial call \(\textit{dfs}(n - 1, 0, 0)\) counts all pairs with equal GCDs, including the case where both subsequences are empty. Therefore, we subtract \(1\) and take the result modulo \(10^9 + 7\).

The time complexity is \(O(n \times m^2 \times \log m)\), and the space complexity is \(O(n \times m^2)\), where \(n\) is the length of the array and \(m\) is the maximum value in the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def subsequencePairCount(self, nums: List[int]) -> int:
        @cache
        def dfs(i: int, j: int, k: int) -> int:
            if i < 0:
                return int(j == k)
            return (
                dfs(i - 1, j, k)
                + dfs(i - 1, gcd(nums[i], j), k)
                + dfs(i - 1, j, gcd(nums[i], k))
            ) % mod

        mod = 10**9 + 7
        return (dfs(len(nums) - 1, 0, 0) - 1) % mod

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    private int[] nums;
    private Integer[][][] f;
    private static final int MOD = 1_000_000_007;

    public int subsequencePairCount(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        int m = 0;
        for (int x : nums) {
            if (x > m) m = x;
        }
        this.f = new Integer[n + 1][m + 1][m + 1];
        return (dfs(n, 0, 0) - 1 + MOD) % MOD;
    }

    private int dfs(int i, int j, int k) {
        if (i == 0) {
            return j == k ? 1 : 0;
        }
        if (f[i][j][k] != null) {
            return f[i][j][k];
        }
        int x = nums[i - 1];
        int res = ((dfs(i - 1, j, k) + dfs(i - 1, gcd(x, j), k)) % MOD + dfs(i - 1, j, gcd(x, k)))
            % MOD;
        f[i][j][k] = res;
        return res;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int subsequencePairCount(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        int n = nums.size();
        int m = ranges::max(nums);
        vector f(n, vector(m + 1, vector<int>(m + 1, -1)));
        auto dfs = [&](this auto&& dfs, int i, int j, int k) -> int {
            if (i < 0) {
                return j == k;
            }
            int& res = f[i][j][k];
            if (res < 0) {
                res = ((dfs(i - 1, j, k)
                           + dfs(i - 1, gcd(nums[i], j), k))
                              % MOD
                          + dfs(i - 1, j, gcd(nums[i], k)))
                    % MOD;
            }
            return res;
        };
        return (dfs(n - 1, 0, 0) - 1 + MOD) % MOD;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
func subsequencePairCount(nums []int) int {
    const mod = 1_000_000_007
    n := len(nums)
    m := slices.Max(nums)
    f := make([][][]int, n)
    for i := range f {
        f[i] = make([][]int, m+1)
        for j := range f[i] {
            f[i][j] = make([]int, m+1)
            for k := range f[i][j] {
                f[i][j][k] = -1
            }
        }
    }
    var gcd func(int, int) int
    gcd = func(a, b int) int {
        if b == 0 {
            return a
        }
        return gcd(b, a%b)
    }
    var dfs func(i, j, k int) int
    dfs = func(i, j, k int) int {
        if i < 0 {
            if j == k {
                return 1
            }
            return 0
        }
        res := &f[i][j][k]
        if *res < 0 {
            x := nums[i]
            *res = ((dfs(i-1, j, k)+
                dfs(i-1, gcd(x, j), k))%mod +
                dfs(i-1, j, gcd(x, k))) % mod
        }
        return *res
    }
    return (dfs(n-1, 0, 0) - 1 + mod) % mod
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function subsequencePairCount(nums: number[]): number {
    const mod = 1_000_000_007;
    const n = nums.length;
    const m = Math.max(...nums);
    const f: number[][][] = Array.from({ length: n }, () =>
        Array.from({ length: m + 1 }, () => new Array(m + 1).fill(-1)),
    );
    const gcd = (a: number, b: number): number => {
        a = Math.abs(a);
        b = Math.abs(b);
        while (b !== 0) {
            [a, b] = [b, a % b];
        }
        return a;
    };
    const dfs = (i: number, j: number, k: number): number => {
        if (i < 0) {
            return j === k ? 1 : 0;
        }
        let res = f[i][j][k];
        if (res < 0) {
            const x = nums[i];
            res =
                (((dfs(i - 1, j, k) + dfs(i - 1, gcd(x, j), k)) % mod) + dfs(i - 1, j, gcd(x, k))) %
                mod;
            f[i][j][k] = res;
        }
        return res;
    };
    return (((dfs(n - 1, 0, 0) - 1) % mod) + mod) % mod;
}

Solution 2: Dynamic Programming

Thinking

The memoized recursion pays for call depth and a three-dimensional cache. The same transitions fit a rolling table: a new \(g\) receives the three choices for \(x\).

Space drops from \(O(n M^2)\) to \(O(M^2)\) and there is no recursion. The answer is still the diagonal sum minus one.

Skipping zero cells in \(f\) further reduces the practical constant.

We can convert the memoization in Solution 1 into an iterative DP.

Define \(f[j][k]\) as the number of ways after processing the current elements such that the GCD of the first subsequence is \(j\) and that of the second is \(k\). Initially, \(f[0][0] = 1\).

For each element \(x\), transfer into a new array \(g\):

\[ \begin{aligned} g[j][k] &\mathrel{+}= f[j][k], \\ g[\gcd(j, x)][k] &\mathrel{+}= f[j][k], \\ g[j][\gcd(k, x)] &\mathrel{+}= f[j][k]. \end{aligned} \]

These correspond to skipping \(x\), putting \(x\) into the first subsequence, and putting \(x\) into the second subsequence, respectively. After processing all elements, the answer is \(\sum_{i=0}^{m} f[i][i] - 1\), taken modulo \(10^9 + 7\).

The time complexity is \(O(n \times m^2 \times \log m)\), and the space complexity is \(O(m^2)\), where \(n\) is the length of the array and \(m\) is the maximum value in the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def subsequencePairCount(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        m = max(nums)
        f = [[0] * (m + 1) for _ in range(m + 1)]
        f[0][0] = 1
        for x in nums:
            g = [[0] * (m + 1) for _ in range(m + 1)]
            for j in range(m + 1):
                for k in range(m + 1):
                    if f[j][k] == 0:
                        continue
                    v = f[j][k]
                    g[j][k] = (g[j][k] + v) % mod
                    gj, gk = gcd(j, x), gcd(k, x)
                    g[gj][k] = (g[gj][k] + v) % mod
                    g[j][gk] = (g[j][gk] + v) % mod
            f = g
        return (sum(f[i][i] for i in range(m + 1)) - 1) % mod

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int subsequencePairCount(int[] nums) {
        final int MOD = 1_000_000_007;
        int m = 0;
        for (int x : nums) {
            m = Math.max(m, x);
        }
        int[][] f = new int[m + 1][m + 1];
        f[0][0] = 1;
        for (int x : nums) {
            int[][] g = new int[m + 1][m + 1];
            for (int j = 0; j <= m; ++j) {
                for (int k = 0; k <= m; ++k) {
                    if (f[j][k] == 0) {
                        continue;
                    }
                    int v = f[j][k];
                    g[j][k] = (g[j][k] + v) % MOD;
                    int gj = gcd(j, x), gk = gcd(k, x);
                    g[gj][k] = (g[gj][k] + v) % MOD;
                    g[j][gk] = (g[j][gk] + v) % MOD;
                }
            }
            f = g;
        }
        long ans = 0;
        for (int i = 0; i <= m; ++i) {
            ans += f[i][i];
        }
        return (int) ((ans - 1 + MOD) % MOD);
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int subsequencePairCount(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        int m = ranges::max(nums);
        vector f(m + 1, vector<int>(m + 1));
        f[0][0] = 1;
        for (int x : nums) {
            vector g(m + 1, vector<int>(m + 1));
            for (int j = 0; j <= m; ++j) {
                for (int k = 0; k <= m; ++k) {
                    if (f[j][k] == 0) {
                        continue;
                    }
                    int v = f[j][k];
                    g[j][k] = (g[j][k] + v) % MOD;
                    int gj = gcd(j, x), gk = gcd(k, x);
                    g[gj][k] = (g[gj][k] + v) % MOD;
                    g[j][gk] = (g[j][gk] + v) % MOD;
                }
            }
            f.swap(g);
        }
        long long ans = 0;
        for (int i = 0; i <= m; ++i) {
            ans += f[i][i];
        }
        return (ans - 1 + MOD) % MOD;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func subsequencePairCount(nums []int) int {
    const mod = 1_000_000_007
    m := slices.Max(nums)
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, m+1)
    }
    f[0][0] = 1
    gcd := func(a, b int) int {
        for b != 0 {
            a, b = b, a%b
        }
        return a
    }
    for _, x := range nums {
        g := make([][]int, m+1)
        for i := range g {
            g[i] = make([]int, m+1)
        }
        for j := 0; j <= m; j++ {
            for k := 0; k <= m; k++ {
                if f[j][k] == 0 {
                    continue
                }
                v := f[j][k]
                g[j][k] = (g[j][k] + v) % mod
                gj, gk := gcd(j, x), gcd(k, x)
                g[gj][k] = (g[gj][k] + v) % mod
                g[j][gk] = (g[j][gk] + v) % mod
            }
        }
        f = g
    }
    ans := 0
    for i := 0; i <= m; i++ {
        ans += f[i][i]
    }
    return (ans - 1 + mod) % mod
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function subsequencePairCount(nums: number[]): number {
    const mod = 1_000_000_007;
    const m = Math.max(...nums);
    let f: number[][] = Array.from({ length: m + 1 }, () => Array(m + 1).fill(0));
    f[0][0] = 1;
    const gcd = (a: number, b: number): number => {
        while (b !== 0) {
            [a, b] = [b, a % b];
        }
        return a;
    };
    for (const x of nums) {
        const g: number[][] = Array.from({ length: m + 1 }, () => Array(m + 1).fill(0));
        for (let j = 0; j <= m; ++j) {
            for (let k = 0; k <= m; ++k) {
                if (f[j][k] === 0) {
                    continue;
                }
                const v = f[j][k];
                g[j][k] = (g[j][k] + v) % mod;
                const gj = gcd(j, x);
                const gk = gcd(k, x);
                g[gj][k] = (g[gj][k] + v) % mod;
                g[j][gk] = (g[j][gk] + v) % mod;
            }
        }
        f = g;
    }
    let ans = 0;
    for (let i = 0; i <= m; ++i) {
        ans += f[i][i];
    }
    return (((ans - 1) % mod) + mod) % mod;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
impl Solution {
    pub fn subsequence_pair_count(nums: Vec<i32>) -> i32 {
        fn gcd(mut first: usize, mut second: usize) -> usize {
            while second != 0 {
                let remainder = first % second;
                first = second;
                second = remainder;
            }
            first
        }
        const MOD: i32 = 1_000_000_007;
        const GCD_STATE_COUNT: usize = 201;
        let mut dp = [[0i32; GCD_STATE_COUNT]; GCD_STATE_COUNT];
        dp[0][0] = 1;
        for &num in nums.iter() {
            let value = num as usize;
            let mut gcd_with_value = [0usize; GCD_STATE_COUNT];
            for gcd_value in 0..GCD_STATE_COUNT {
                gcd_with_value[gcd_value] = gcd(gcd_value, value);
            }
            let mut next_dp = dp;
            for first_gcd in 0..GCD_STATE_COUNT {
                for second_gcd in 0..GCD_STATE_COUNT {
                    let count = dp[first_gcd][second_gcd];
                    if count == 0 {
                        continue;
                    }
                    let next_first_gcd = gcd_with_value[first_gcd];
                    let next_second_gcd = gcd_with_value[second_gcd];
                    next_dp[next_first_gcd][second_gcd] += count;
                    if next_dp[next_first_gcd][second_gcd] >= MOD {
                        next_dp[next_first_gcd][second_gcd] -= MOD;
                    }
                    next_dp[first_gcd][next_second_gcd] += count;
                    if next_dp[first_gcd][next_second_gcd] >= MOD {
                        next_dp[first_gcd][next_second_gcd] -= MOD;
                    }
                }
            }
            dp = next_dp;
        }
        let mut answer = 0;
        for gcd_value in 1..GCD_STATE_COUNT {
            answer += dp[gcd_value][gcd_value];
            if answer >= MOD {
                answer -= MOD;
            }
        }
        answer
    }
}

Comments