3336. Find the Number of Subsequences With Equal GCD

import java.util.*;

class Solution {

    private static final int MOD = 1_000_000_007;
    private static final int MAX = 200;

    public int subsequencePairCount(int[] nums) {

        long[][] dp = new long[MAX + 1][MAX + 1];
        dp[0][0] = 1;

        for (int num : nums) {

            long[][] next = new long[MAX + 1][MAX + 1];

            for (int g1 = 0; g1 <= MAX; g1++) {
                for (int g2 = 0; g2 <= MAX; g2++) {

                    if (dp[g1][g2] == 0) continue;

                    // Ignore current number
                    next[g1][g2] = (next[g1][g2] + dp[g1][g2]) % MOD;

                    // Put in first subsequence
                    int ng1 = (g1 == 0) ? num : gcd(g1, num);
                    next[ng1][g2] = (next[ng1][g2] + dp[g1][g2]) % MOD;

                    // Put in second subsequence
                    int ng2 = (g2 == 0) ? num : gcd(g2, num);
                    next[g1][ng2] = (next[g1][ng2] + dp[g1][g2]) % MOD;
                }
            }

            dp = next;
        }

        long ans = 0;

        for (int g = 1; g <= MAX; g++) {
            ans = (ans + dp[g][g]) % MOD;
        }

        return (int) ans;
    }

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

class Solution:
    MOD = 10**9 + 7
    MAX = 200

    def subsequencePairCount(self, nums: List[int]) -> int:
        dp = [[0] * (self.MAX + 1) for _ in range(self.MAX + 1)]
        dp[0][0] = 1

        for num in nums:
            nxt = [[0] * (self.MAX + 1) for _ in range(self.MAX + 1)]

            for g1 in range(self.MAX + 1):
                for g2 in range(self.MAX + 1):
                    if dp[g1][g2] == 0:
                        continue

                    nxt[g1][g2] = (nxt[g1][g2] + dp[g1][g2]) % self.MOD

                    ng1 = num if g1 == 0 else math.gcd(g1, num)
                    nxt[ng1][g2] = (nxt[ng1][g2] + dp[g1][g2]) % self.MOD

                    ng2 = num if g2 == 0 else math.gcd(g2, num)
                    nxt[g1][ng2] = (nxt[g1][ng2] + dp[g1][g2]) % self.MOD

            dp = nxt

        ans = 0
        for g in range(1, self.MAX + 1):
            ans = (ans + dp[g][g]) % self.MOD

        return ans

class Solution {
public:
    static const int MOD = 1000000007;
    static const int MAX = 200;

    int subsequencePairCount(vector<int>& nums) {
        vector<vector<long long>> dp(MAX + 1, vector<long long>(MAX + 1));
        dp[0][0] = 1;

        for (int num : nums) {
            vector<vector<long long>> nxt(MAX + 1, vector<long long>(MAX + 1));

            for (int g1 = 0; g1 <= MAX; g1++) {
                for (int g2 = 0; g2 <= MAX; g2++) {
                    if (dp[g1][g2] == 0) continue;

                    nxt[g1][g2] = (nxt[g1][g2] + dp[g1][g2]) % MOD;

                    int ng1 = (g1 == 0) ? num : gcd(g1, num);
                    nxt[ng1][g2] = (nxt[ng1][g2] + dp[g1][g2]) % MOD;

                    int ng2 = (g2 == 0) ? num : gcd(g2, num);
                    nxt[g1][ng2] = (nxt[g1][ng2] + dp[g1][g2]) % MOD;
                }
            }

            dp = move(nxt);
        }

        long long ans = 0;
        for (int g = 1; g <= MAX; g++) {
            ans = (ans + dp[g][g]) % MOD;
        }

        return (int)ans;
    }
};

/**
 * @param {number[]} nums
 * @return {number}
 */
var subsequencePairCount = function(nums) {
    const MOD = 1000000007;
    const MAX = 200;

    let dp = Array.from({ length: MAX + 1 }, () => Array(MAX + 1).fill(0));
    dp[0][0] = 1;

    const gcd = (a, b) => {
        while (b !== 0) {
            let t = a % b;
            a = b;
            b = t;
        }
        return a;
    };

    for (const num of nums) {
        let next = Array.from({ length: MAX + 1 }, () => Array(MAX + 1).fill(0));

        for (let g1 = 0; g1 <= MAX; g1++) {
            for (let g2 = 0; g2 <= MAX; g2++) {
                if (dp[g1][g2] === 0) continue;

                next[g1][g2] = (next[g1][g2] + dp[g1][g2]) % MOD;

                const ng1 = (g1 === 0) ? num : gcd(g1, num);
                next[ng1][g2] = (next[ng1][g2] + dp[g1][g2]) % MOD;

                const ng2 = (g2 === 0) ? num : gcd(g2, num);
                next[g1][ng2] = (next[g1][ng2] + dp[g1][g2]) % MOD;
            }
        }

        dp = next;
    }

    let ans = 0;
    for (let g = 1; g <= MAX; g++) {
        ans = (ans + dp[g][g]) % MOD;
    }

    return ans;
};