2025-10-24：魔法序列的数组乘积之和。用go语言，给定一个整数 m、一个整数 k 以及一个数组 nums（长度记作 n）

福大大架构师每日一题

发布于 2025-12-18 15:45:36

930

2025-10-24：魔法序列的数组乘积之和。用go语言，给定一个整数 m、一个整数 k 以及一个数组 nums（长度记作 n）。考虑长度为 m 的下标序列 seq，其中每个元素都是 0 到 n-1 之间的整数（允许重复）。把这些下标对应的二次幂相加，即，如果这个和在二进制表示中恰好有 k 个 1 比特位，则称该下标序列为“魔法序列”。对于一个魔法序列，把对应的数组元素相乘得到它的数组乘积。题目要求把所有魔法序列的数组乘积加总，并将结果对 1000000007 取模后返回。

1 <= k <= m <= 30。

1 <= nums.length <= 50。

1 <= nums[i] <= 100000000。

输入: m = 5, k = 5, nums = [1,10,100,10000,1000000]。

输出: 991600007。

解释:

所有 [0, 1, 2, 3, 4] 的排列都是魔法序列，每个序列的数组乘积是 10000000000000。

题目来自力扣3539。

求解过程

1. 预处理阶段

• 阶乘预处理：计算 0 到 m 的阶乘 fac[i] 和阶乘的逆元 ifac[i]，用于后续的组合数计算
• 快速幂计算：实现快速模幂运算，用于计算逆元
• 元素幂次预处理：对每个数组元素 nums[i]，预计算其 0 到 m 次幂，避免重复计算

2. 动态规划状态设计

使用四维动态规划数组 f[i][j][p][q]：

• i：当前考虑到的数组元素索引（0 到 n-1）
• j：已经选择的元素总个数（0 到 m）
• p：当前二次幂和的"压缩表示"（0 到 2m）
• q：当前已经产生的进位计数（0 到 k）

3. 动态规划转移过程

• 初始状态：只考虑第一个数组元素，选择 j 个该元素，状态为 (j, j, 0)
• 状态转移：从第 i 个元素转移到第 i+1 个元素时：
- • 考虑选择 r 个 nums[i+1] 元素
- • 更新已选元素总数：j + r
- • 更新压缩状态：p2 = p/2 + r（模拟二进制加法进位）
- • 更新进位计数：q2 = p%2 + q（记录当前位的进位）
- • 贡献值乘以 nums[i+1]^r / r!（包含组合数因子）

4. 最终结果计算

遍历所有可能的最终状态 (m, p, q)：

• 检查条件：bits.OnesCount(p) + q == k
• 满足条件的状态贡献为 f[n-1][m][p][q] × m!（还原组合数因子）
• 将所有满足条件的贡献求和得到最终结果

算法核心思想

该解法巧妙地将二进制加法过程转化为状态转移：

• 用 p 模拟二进制加法过程中的中间结果
• 用 q 记录已经产生的进位数量
• 通过 p/2 和 p%2 模拟二进制位的移位和进位

复杂度分析

时间复杂度

• 状态数量：n × m × (2m) × k ≈ 50 × 30 × 60 × 30 = 2,700,000
• 每个状态的转移：最多 m 种选择（选择 0 到 m 个当前元素）
• 总时间复杂度：O(n × m³ × k)，大约为 50 × 30³ × 30 ≈ 40,500,000 次操作

空间复杂度

• DP 数组：n × m × (2m) × k ≈ 2,700,000 个状态
• 预处理数组：阶乘、逆元、幂次数组等，大小均为 O(m) 或 O(n×m)
• 总空间复杂度：O(n × m² × k)，主要来自四维 DP 数组

Go完整代码如下：

package main

import (
    "fmt"
    "math/bits"
)

func quickmul(x, y, mod int64) int64 {
    res, cur := int64(1), x%mod
    for y > 0 {
        if y&1 == 1 {
            res = res * cur % mod
        }
        y >>= 1
        cur = cur * cur % mod
    }
    return res
}

