3850. 计算到达K的序列数

Hard

题目描述

给你一个整数数组 nums 和一个整数 k。

从初始值 val = 1 开始，从左到右处理 nums。在每个索引 i 处，你必须恰好选择以下操作之一：

将 val 乘以 nums[i]
将 val 除以 nums[i]
保持 val 不变

处理完所有元素后，当且仅当 val 的最终有理数值恰好等于 k 时，才认为 val 等于 k。

返回能使 val == k 的不同选择序列的数量。

注意：除法是有理数（精确）除法，不是整数除法。例如，2 / 4 = 1 / 2。

示例 1：

输入：nums = [2,3,2], k = 6
输出：2

示例 2：

输入：nums = [4,6,3], k = 2
输出：2

示例 3：

输入：nums = [1,5], k = 1
输出：3

约束条件：

1 <= nums.length <= 19
1 <= nums[i] <= 6
1 <= k <= 10^15

解题思路

这是一道关于数论和动态规划的题目。关键洞察是使用质因数分解来表示有理数。

核心思路：

由于 nums[i] 只能是1到6的数字，所有可能的质因子只有2、3、5。我们可以用三元组 (x, y, z) 表示数字 2^x * 3^y * 5^z。

算法步骤：

质因数分解：将目标值 k 分解为 2^kx * 3^ky * 5^kz 的形式
预处理数组：将 nums 中每个数字分解为质因数指数形式
动态规划：使用记忆化搜索，状态为 dp(index, x, y, z)，表示处理到第 index 个数字时，当前值为 2^x * 3^y * 5^z 的方案数
状态转移：对于每个数字，有三种选择：
- 乘法：指数相加
- 除法：指数相减
- 不变：指数不变

优化细节：

使用哈希表进行记忆化，避免重复计算
指数范围有限（最多19个数字，每个数字最大贡献有限），可以进行剪枝
当指数绝对值过大时提前返回0（不可能达到目标）

时间复杂度主要取决于可能的状态数量，由于指数范围有限，实际运行效率很高。

代码实现

class Solution {
public:
    const int MOD = 1e9 + 7;
    map<tuple<int, int, int, int>, int> memo;
    vector<vector<int>> factors;
    vector<int> target;
    
    int countSequences(vector<int>& nums, long long k) {
        // 分解k的质因数
        target = getPrimeFactors(k);
        
        // 预处理nums中每个数字的质因数
        factors.clear();
        for (int num : nums) {
            factors.push_back(getPrimeFactors(num));
        }
        
        memo.clear();
        return dfs(0, 0, 0, 0);
    }
    
private:
    vector<int> getPrimeFactors(long long n) {
        vector<int> result(3, 0); // [2的指数, 3的指数, 5的指数]
        
        while (n % 2 == 0) {
            result[0]++;
            n /= 2;
        }
        while (n % 3 == 0) {
            result[1]++;
            n /= 3;
        }
        while (n % 5 == 0) {
            result[2]++;
            n /= 5;
        }
        
        return result;
    }
    
    int dfs(int idx, int x, int y, int z) {
        if (abs(x) > 100 || abs(y) > 100 || abs(z) > 100) return 0;
        
        if (idx == factors.size()) {
            return (x == target[0] && y == target[1] && z == target[2]) ? 1 : 0;
        }
        
        auto key = make_tuple(idx, x, y, z);
        if (memo.count(key)) {
            return memo[key];
        }
        
        int result = 0;
        
        // 选择1: 乘法
        result = (result + dfs(idx + 1, x + factors[idx][0], y + factors[idx][1], z + factors[idx][2])) % MOD;
        
        // 选择2: 除法
        result = (result + dfs(idx + 1, x - factors[idx][0], y - factors[idx][1], z - factors[idx][2])) % MOD;
        
        // 选择3: 不变
        result = (result + dfs(idx + 1, x, y, z)) % MOD;
        
        return memo[key] = result;
    }
};

