leetcode每日一题 P3539 魔法序列的数组乘积之和

---

时间轴

时间轴

2025-10-12

init

用DP模拟二进制加法进位规律的组合计数题，高阶动态规划，__builtin_popcount

---

题目：

P3539 魔法序列的数组乘积之和

https://leetcode.cn/problems/find-sum-of-array-product-of-magical-sequences/?envType=daily-question&envId=2025-10-12

尝试穷举

我最开始只想到了穷举，但是穷举也没穷举完整，难受了

#include <algorithm>
#include <stack>
#include <vector>

using std::stack;
using std::vector;

const int MOD = 1000000007; // 10^9 + 7

class Solution {
    public:
        bool magicalSeq(vector<int> &seq, int m, int k, int length)
        {
                // 魔法序列：seq 的序列长度为 m。
                // 0 <= seq[i] < nums.length
                // 2^seq[0] + 2^seq[1] + ... + 2^seq[m - 1] 的 二进制形式 有 m 个 置位。
                // 也就是说{seq[0], seq[1] ..seq[M-1]}中,如果两个数相同
                // 递归地将相同的数合并成一个原来的数值+1，直到没有相同地数为止
                int val;
                int set = 0;
                if (seq.size() != m) {
                        return false;
                }

                std::sort(seq.begin(), seq.end());

                if (seq[0] < 0 || seq[m - 1] >= length) {
                        return false;
                }

                stack<int, std::vector<int> > st(seq);

                while (!st.empty()) {
                        val = st.top();
                        st.pop();
                        set++;
                        if (!st.empty() && val == st.top()) {
                                st.top()++;
                                set--;
                        }
                }

                if (set == k) {
                        return true;
                } else {
                        return false;
                }
        }

        int magicalSum(int m, int k, vector<int> &nums)
        {
                int i, j;
                int n = nums.size();
                unsigned long magical_sum = 0;
                unsigned long array_mul;

                vector<vector<int> > result;
                int res_size;

                if (m <= n) {
                        // 生成长度为m的nums的所有子序列
                        // predict数组，类似于SVE指令
                        vector<int> predict(n, 0);
                        // 从字典序最小的开始
                        std::fill(predict.end() - m, predict.end(), 1);

                        do {
                                vector<int> tmp;
                                for (i = 0; i < n; i++) {
                                        if (predict[i] != 0) {
                                                tmp.push_back(i);
                                        }
                                }

                                result.push_back(tmp);
                        } while (std::next_permutation(predict.begin(), predict.end()));
                }

                res_size = result.size();
                // 判断是不是magic sequence
                for (i = 0; i < res_size; i++) {
                        if (magicalSeq(result[i], m, k, n)) {
                                // 如果是magic sequence，计算它的全排列的数组乘积
                                // 但如果数字相同，排列不同，数组乘积是一样的
                                // 因此直接乘以 m 的阶乘
                                array_mul = 1;
                                for (j = 0; j < m; j++) {
                                        array_mul = (array_mul * nums[result[i][j]]) % MOD;
                                }
                                for (j = 1; j <= m; j++) {
                                        array_mul = (array_mul * j) % MOD;
                                }
                                magical_sum = (magical_sum + array_mul) % MOD;
                        }
                }
                return magical_sum;
        }
};

动态规划

这题题解还是用动态规划，不过是高阶动态规划。

题目

给你两个整数M和K，和一个整数数组nums。

一个整数序列seq如果满足以下条件，被称为 魔法 序列：

• seq的序列长度为M。
• 0 <= seq[i] < nums.length
• 2^seq[0] + 2^seq[1] + ... + 2^seq[M - 1]的 二进制形式 有K个 置位。

这个序列的 数组乘积 定义为prod(seq) = (nums[seq[0]] * nums[seq[1]] * ... * nums[seq[M - 1]])。

返回所有有效 魔法 序列的 数组乘积 的 总和 。

由于答案可能很大，返回结果对10^9 + 7取模。

置位 是指一个数字的二进制表示中值为 1 的位。

我们要做的是：

