时间轴

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;
  }
};

动态规划

这题题解还是用动态规划

我们要做的是：

  • 给定数组 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! 种排列（因为重复数字排列不算新的序列）
    • 所以 乘起来就是该组合的总贡献

动态规划思路

  • 枚举所有可能的 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!

代码实现

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
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;
        vector<long long> fac(m + 1, 1);
        for (int i = 1; i <= m; i++) {
            fac[i] = fac[i - 1] * i % mod;
        }
        vector<long long> ifac(m + 1, 1);
        for (int i = 2; i <= m; i++) {
            ifac[i] = quickmul(i, mod - 2, mod);
        }
        for (int i = 2; i <= m; i++) {
            ifac[i] = ifac[i - 1] * ifac[i] % mod;
        }
        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;
    }
};