class Solution:
    def countSequences(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7
        
        def get_prime_factors(n):
            factors = [0, 0, 0]  # [2的指数, 3的指数, 5的指数]
            
            while n % 2 == 0:
                factors[0] += 1
                n //= 2
            while n % 3 == 0:
                factors[1] += 1
                n //= 3
            while n % 5 == 0:
                factors[2] += 1
                n //= 5
            
            return factors
        
        target = get_prime_factors(k)
        factors = [get_prime_factors(num) for num in nums]
        
        memo = {}
        
        def dfs(idx, x, y, z):
            if abs(x) > 100 or abs(y) > 100 or abs(z) > 100:
                return 0
            
            if idx == len(factors):
                return 1 if (x, y, z) == tuple(target) else 0
            
            if (idx, x, y, z) in memo:
                return memo[(idx, x, y, z)]
            
            result = 0
            
            # 选择1: 乘法
            result = (result + dfs(idx + 1, x + factors[idx][0], y + factors[idx][1], z + factors[idx][2])) % MOD
            
            # 选择2: 除法
            result = (result + dfs(idx + 1, x - factors[idx][0], y - factors[idx][1], z - factors[idx][2])) % MOD
            
            # 选择3: 不变
            result = (result + dfs(idx + 1, x, y, z)) % MOD
            
            memo[(idx, x, y, z)] = result
            return result
        
        return dfs(0, 0, 0, 0)

public class Solution {
    private const int MOD = 1000000007;
    private Dictionary<(int, int, int, int), int> memo;
    private List<int[]> factors;
    private int[] target;
    
    public int CountSequences(int[] nums, long k) {
        target = GetPrimeFactors(k);
        
        factors = new List<int[]>();
        foreach (int num in nums) {
            factors.Add(GetPrimeFactors(num));
        }
        
        memo = new Dictionary<(int, int, int, int), int>();
        return DFS(0, 0, 0, 0);
    }
    
    private int[] GetPrimeFactors(long n) {
        int[] result = new int[3]; // [2的指数, 3的指数, 5的指数]
        
        while (n % 2 == 0) {
            result[0]++;
            n /= 2;
        }
        while (n % 3 == 0) {
            result[1]++;
            n /= 3;
        }
        while (n % 5 == 0) {
            result[2]++;
            n /= 5;
        }
        
        return result;
    }
    
    private int DFS(int idx, int x, int y, int z) {
        if (Math.Abs(x) > 100 || Math.Abs(y) > 100 || Math.Abs(z) > 100) return 0;
        
        if (idx == factors.Count) {
            return (x == target[0] && y == target[1] && z == target[2]) ? 1 : 0;
        }
        
        var key = (idx, x, y, z);
        if (memo.ContainsKey(key)) {
            return memo[key];
        }
        
        int result = 0;
        
        // 选择1: 乘法
        result = (result + DFS(idx + 1, x + factors[idx][0], y + factors[idx][1], z + factors[idx][2])) % MOD;
        
        // 选择2: 除法
        result = (result + DFS(idx + 1, x - factors[idx][0], y - factors[idx][1], z - factors[idx][2])) % MOD;
        
        // 选择3: 不变
        result = (result + DFS(idx + 1, x, y, z)) % MOD;
        
        memo[key] = result;
        return result;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countSequences = function(nums, k) {
    const memo = new Map();
    
    function gcd(a, b) {
        while (b !== 0) {
            let temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    function normalize(num, den) {
        if (num === 0) return [0, 1];
        const g = gcd(Math.abs(num), Math.abs(den));
        num /= g;
        den /= g;
        if (den < 0) {
            num = -num;
            den = -den;
        }
        return [num, den];
    }
    
    function dfs(index, num, den) {
        if (index === nums.length) {
            return (num === k && den === 1) ? 1 : 0;
        }
        
        const key = `${index},${num},${den}`;
        if (memo.has(key)) {
            return memo.get(key);
        }
        
        let result = 0;
        
        // Leave unchanged
        result += dfs(index + 1, num, den);
        
        // Multiply
        const [newNum1, newDen1] = normalize(num * nums[index], den);
        result += dfs(index + 1, newNum1, newDen1);
        
        // Divide
        const [newNum2, newDen2] = normalize(num, den * nums[index]);
        result += dfs(index + 1, newNum2, newDen2);
        
        memo.set(key, result);
        return result;
    }
    
    return dfs(0, 1, 1);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	值	说明
时间复杂度	O(3^n × S)	n为数组长度，S为状态空间大小（指数范围有限）
空间复杂度	O(S)	记忆化存储的状态数量

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析