问题描述
给定整数数组 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。
```java
import java.util.HashMap;
import java.util.Map;
class Solution {
private Map<Long, 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：乘以 x
res += dfs(i - 1, p * x, q);
// 操作2：除以 x
res += dfs(i - 1, p, q * x);
// 操作3：不变
res += dfs(i - 1, p, q);
memo[i].put(key, res);
return res;
}
}
```
约分优化版（减少状态）
每次乘除后约分，避免 p/q 非最简形式产生冗余状态：
```java
class Solution {
private Map<Long, 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); // 乘以 x
g = gcd(p, q * x);
res += dfs(i - 1, p / g, q * x / g); // 除以 x
res += 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：自身影响 + 被 4（=2²）和 6（=2×3）影响
· 枚举 4 和 6 的净贡献（范围 [-count, count]），反推 2、3、5 需要的净贡献，用乘法原理累加
```java
class 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]; // 不变：贡献 0
if (j > 0) f[i][j] += f[i - 1][j - 1]; // 乘：贡献 +1
if (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个2，6贡献1个2
int three = six; // 6贡献1个3
int 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 难度预期。