func magicalSum(m int, k int, nums []int) int {
    mod := int64(1000000007)
    fac := make([]int64, m+1)
    fac[0] = 1
    for i := 1; i <= m; i++ {
        fac[i] = fac[i-1] * int64(i) % mod
    }
    ifac := make([]int64, m+1)
    ifac[0] = 1
    ifac[1] = 1
    for i := 2; i <= m; i++ {
        ifac[i] = quickmul(int64(i), mod-2, mod)
    }
    for i := 2; i <= m; i++ {
        ifac[i] = ifac[i-1] * ifac[i] % mod
    }

    numsPower := make([][]int64, len(nums))
    for i := range nums {
        numsPower[i] = make([]int64, m+1)
        numsPower[i][0] = 1
        for j := 1; j <= m; j++ {
            numsPower[i][j] = numsPower[i][j-1] * int64(nums[i]) % mod
        }
    }

    f := make([][][][]int64, len(nums))
    for i := range nums {
        f[i] = make([][][]int64, m+1)
        for j := 0; j <= m; j++ {
            f[i][j] = make([][]int64, m*2+1)
            for p := 0; p <= m*2; p++ {
                f[i][j][p] = make([]int64, k+1)
            }
        }
    }

    for j := 0; j <= m; j++ {
        f[0][j][j][0] = numsPower[0][j] * ifac[j] % mod
    }
    for i := 0; i+1 < len(nums); i++ {
        for j := 0; j <= m; j++ {
            for p := 0; p <= m*2; p++ {
                for q := 0; q <= k; q++ {
                    q2 := p%2 + q
                    if q2 > k {
                        break
                    }
                    for r := 0; r+j <= m; r++ {
                        p2 := p/2 + r
                        f[i+1][j+r][p2][q2] += f[i][j][p][q] * numsPower[i+1][r] % mod * ifac[r] % mod
                        f[i+1][j+r][p2][q2] %= mod
                    }
                }
            }
        }
    }

    res := int64(0)
    for p := 0; p <= m*2; p++ {
        for q := 0; q <= k; q++ {
            if bits.OnesCount(uint(p))+q == k {
                res = (res + f[len(nums)-1][m][p][q]*fac[m]%mod) % mod
            }
        }
    }
    return int(res)
}

func main() {
    m := 5
    k := 5
    nums := []int{1, 10, 100, 10000, 1000000}
    result := magicalSum(m, k, nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

MOD = 1000000007

def quickmul(x, y, mod):
    res, cur = 1, x % mod
    while y > 0:
        if y & 1:
            res = res * cur % mod
        y >>= 1
        cur = cur * cur % mod
    return res

def magicalSum(m, k, nums):
    mod = MOD
    
    # 预计算阶乘
    fac = [1] * (m + 1)
    for i in range(1, m + 1):
        fac[i] = fac[i - 1] * i % mod
    
    # 预计算逆阶乘
    ifac = [1] * (m + 1)
    ifac[1] = 1
    for i in range(2, m + 1):
        ifac[i] = quickmul(i, mod - 2, mod)
    for i in range(2, m + 1):
        ifac[i] = ifac[i - 1] * ifac[i] % mod
    
    # 预计算nums的幂次
    nums_power = []
    for num in nums:
        powers = [1] * (m + 1)
        for j in range(1, m + 1):
            powers[j] = powers[j - 1] * num % mod
        nums_power.append(powers)
    
    n = len(nums)
    
    # 初始化四维DP数组
    # f[i][j][p][q] 表示前i+1个数，总共选了j次，当前p值，当前q值的方案数
    # 使用嵌套列表来模拟四维数组
    f = [[[[0] * (k + 1) for _ in range(m * 2 + 1)] for _ in range(m + 1)] for _ in range(n)]
    
    # 初始化第一个数
    for j in range(m + 1):
        f[0][j][j][0] = nums_power[0][j] * ifac[j] % mod
    
    # DP转移
    for i in range(n - 1):
        for j in range(m + 1):
            for p in range(m * 2 + 1):
                for q in range(k + 1):
                    if f[i][j][p][q] == 0:
                        continue
                    # 计算新的q值
                    q2 = p % 2 + q
                    if q2 > k:
                        continue
                    # 枚举下一个数选择的次数
                    for r in range(m + 1 - j):
                        p2 = p // 2 + r
                        if p2 <= m * 2:
                            f[i + 1][j + r][p2][q2] = (
                                f[i + 1][j + r][p2][q2] + 
                                f[i][j][p][q] * nums_power[i + 1][r] % mod * ifac[r] % mod
                            ) % mod
    
    # 计算结果
    res = 0
    for p in range(m * 2 + 1):
        for q in range(k + 1):
            # 检查条件：p的二进制中1的个数 + q == k
            if bin(p).count('1') + q == k:
                res = (res + f[n - 1][m][p][q] * fac[m] % mod) % mod
    
    return res

# 测试代码
if __name__ == "__main__":
    m = 5
    k = 5
    nums = [1, 10, 100, 10000, 1000000]
    result = magicalSum(m, k, nums)
    print(result)