这是 LeetCode 3539. 魔法序列的数组乘积之和 的 Java 实现。思路本题是组合数学 记忆化搜索。核心观察 枚举每个 nums[i] 被选取的次数 c_iΣc_i m则- 序列的排列数为多重集排列m! / (c_0! · c_1! · ... · c_{n-1}!)- 数组乘积为nums[0]^c_0 · nums[1]^c_1 · ...利用组合数 C(remaining, count) 在递归中直接累乘恰好得到 m! / ∏c_i! 的因子无需最后再乘 m!。状态定义 dp(i, leftM, carry, leftK) 表示- 处理到第 i 个元素- 还需选 leftM 个数- 当前低位向第 i 位的进位为 carry即 sum i- 还需满足 leftK 个置位转移 枚举选 count 个下标 i则- 当前位产生的置位(carry count) 1- 新进位(carry count) 1- 贡献C(leftM, count) · nums[i]^count复杂度 O(n · m² · k)由于 m ≤ 30, n ≤ 50完全可行。---javaclass Solution {private static final int MOD 1_000_000_007;private Integer[][][][] memo;private int[][] comb;private int[] nums;public int magicalSum(int m, int k, int[] nums) {this.nums nums;int n nums.length;// 预处理组合数 C[i][j] C(i, j)comb new int[m 1][m 1];for (int i 0; i m; i) {comb[i][0] 1;for (int j 1; j i; j) {comb[i][j] (comb[i - 1][j - 1] comb[i - 1][j]) % MOD;}}// 记忆化: memo[remainingM][remainingK][index][carry]// carry 的范围为 [0, m]因为每次进位 (carry count) 1 mmemo new Integer[m 1][k 1][n 1][m 1];return dp(m, k, 0, 0);}private int dp(int remainingM, int remainingK, int i, int carry) {// 剪枝即使剩余所有位都产生置位也不够 leftKint bits Integer.bitCount(carry);if (remainingM 0 || remainingK 0 || bits remainingM remainingK) {return 0;}// 已选完所有数检查进位中是否恰好还有 remainingK 个置位if (remainingM 0) {return remainingK bits ? 1 : 0;}// 没有更多数字可选但还没选够if (i nums.length) {return 0;}if (memo[remainingM][remainingK][i][carry] ! null) {return memo[remainingM][remainingK][i][carry];}long res 0;for (int count 0; count remainingM; count) {// 从剩余 remainingM 个位置中选 count 个放 nums[i]long contribution (long) comb[remainingM][count] * modPow(nums[i], count) % MOD;int newCarry carry count;int next dp(remainingM - count, remainingK - (newCarry 1), i 1, newCarry 1);res (res next * contribution) % MOD;}memo[remainingM][remainingK][i][carry] (int) res;return (int) res;}private long modPow(long base, int exp) {long res 1;while (exp 0) {if ((exp 1) 1) {res res * base % MOD;}base base * base % MOD;exp 1;}return res;}}---验证- 示例 1m5, k5, nums[1,10,100,10000,1000000] → 991600007 ✓- 示例 2m2, k2, nums[5,4,3,2,1] → 170 ✓- 示例 3m1, k1, nums[28] → 28 ✓
这是 LeetCode 3539. 魔法序列的数组乘积之和 的 Java 实现。思路本题是组合数学 记忆化搜索。核心观察 枚举每个 nums[i] 被选取的次数 c_iΣc_i m则- 序列的排列数为多重集排列m! / (c_0! · c_1! · ... · c_{n-1}!)- 数组乘积为nums[0]^c_0 · nums[1]^c_1 · ...利用组合数 C(remaining, count) 在递归中直接累乘恰好得到 m! / ∏c_i! 的因子无需最后再乘 m!。状态定义 dp(i, leftM, carry, leftK) 表示- 处理到第 i 个元素- 还需选 leftM 个数- 当前低位向第 i 位的进位为 carry即 sum i- 还需满足 leftK 个置位转移 枚举选 count 个下标 i则- 当前位产生的置位(carry count) 1- 新进位(carry count) 1- 贡献C(leftM, count) · nums[i]^count复杂度 O(n · m² · k)由于 m ≤ 30, n ≤ 50完全可行。---javaclass Solution {private static final int MOD 1_000_000_007;private Integer[][][][] memo;private int[][] comb;private int[] nums;public int magicalSum(int m, int k, int[] nums) {this.nums nums;int n nums.length;// 预处理组合数 C[i][j] C(i, j)comb new int[m 1][m 1];for (int i 0; i m; i) {comb[i][0] 1;for (int j 1; j i; j) {comb[i][j] (comb[i - 1][j - 1] comb[i - 1][j]) % MOD;}}// 记忆化: memo[remainingM][remainingK][index][carry]// carry 的范围为 [0, m]因为每次进位 (carry count) 1 mmemo new Integer[m 1][k 1][n 1][m 1];return dp(m, k, 0, 0);}private int dp(int remainingM, int remainingK, int i, int carry) {// 剪枝即使剩余所有位都产生置位也不够 leftKint bits Integer.bitCount(carry);if (remainingM 0 || remainingK 0 || bits remainingM remainingK) {return 0;}// 已选完所有数检查进位中是否恰好还有 remainingK 个置位if (remainingM 0) {return remainingK bits ? 1 : 0;}// 没有更多数字可选但还没选够if (i nums.length) {return 0;}if (memo[remainingM][remainingK][i][carry] ! null) {return memo[remainingM][remainingK][i][carry];}long res 0;for (int count 0; count remainingM; count) {// 从剩余 remainingM 个位置中选 count 个放 nums[i]long contribution (long) comb[remainingM][count] * modPow(nums[i], count) % MOD;int newCarry carry count;int next dp(remainingM - count, remainingK - (newCarry 1), i 1, newCarry 1);res (res next * contribution) % MOD;}memo[remainingM][remainingK][i][carry] (int) res;return (int) res;}private long modPow(long base, int exp) {long res 1;while (exp 0) {if ((exp 1) 1) {res res * base % MOD;}base base * base % MOD;exp 1;}return res;}}---验证- 示例 1m5, k5, nums[1,10,100,10000,1000000] → 991600007 ✓- 示例 2m2, k2, nums[5,4,3,2,1] → 170 ✓- 示例 3m1, k1, nums[28] → 28 ✓
