问题描述给定整数数组 nums长度 ≤ 19元素范围 1~6和整数 k≤ 10¹⁵。从 val 1 开始对每个 nums[i] 必须选择三种操作之一· 乘以 nums[i]· 除以 nums[i]· 保持不变除法为有理数精确除法如 2/4 1/2。求最终 val k 的不同操作序列数量。---解法一记忆化搜索最直观用分数 p/q 表示当前值从 1/1 开始目标变为 k/1。javaimport java.util.HashMap;import java.util.Map;class Solution {private MapLong, Integer[] memo;private int[] nums;private long k;public int countSequences(int[] nums, long k) {this.nums nums;this.k k;int n nums.length;memo new HashMap[n];for (int i 0; i n; i) {memo[i] new HashMap();}return dfs(n - 1, 1, 1);}// 处理完 [0..i] 后当前值为 p/q返回方案数private int dfs(int i, long p, long q) {if (i 0) {return p k q 1 ? 1 : 0;}// 用 p * 31 q 作为简易哈希键p,q 范围有限long key p * 31 q;if (memo[i].containsKey(key)) {return memo[i].get(key);}int x nums[i];int res 0;// 操作1乘以 xres dfs(i - 1, p * x, q);// 操作2除以 xres dfs(i - 1, p, q * x);// 操作3不变res dfs(i - 1, p, q);memo[i].put(key, res);return res;}}约分优化版减少状态每次乘除后约分避免 p/q 非最简形式产生冗余状态javaclass Solution {private MapLong, Integer[] memo;private int[] nums;private long k;private long gcd(long a, long b) {return b 0 ? a : gcd(b, a % b);}public int countSequences(int[] nums, long k) {this.nums nums;this.k k;int n nums.length;memo new HashMap[n];for (int i 0; i n; i) {memo[i] new HashMap();}return dfs(n - 1, 1, 1);}private int dfs(int i, long p, long q) {if (i 0) {return p k q 1 ? 1 : 0;}long key p * 31 q;if (memo[i].containsKey(key)) {return memo[i].get(key);}int x nums[i];int res 0;long g gcd(p * x, q);res dfs(i - 1, p * x / g, q / g); // 乘以 xg gcd(p, q * x);res dfs(i - 1, p / g, q * x / g); // 除以 xres dfs(i - 1, p, q); // 不变memo[i].put(key, res);return res;}}---解法二组合数学 DP最优AC核心思路· 1~6 的质因子只有 2、3、5· 对 k 质因数分解若含其他质因子直接返回 0· 数字 1三种操作都不影响结果贡献 3^count[1]· 数字 5只影响质因子 5用 DP 计算贡献方案数· 数字 2、3自身影响 被 42²和 62×3影响· 枚举 4 和 6 的净贡献范围 [-count, count]反推 2、3、5 需要的净贡献用乘法原理累加javaclass Solution {public int countSequences(int[] nums, long k) {int n nums.length;// f[i][j]处理 i 个相同数字净贡献为 j-n 的方案数// j n 表示净贡献为 0避免负下标[reference:9]long[][] f new long[n 1][2 * n 1];f[0][n] 1;for (int i 1; i n; i) {for (int j 0; j 2 * n; j) {f[i][j] f[i - 1][j]; // 不变贡献 0if (j 0) f[i][j] f[i - 1][j - 1]; // 乘贡献 1if (j 2 * n) f[i][j] f[i - 1][j 1]; // 除贡献 -1}}int[] cnt new int[7];for (int x : nums) cnt[x];long K k;int[] need new int[7];for (int p 2; p 6; p) {while (K % p 0) {K / p;need[p];}}if (K 1) return 0; // 包含 2,3,5 以外的质因子[reference:10]long ans 0;// 枚举 4 和 6 的净贡献[reference:11]for (int four -cnt[4]; four cnt[4]; four) {for (int six -cnt[6]; six cnt[6]; six) {int two four * 2 six; // 4贡献2个26贡献1个2int three six; // 6贡献1个3int need2 need[2] - two;int need3 need[3] - three;int need5 need[5];if (need2 -n need2 n need3 -n need3 n need5 -n need5 n) {long tmp f[cnt[4]][four n] * f[cnt[6]][six n];tmp * f[cnt[2]][need2 n];tmp * f[cnt[3]][need3 n];tmp * f[cnt[5]][need5 n];ans tmp;}}}// 数字 1 任意选择三种操作[reference:12][reference:13]for (int i 0; i cnt[1]; i) ans * 3;return (int) ans;}}---两种解法对比记忆化搜索 组合数学 DP思路 直接模拟三种操作缓存中间状态 质因数分解分别计算每种数字的贡献代码量 较少直观 较多需理解组合数学时间复杂度 O(状态数) ≈ 可过 O(n²)适用场景 快速实现不易出错 最优解体现数学思维推荐解法二作为正式提交方案效率更高且符合题目 Hard 难度预期。
