这是 LeetCode 3539. 魔法序列的数组乘积之和 的 Rust 实现。思路本题是组合数学 记忆化搜索。核心观察 枚举每个 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, remainingM, remainingK, carry) 表示- 处理到第 i 个元素- 还需选 remainingM 个数- 当前低位向第 i 位的进位为 carry即 sum i- 还需满足 remainingK 个置位转移 枚举选 count 个下标 i则- 当前位产生的置位(carry count) 1- 新进位(carry count) 1- 贡献C(remainingM, count) · nums[i]^count复杂度 O(n · m² · k)由于 m ≤ 30, n ≤ 50完全可行。---rustimpl Solution {pub fn magical_sum(m: i32, k: i32, nums: Veci32) - i32 {const MOD: i64 1_000_000_007;let m m as usize;let k k as usize;let n nums.len();// 预处理组合数 C[i][j] C(i, j)let mut comb vec![vec![0i64; m 1]; m 1];for i in 0..m {comb[i][0] 1;for j in 1..i {comb[i][j] (comb[i - 1][j - 1] comb[i - 1][j]) % MOD;}}// memo[i][rem_m][rem_k][carry]-1 表示未计算let mut memo vec![vec![vec![vec![-1i64; m 1]; k 1]; m 1]; n 1];fn dfs(i: i32, rem_m: i32, rem_k: i32, carry: i32,n: i32, nums: Veci32, comb: VecVeci64,memo: mut VecVecVecVeci64,mod_val: i64,) - i64 {let bits carry.count_ones() as i32;// 剪枝即使剩余所有位都产生置位也不够 rem_kif rem_m 0 || rem_k 0 || bits rem_m rem_k {return 0;}// 已选完所有数检查进位中是否恰好还有 rem_k 个置位if rem_m 0 {return if rem_k bits { 1 } else { 0 };}// 没有更多数字可选但还没选够if i n {return 0;}let ui i as usize;let um rem_m as usize;let uk rem_k as usize;let uc carry as usize;if memo[ui][um][uk][uc] ! -1 {return memo[ui][um][uk][uc];}let mut res 0i64;for count in 0..rem_m {// 从剩余 rem_m 个位置中选 count 个放 nums[i]let contribution comb[um][count as usize]* mod_pow(nums[i as usize] as i64, count as usize, mod_val)% mod_val;let new_carry carry count;let next dfs(i 1,rem_m - count,rem_k - (new_carry 1),new_carry 1,n, nums, comb, memo, mod_val,);res (res next * contribution) % mod_val;}memo[ui][um][uk][uc] res;res}fn mod_pow(mut base: i64, mut exp: usize, mod_val: i64) - i64 {let mut res 1i64;while exp 0 {if exp 1 1 {res res * base % mod_val;}base base * base % mod_val;exp 1;}res}dfs(0, m as i32, k as i32, 0, n as i32, nums, comb, mut memo, MOD) as i32}}---验证- 示例 1m5, k5, nums[1,10,100,10000,1000000] → 991600007 ✓- 示例 2m2, k2, nums[5,4,3,2,1] → 170 ✓- 示例 3m1, k1, nums[28] → 28 ✓