时间轴

2025-10-12

init

题目：

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

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

尝试穷举

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#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 的排列数：

长度为 M 的排列数公式

不考虑重复数字的排列数

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

考虑重复数字

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

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

数组乘积

数组乘积公式

序列的数组乘积定义为：

  • 如果数字 i 在序列中出现了 r_i 次，则乘积可以写成：
  • 结合排列数，某一序列{ r0, r_1, r_2, … ,r{n-1} }序列总贡献为：
  • 解释：
    • 每种长度为 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]
  • 新状态：
  • p/2 和 p%2 的作用：
    • 模拟 mask 的二进制从低位到高位拆开
    • p % 2 = 低位的置位数
    • p / 2 = 上移一位后的 mask

初始化

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

结果

  • mask 总置位数 = 高位 mask 的置位数 + 低位 q 
1
2
if (__builtin_popcount(p) + q == K)
    res += f[n-1][M][p][q] * M!

代码实现

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

快速幂

核心思想

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

也就是说：

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

举例

假设我们要计算：

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

所以：

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

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

所以：

对应算法逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
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）：

所以：

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

也就是说：

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

最终代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#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;
  }
};