• 给定数组nums，长度n
• 取长度为M的序列seq（可以重复选择 nums 中的元素）
• 条件：2^seq[0] + ... + 2^seq[M-1]二进制中有K个 1
• 数组乘积：prod(seq) = nums[seq[0]] * ... * nums[seq[M-1]]
• 目标：所有魔法序列数组乘积的和（mod 1e9+7）

序列排列数

假设我们从nums下标0..n-1取数：

• 每个数i取了r_i个
• 总数满足：r_0 + r_1 + ... + r_{n-1} = M

长度为 M 的排列数：

$$\frac{M!}{r_0! \, r_1! \, ... \, r_{n-1}!}$$

长度为 M 的排列数公式

不考虑重复数字的排列数

• 如果 所有数字都不同，长度为 M 的序列排列数就是 M!
  • 因为 M 个不同的元素可以有 M! 种排列

考虑重复数字

• 如果某些数字重复出现，例如：

$$seq = [a, a, b, b, b, c]$$

• 重复的数字交换不会产生新序列
• 在组合数学中，我们要 除以每个重复数字的阶乘，消除重复排列的影响
• 假设数字 i 出现了r_i次，总排列数公式为：

$$\text{排列数} = \frac{M!}{r_0! \, r_1! \, \dots \, r_{n-1}!}$$

这是经典的多重集排列公式：长度为 M 的排列数 = 总元素阶乘 / 每种重复元素的阶乘

数组乘积

$$\prod_{i=0}^{n-1} nums[i]^{r_i} \cdot \frac{M!}{r_0! \, r_1! \, ... \, r_{n-1}!}$$

数组乘积公式

序列的数组乘积定义为：

$$\text{prod(seq)} = nums[seq[0]] \cdot nums[seq[1]] \cdot \dots \cdot nums[seq[M-1]]$$

• 如果数字 i 在序列中出现了r_i次，则乘积可以写成：

$$\prod_{i=0}^{n-1} nums[i]^{r_i}$$

• 结合排列数，某一序列{ r0, r_1, r_2, … ,r }序列总贡献为：

$$\text{总贡献} = \frac{M!}{r_0! \, r_1! \, ... \, r_{n-1}!} \cdot \prod_{i=0}^{n-1} nums[i]^{r_i}$$

• 解释：
  • 每种长度为 M 的序列对应的数组乘积是∏ nums[i]^r_i
  • 总共有M! / ∏ r_i!种排列（因为重复数字排列不算新的序列）
  • 所以 乘起来就是该组合的总贡献

动态规划思路

用 DP 模拟二进制加法进位规律

• 枚举所有可能的r_i（每个数出现次数）很复杂
• 动态规划的思路：逐个考虑 nums 中的数字

状态定义

• f[i][j][p][q]表示：
  • 已考虑前i个数（nums[0…i]）
  • 已取总数j
  • 当前 mask(进位状态) 的低 i 位和为p
  • 低 i 位的置位数为q
  • 值 = 对应所有序列∏ r_t! * nums[t]^r_t的和，也就是所有这些情况的贡献之和

转移公式

当考虑第i+1个数：

• 假设选了r个nums[i+1]
• 新状态：

$$f[i+1][j+r][\lfloor p/2 \rfloor + r][q + (p \bmod 2)] += f[i][j][p][q] * nums[i+1]^r * r!$$

• p/2和p%2的作用：
  • 模拟 mask 的二进制从低位到高位拆开
  • p % 2= 低位的置位数
  • p / 2= 上移一位后的 mask

初始化

• 对i=0，也就是第一个数字：

$$f[0][j][j][0] = nums[0]^j * j!$$

• 低 0 位置位数 = 0

---

结果

• mask 总置位数 = 高位 mask 的置位数 + 低位 q

if (__builtin_popcount(p) + q == K)
    res += f[n-1][M][p][q] * M!

代码实现

代码中利用到了很多技巧，这里先介绍以下

快速幂

核心思想

利用指数的二进制表示和幂的拆分性质：

$$x^y = x^{(b_0·2^0 + b_1·2^1 + ... + b_k·2^k)} = \prod_{i | b_i=1} x^{2^i}$$

也就是说：

