Leetcode每日一题 —— 3336. 最大公约数相等的子序列数量

SomeBottle 2026-07-14 12:30 1

思路

这题的状态还是挺好找的，处理到的下标 idx，第一个序列的 GCD gcd1 以及第二个序列的 GCD gcd2。

idx 从 0 处理到 n-1，每一步有三个分支：每个数字要不不选，要不放到子序列 seq1 中，要不放到子序列 seq2 中。idx 到头后就形成了一组方案。

按照这个处理思路，很适合用 DFS 来做，但是状态空间可能很大，因此还要加记忆化。

GCD 的话就用辗转相除法，辗转相除法可以用正方形填矩形去理解，真的是一旦知道，一辈子都忘不掉了。

代码

class Solution {

public:

    int subsequencePairCount(vector<int>& nums) {

        // 每个位置要不选，要不不选

        // 然后还有 seq1 的 GCD 和 seq2 的 GCD 两个状态，共三个状态

        int n=nums.size();



        int modulus=(int)(1e9+7);

        // 求二者公因数

        auto GCD=[&](int a, int b)->int {

            if(a<b){

                // 保持 a 较大

                swap(a, b);

            }

            // 辗转相除法

            int dividend=a;

            int div=b;

            if(div==0){

                return dividend;

            }

            while(true){

                int remainder=dividend%div;

                if(remainder==0){

                    return div;

                }

                dividend=div;

                div=remainder;

            }

            return -1;

        };



        // 记忆化

        static int memo[201][201][201];

        for(int i=0;i<n;i++){

            for(int j=0;j<201;j++){

                for(int k=0;k<201;k++){

                    memo[i][j][k]=-1;

                }

            }

        }



        auto dfs=[&](auto&& self, int idx, int gcd1, int gcd2)->int {

            if(idx>=n){

                // 到达 n，说明当前数组中每个数是去是留，放到哪个 seq 已经分配完了，形成了一个方案

                // 这个时候才判断 gcd1 是否等于 gcd2

                if(gcd1>0&&gcd1==gcd2){

                    return 1;

                }

                return 0;

            }            

            if(memo[idx][gcd1][gcd2]!=-1){

                return memo[idx][gcd1][gcd2];

            }

            // 接下来对于 idx，就是三种走向:  

            // 1. 不选择 idx 对应的元素

            // 2. 选择 idx，选入 seq1

            // 3. 选择 idx，选入 seq2

            // 三种走向的子序列对数量累加起来

            int ans = (int)(((long long)self(self, idx+1, gcd1, gcd2) 

                + self(self, idx+1, GCD(gcd1,nums[idx]),gcd2)

                + self(self,idx+1, gcd1, GCD(gcd2,nums[idx])))%modulus);

            memo[idx][gcd1][gcd2]=ans;

            return ans;

        };



        return dfs(dfs,0,0,0);

    }

};

最新回复 (2)

魔法师 07-14 21:19

1楼

思路

感觉这题应该是有合适的数学算法的，但是今天越想越晕……脑子像一团浆糊

最后还是用动规/递推做的。

代码

    private static final int MOD = 1_000_000_007;

    public int subsequencePairCount(int[] nums) {

        int n = nums.length;

        int max = 0;

        for (int num : nums) {

            max = Math.max(max, num);

        }

        int[][] dp = new int[max + 1][max + 1];

        dp[0][0] = 1;

        for (int num : nums) {

            int[][] next = new int[max + 1][max + 1];

            for (int j = 0; j <= max; j++) {

                int gcd1 = gcd(num, j);

                for (int k = 0; k <= max; k++) {

                    int val = dp[j][k];

                    int gcd2 = gcd(num, k);

                    next[j][k] = (next[j][k] + val) % MOD;

                    next[gcd1][k] = (next[gcd1][k] + val) % MOD;

                    next[j][gcd2] = (next[j][gcd2] + val) % MOD;

                }

            }

            dp = next;

        }



        int ans = 0;

        for (int i = 1; i <= max; i++) {

            ans = (ans + dp[i][i]) % MOD;

        }

        return ans;

    }

    private int gcd(int a, int b) {

        while (b != 0) {

            int temp = a;

            a = b;

            b = temp % b;

        }

        return a;

    }

snow 07-14 23:54

2楼

今天来的有点晚，先贴一个代码，大概思路就是 dp_{i,j,k} 表示选了前 i 个数，集合 1 的 gcd 为 j，集合 2 的 gcd 为 k，枚举到每一个数，可以是加入集合 1 或者加入集合 2，或者不加入任何集合，转移即可，注意到省略一维。

constexpr int MOD = 1E9 + 7;

class Solution {

public:

    int subsequencePairCount(vector<int>& nums) {

        int n = nums.size();

        array<array<int, 201>, 201> dp{};

        dp[nums[0]][0] = dp[0][nums[0]] = dp[0][0] = 1;

        for (int i = 1; i < n; i++) {

            array<array<int, 201>, 201> ndp{};

            for (int j = 0; j < 201; j++) {

                for (int k = 0; k < 201; k++) {

                    if (!dp[j][k]) continue;

                    ndp[__gcd(j, nums[i])][k] = (1LL * ndp[__gcd(j, nums[i])][k] + dp[j][k]) % MOD;

                    ndp[j][__gcd(k, nums[i])] = (1LL * ndp[j][__gcd(k, nums[i])] + dp[j][k]) % MOD;

                    ndp[j][k] = (1LL * ndp[j][k] + dp[j][k]) % MOD;

                }

            }

            dp = ndp;

        }

        int ans = 0;

        for (int i = 1; i < 201; i++) {

            ans = (1LL * ans + dp[i][i]) % MOD;

        }

        return ans;

    }

};

* 帖子来源Linux.do

附近帖子