Kimi LeetCode 3539. 魔法序列的数组乘积之和 Go实现

这是 LeetCode 3539. 魔法序列的数组乘积之和 的 Go 实现。思路本题是组合数学 记忆化搜索。核心观察 枚举每个 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完全可行。---gopackage mainimport math/bitsfunc magicalSum(m int, k int, nums []int) int {const MOD int 1_000_000_007n : len(nums)// 预处理组合数 C[i][j] C(i, j)comb : make([][]int, m1)for i : 0; i m; i {comb[i] make([]int, m1)comb[i][0] 1for j : 1; j i; j {comb[i][j] (comb[i-1][j-1] comb[i-1][j]) % MOD}}// memo[i][remM][remK][carry]-1 表示未计算memo : make([][][][]int, n1)for i : range memo {memo[i] make([][][]int, m1)for j : range memo[i] {memo[i][j] make([][]int, k1)for l : range memo[i][j] {memo[i][j][l] make([]int, m1)for c : range memo[i][j][l] {memo[i][j][l][c] -1}}}}var dfs func(i, remM, remK, carry int) intdfs func(i, remM, remK, carry int) int {bits : bits.OnesCount32(uint32(carry))// 剪枝即使剩余所有位都产生置位也不够 remKif remM 0 || remK 0 || bitsremM remK {return 0}// 已选完所有数检查进位中是否恰好还有 remK 个置位if remM 0 {if remK bits {return 1}return 0}// 没有更多数字可选但还没选够if i n {return 0}if memo[i][remM][remK][carry] ! -1 {return memo[i][remM][remK][carry]}res : 0for count : 0; count remM; count {// 从剩余 remM 个位置中选 count 个放 nums[i]contribution : comb[remM][count] * modPow(nums[i], count, MOD) % MODnewCarry : carry countnext : dfs(i1, remM-count, remK-(newCarry1), newCarry1)res (res next*contribution) % MOD}memo[i][remM][remK][carry] resreturn res}return dfs(0, m, k, 0)}func modPow(base, exp, mod int) int {res : 1b : base % mode : expfor e 0 {if e1 1 {res res * b % mod}b b * b % mode 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 ✓