• 把y看成二进制；
• 每次平方底数，相当于翻倍指数；
• 如果当前二进制位是 1，就把这一项乘进结果

举例

假设我们要计算：

$$3^{13}$$

13 的二进制是：1101₂ = 8 + 4 + 0 + 1

所以：

$$3^{13} = 3^{8} × 3^{4} × 3^{1}$$

我们可以通过不断平方得到这些幂次：

步骤	幂次	结果
3¹	3
3²	9
3⁴	81
3⁸	6561

所以：

$$3^{13} = 3⁸ × 3⁴ × 3¹ = 6561 × 81 × 3 = 1594323$$

对应算法逻辑

long long quickPow(long long x, long long y) {
    long long res = 1;
    long long cur = x;  // 当前底数

    while (y > 0) {
        if (y & 1) {
            res *= cur;  // 当前位是1 → 把当前幂次乘进去
        }
        y >>= 1;         // 右移一位，相当于除以2
        cur *= cur;      // 底数平方 → 指数翻倍
    }
    return res;
}

费马小定理

根据费马小定理（Fermat’s Little Theorem）：

$$a^{p-1} ≡ 1 \pmod{p}$$

所以：

$$a^{p-2} ≡ a^{-1} \pmod{p}$$

费马小定理要求 p 必须是一个质数

也就是说：

一个数的模逆元 = 这个数的 (mod - 2) 次方 取模。

最终代码实现

#include <vector>
using std::vector;

class Solution {
    public:
        long long quickmul(long long x, long long y, long long mod)
        {
                long long res = 1, cur = x % mod;
                while (y) {
                        if (y & 1) {
                                res = res * cur % mod;
                        }
                        y >>= 1;
                        cur = cur * cur % mod;
                }
                return res;
        };

        int magicalSum(int m, int k, vector<int> &nums)
        {
                int n = nums.size();
                const long long mod = 1e9 + 7;

                // 计算1~m的阶乘
                vector<long long> fac(m + 1, 1);
                for (int i = 1; i <= m; i++) {
                        fac[i] = fac[i - 1] * i % mod;
                }
                // ifac[i]=(i!)^(−1) mod mod
                vector<long long> ifac(m + 1, 1);
                for (int i = 2; i <= m; i++) {
                        // 利用费马小定理计算每个i的模逆元
                        ifac[i] = quickmul(i, mod - 2, mod);
                }
                // 利用递推关系把单个整数的逆元变成阶乘逆元
                for (int i = 2; i <= m; i++) {
                        ifac[i] = ifac[i - 1] * ifac[i] % mod;
                }

                // numsPower[i][j] 表示 nums[i] 的 j 次幂模 mod
                // 如果i在序列中出现了j次，那么这个序列的乘积就是遍历所有序列i，
                // 累乘numsPower[i][j]
                vector numsPower(n, vector<long long>(m + 1, 1));
                for (int i = 0; i < n; i++) {
                        for (int j = 1; j <= m; j++) {
                                numsPower[i][j] = numsPower[i][j - 1] * nums[i] % mod;
                        }
                }

                vector f(n, vector(m + 1, vector(m * 2 + 1, vector<long long>(k + 1, 0))));

                for (int j = 0; j <= m; j++) {
                        f[0][j][j][0] = numsPower[0][j] * ifac[j] % mod;
                }

                for (int i = 0; i + 1 < n; i++) {
                        for (int j = 0; j <= m; j++) {
                                for (int p = 0; p <= m * 2; p++) {
                                        for (int q = 0; q <= k; q++) {
                                                int q2 = p % 2 + q;
                                                if (q2 > k) {
                                                        break;
                                                }
                                                for (int r = 0; r + j <= m; r++) {
                                                        int 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;
                                                }
                                        }
                                }
                        }
                }
                long long res = 0;
                for (int p = 0; p <= m * 2; p++) {
                        for (int q = 0; q <= k; q++) {
                                if (__builtin_popcount(p) + q == k) {
                                        res = (res + f[n - 1][m][p][q] * fac[m] % mod) % mod;
                                }
                        }
                }
                return res;
        }
};