这是 LeetCode 3539. 魔法序列的数组乘积之和 的 Python3 实现。思路本题是组合数学 记忆化搜索。核心观察 枚举每个 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完全可行。---pythonfrom typing import Listfrom functools import lru_cacheclass Solution:def magicalSum(self, m: int, k: int, nums: List[int]) - int:MOD 1_000_000_007n len(nums)# 预处理组合数 C[i][j] C(i, j)comb [[0] * (m 1) for _ in range(m 1)]for i in range(m 1):comb[i][0] 1for j in range(1, i 1):comb[i][j] (comb[i - 1][j - 1] comb[i - 1][j]) % MODlru_cache(None)def dp(i: int, remainingM: int, remainingK: int, carry: int) - int:bits carry.bit_count()# 剪枝即使剩余所有位都产生置位也不够 remainingKif remainingM 0 or remainingK 0 or bits remainingM remainingK:return 0# 已选完所有数检查进位中是否恰好还有 remainingK 个置位if remainingM 0:return 1 if remainingK bits else 0# 没有更多数字可选但还没选够if i n:return 0res 0for count in range(remainingM 1):# 从剩余 remainingM 个位置中选 count 个放 nums[i]contribution comb[remainingM][count] * pow(nums[i], count, MOD) % MODnewCarry carry countnxt dp(i 1, remainingM - count, remainingK - (newCarry 1), newCarry 1)res (res nxt * contribution) % MODreturn resreturn dp(0, m, k, 0)---验证- 示例 1m5, k5, nums[1,10,100,10000,1000000] → 991600007 ✓- 示例 2m2, k2, nums[5,4,3,2,1] → 170 ✓- 示例 3m1, k1, nums[28] → 28 ✓