Hard
题目描述
给定两个整数 m 和 k，以及一个整数数组 nums。
如果一个整数序列 seq 满足以下条件，则称其为神奇的：
seq的大小为m0 <= seq[i] < nums.length2^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 的位。
示例 1：
输入：m = 5, k = 5, nums = [1,10,100,10000,1000000]
输出：991600007
解释：[0, 1, 2, 3, 4] 的所有排列都是神奇序列，每个的数组乘积都是 10^13。
示例 2：
输入：m = 2, k = 2, nums = [5,4,3,2,1]
输出：170
解释：神奇序列有 [0, 1], [0, 2], [0, 3], [0, 4], [1, 0], [1, 2], [1, 3], [1, 4], [2, 0], [2, 1], [2, 3], [2, 4], [3, 0], [3, 1], [3, 2], [3, 4], [4, 0], [4, 1], [4, 2], [4, 3]。
示例 3：
输入：m = 1, k = 1, nums = [28]
输出：28
解释：唯一的神奇序列是 [0]。
约束：
1 <= k <= m <= 301 <= nums.length <= 501 <= nums[i] <= 10^8
解题思路
这是一道结合了动态规划、位运算和组合数学的复杂题目。
核心思路：
题目要求找出所有长度为 m 的序列，使得 2^seq[0] + 2^seq[1] + ... + 2^seq[m-1] 的二进制表示恰好有 k 个1。
关键观察：当我们计算多个2的幂次的和时，会产生进位现象。例如 2^1 + 2^1 = 2^2，这样原本应该有2个1位的和变成了只有1个1位。
动态规划状态设计：
使用 dp[i][j][mask] 表示：
i：已选择的数字个数j：当前和的二进制表示中的1位个数mask：低位的进位状态（表示哪些位上有未处理的进位）
对于每个状态，我们需要跟踪两个值：
- 达到该状态的方案数
- 达到该状态的所有乘积之和
状态转移：
对于每个可选的索引，我们需要：
- 计算新的进位状态
- 更新1位的个数
- 累加方案数和乘积和
组合数学优化：
当数组中有重复元素时，我们可以用组合数学来优化计算，避免重复枚举相同的排列。
最终答案是所有满足条件状态（选择了 m 个数且恰好有 k 个1位）的乘积和。
代码实现
class Solution {
public:
int magicalSum(int m, int k, vector<int>& nums) {
const int MOD = 1e9 + 7;
int n = nums.size();
// dp[i][j][mask] = {count, sum}
map<tuple<int, int, int>, pair<long long, long long>> dp;
dp[{0, 0, 0}] = {1, 1};
for (int i = 0; i < m; i++) {
map<tuple<int, int, int>, pair<long long, long long>> next_dp;
for (auto& [state, val] : dp) {
auto [pos, bits, mask] = state;
auto [count, sum] = val;
for (int j = 0; j < n; j++) {
int new_mask = mask | (1 << j);
int new_bits = bits;
// Calculate carries
int carry_mask = mask & (1 << j) ? mask : 0;
if (mask & (1 << j)) {
new_mask &= ~(1 << j);
carry_mask = mask;
} else {
new_bits++;
}
// Process carries
while (carry_mask) {
int next_carry = 0;
for (int bit = 0; bit < 30; bit++) {
if (carry_mask & (1 << bit)) {
if (new_mask & (1 << (bit + 1))) {
next_carry |= (1 << (bit + 1));
} else {
new_mask |= (1 << (bit + 1));
new_bits++;
}
new_mask &= ~(1 << bit);
new_bits--;
}
}
carry_mask = next_carry;
}
auto new_state = make_tuple(i + 1, new_bits, new_mask);
long long new_count = (count * 1) % MOD;
long long new_sum = (sum * nums[j]) % MOD;
if (next_dp.find(new_state) != next_dp.end()) {
next_dp[new_state].first = (next_dp[new_state].first + new_count) % MOD;
next_dp[new_state].second = (next_dp[new_state].second + new_sum) % MOD;
} else {
next_dp[new_state] = {new_count, new_sum};
}
}
}
dp = next_dp;
}
long long result = 0;
for (auto& [state, val] : dp) {
auto [pos, bits, mask] = state;
if (pos == m && bits == k && mask == 0) {
result = (result + val.second) % MOD;
}
}
return result;
}
};
class Solution:
def magicalSum(self, m: int, k: int, nums: List[int]) -> int:
MOD = 10**9 + 7
n = len(nums)
# dp[i][j][mask] = (count, sum)
dp = {(0, 0, 0): (1, 1)}
for i in range(m):
next_dp = {}
for (pos, bits, mask), (count, total_sum) in dp.items():
for j in range(n):
new_mask = mask
new_bits = bits
if mask & (1 << j):
# There's already a carry at position j
new_mask &= ~(1 << j) # Remove the bit
# Process carry
carry_pos = j
while carry_pos < 30:
if new_mask & (1 << (carry_pos + 1)):
new_mask &= ~(1 << (carry_pos + 1))
carry_pos += 1
else:
new_mask |= (1 << (carry_pos + 1))
break
else:
# No carry, just set the bit
new_mask |= (1 << j)
new_bits += 1
# Count set bits in final mask
final_bits = new_bits
temp_mask = new_mask
while temp_mask:
if temp_mask & 1:
final_bits += 1
temp_mask >>= 1
# Only consider states with reasonable bit counts
if final_bits <= k:
new_state = (i + 1, new_bits, new_mask)
new_count = count % MOD
new_sum = (total_sum * nums[j]) % MOD
if new_state in next_dp:
next_dp[new_state] = (
(next_dp[new_state][0] + new_count) % MOD,
(next_dp[new_state][1] + new_sum) % MOD
)
else:
next_dp[new_state] = (new_count, new_sum)
dp = next_dp
result = 0
for (pos, bits, mask), (count, total_sum) in dp.items():
if pos == m and bits == k and mask == 0:
result = (result + total_sum) % MOD
return result
public class Solution {
public int MagicalSum(int m, int k, int[] nums) {
const int MOD = 1000000007;
int n = nums.Length;
var dp = new Dictionary<(int, int, int), (long, long)>();
dp[(0, 0, 0)] = (1, 1);
for (int i = 0; i < m; i++) {
var nextDp = new Dictionary<(int, int, int), (long, long)>();
foreach (var kvp in dp) {
var (pos, bits, mask) = kvp.Key;
var (count, sum) = kvp.Value;
for (int j = 0; j < n; j++) {
int newMask = mask;
int newBits = bits;
if ((mask & (1 << j)) != 0) {
newMask &= ~(1 << j);
int carryPos = j;
while (carryPos < 30) {
if ((newMask & (1 << (carryPos + 1))) != 0) {
newMask &= ~(1 << (carryPos + 1));
carryPos++;
} else {
newMask |= (1 << (carryPos + 1));
break;
}
}
} else {
newMask |= (1 << j);
newBits++;
}
int finalBits = newBits;
int tempMask = newMask;
while (tempMask > 0) {
if ((tempMask & 1) == 1) {
finalBits++;
}
tempMask >>= 1;
}
if (finalBits <= k) {
var newState = (i + 1, newBits, newMask);
long newCount = count % MOD;
long newSum = (sum * nums[j]) % MOD;
if (nextDp.ContainsKey(newState)) {
var existing = nextDp[newState];
nextDp[newState] = (
(existing.Item1 + newCount) % MOD,
(existing.Item2 + newSum) % MOD
);
} else {
nextDp[newState] = (newCount, newSum);
}
}
}
}
dp = nextDp;
}
long result = 0;
foreach (var kvp in dp) {
var (pos, bits, mask) = kvp.Key;
if (pos == m && bits == k && mask == 0) {
result = (result + kvp.Value.Item2) % MOD;
}
}
return (int)result;
}
}
var magicalSum = function(m, k, nums) {
const MOD = 1e9 + 7;
const n = nums.length;
let dp = new Map();
dp.set('0,0,0', [1, 1]);
for (let i = 0; i < m; i++) {
const nextDp = new Map();
for (const [key, [count, sum]] of dp) {
const [pos, bits, mask] = key.split(',').map(Number);
for (let j = 0; j < n; j++) {
let newMask = mask;
let newBits = bits;
if (mask & (1 << j)) {
newMask &= ~(1 << j);
let carryPos = j;
while (carryPos < 30) {
if (newMask & (1 << (carryPos + 1))) {
newMask &= ~(1 << (carryPos + 1));
carryPos++;
} else {
newMask |= (1 << (carryPos + 1));
break;
}
}
} else {
newMask |= (1 << j);
newBits++;
}
let finalBits = newBits;
let tempMask = newMask;
while (tempMask > 0) {
if (tempMask & 1) {
finalBits++;
}
tempMask >>= 1;
}
if (finalBits <= k) {
const newKey = `${i + 1},${newBits},${newMask}`;
const newCount = count % MOD;
const newSum = (sum * nums[j]) % MOD;
if (nextDp.has(newKey)) {
const [existingCount, existingSum] = nextDp.get(newKey);
nextDp.set(newKey, [
(existingCount + newCount) % MOD,
(existingSum + newSum) % MOD
]);
} else {
nextDp.set(newKey, [newCount, newSum]);
}
}
}
}
dp = nextDp;
}
let result = 0;
for (const [key, [count, sum]] of dp) {
const [pos, bits, mask]
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |