Find Sum of Array Product of Magical Sequences

Problem

You are given two integers, m and k, and an integer array nums.

A sequence of integers seq is called magical if:

seq has a size of m.
0 <= seq[i] < nums.length
The binary representation of 2seq[0] + 2seq[1] + ... + 2seq[m - 1] has k set bits.

The array product of this sequence is defined as prod(seq) = (nums[seq[0]] * nums[seq[1]] * ... * nums[seq[m - 1]]).

Return the sum of the array products for all valid magical sequences.

Since the answer may be large, return it modulo 10^9 + 7.

A set bit refers to a bit in the binary representation of a number that has a value of 1.

Example 1

1
2
3
4
5


Input: m = 5, k = 5, nums = [1,10,100,10000,1000000]
Output: 991600007
Explanation:
All permutations of `[0, 1, 2, 3, 4]` are magical sequences, each with an
array product of 1013.

Example 2

1
2
3
4
5
6


Input: m = 2, k = 2, nums = [5,4,3,2,1]
Output: 170
Explanation:
The magical sequences are `[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]`, and `[4, 3]`.

Example 3

1
2
3
4


Input: m = 1, k = 1, nums = [28]
Output: 28
Explanation:
The only magical sequence is `[0]`.

Constraints

1 <= k <= m <= 30
1 <= nums.length <= 50
1 <= nums[i] <= 10^8

Examples

Solution

Method 1 – Bitmask Enumeration and Combinatorics

Intuition

We need to count all sequences of length m (with possible repeated indices) such that the sum of 2^seq[i] for i in 0..m-1 has exactly k set bits. For each such sequence, we multiply the corresponding nums values and sum the products. Since m and nums.length are small, we can enumerate all possible multisets using combinatorics and bitmasking.

Approach

For each possible multiset of indices (with repetition) of length m, count the number of ways to arrange them (multinomial coefficient).
For each multiset, compute the sum of 2^i * count[i] for all i.
If the number of set bits in this sum is k, compute the product of nums[i]^count[i] for all i.
Multiply the product by the multinomial coefficient and add to the answer.
Use recursion with memoization to efficiently enumerate all multisets.

Code

 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


class Solution {
public:
    int findSumOfArrayProductOfMagicalSequences(int m, int k, vector<int>& nums) {
        const int MOD = 1e9 + 7, n = nums.size();
        vector<vector<long long>> C(m+1, vector<long long>(m+1, 0));
        for (int i = 0; i <= m; ++i) {
            C[i][0] = 1;
            for (int j = 1; j <= i; ++j)
                C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
        long long ans = 0;
        function<void(int, int, vector<int>&)> dfs = [&](int pos, int left, vector<int>& cnt) {
            if (pos == n) {
                if (left == 0) {
                    long long sum = 0, prod = 1, ways = 1, total = m;
                    for (int i = 0; i < n; ++i) {
                        sum += (1LL << i) * cnt[i];
                        for (int j = 0; j < cnt[i]; ++j)
                            prod = prod * nums[i] % MOD;
                        ways = ways * C[total][cnt[i]] % MOD;
                        total -= cnt[i];
                    }
                    if (__builtin_popcountll(sum) == k)
                        ans = (ans + prod * ways % MOD) % MOD;
                }
                return;
            }
            for (int i = 0; i <= left; ++i) {
                cnt[pos] = i;
                dfs(pos+1, left-i, cnt);
            }
        };
        vector<int> cnt(n, 0);
        dfs(0, m, cnt);
        return ans;
    }
};

 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


func findSumOfArrayProductOfMagicalSequences(m int, k int, nums []int) int {
    MOD := int(1e9 + 7)
    n := len(nums)
    C := make([][]int, m+1)
    for i := range C {
        C[i] = make([]int, m+1)
        C[i][0] = 1
        for j := 1; j <= i; j++ {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD
        }
    }
    var ans int
    var dfs func(pos, left int, cnt []int)
    dfs = func(pos, left int, cnt []int) {
        if pos == n {
            if left == 0 {
                sum, prod, ways, total := 0, 1, 1, m
                for i := 0; i < n; i++ {
                    sum += (1 << i) * cnt[i]
                    for j := 0; j < cnt[i]; j++ {
                        prod = prod * nums[i] % MOD
                    }
                    ways = ways * C[total][cnt[i]] % MOD
                    total -= cnt[i]
                }
                if bits.OnesCount(uint(sum)) == k {
                    ans = (ans + prod*ways%MOD) % MOD
                }
            }
            return
        }
        for i := 0; i <= left; i++ {
            cnt[pos] = i
            dfs(pos+1, left-i, cnt)
        }
    }
    cnt := make([]int, n)
    dfs(0, m, cnt)
    return ans
}

 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


class Solution {
    public int findSumOfArrayProductOfMagicalSequences(int m, int k, int[] nums) {
        int MOD = 1_000_000_007, n = nums.length;
        long[][] C = new long[m+1][m+1];
        for (int i = 0; i <= m; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++)
                C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
        long[] ans = new long[1];
        int[] cnt = new int[n];
        dfs(0, m, cnt, nums, k, C, ans, MOD);
        return (int)ans[0];
    }
    void dfs(int pos, int left, int[] cnt, int[] nums, int k, long[][] C, long[] ans, int MOD) {
        int n = nums.length;
        if (pos == n) {
            if (left == 0) {
                long sum = 0, prod = 1, ways = 1, total = m;
                for (int i = 0; i < n; i++) {
                    sum += ((long)1 << i) * cnt[i];
                    for (int j = 0; j < cnt[i]; j++)
                        prod = prod * nums[i] % MOD;
                    ways = ways * C[(int)total][cnt[i]] % MOD;
                    total -= cnt[i];
                }
                if (Long.bitCount(sum) == k)
                    ans[0] = (ans[0] + prod * ways % MOD) % MOD;
            }
            return;
        }
        for (int i = 0; i <= left; i++) {
            cnt[pos] = i;
            dfs(pos+1, left-i, cnt, nums, k, C, ans, MOD);
        }
    }
}

 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


class Solution {
    fun findSumOfArrayProductOfMagicalSequences(m: Int, k: Int, nums: IntArray): Int {
        val MOD = 1_000_000_007
        val n = nums.size
        val C = Array(m+1) { LongArray(m+1) }
        for (i in 0..m) {
            C[i][0] = 1L
            for (j in 1..i) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD
        }
        var ans = 0L
        val cnt = IntArray(n)
        fun dfs(pos: Int, left: Int) {
            if (pos == n) {
                if (left == 0) {
                    var sum = 0L
                    var prod = 1L
                    var ways = 1L
                    var total = m
                    for (i in 0 until n) {
                        sum += (1L shl i) * cnt[i]
                        repeat(cnt[i]) { prod = prod * nums[i] % MOD }
                        ways = ways * C[total][cnt[i]] % MOD
                        total -= cnt[i]
                    }
                    if (sum.countOneBits() == k)
                        ans = (ans + prod * ways % MOD) % MOD
                }
                return
            }
            for (i in 0..left) {
                cnt[pos] = i
                dfs(pos+1, left-i)
            }
        }
        dfs(0, m)
        return ans.toInt()
    }
}

 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


class Solution:
    def findSumOfArrayProductOfMagicalSequences(self, m: int, k: int, nums: list[int]) -> int:
        from math import comb
        MOD = 10**9 + 7
        n = len(nums)
        ans = 0
        cnt = [0] * n
        def dfs(pos: int, left: int):
            nonlocal ans
            if pos == n:
                if left == 0:
                    s = sum((1 << i) * cnt[i] for i in range(n))
                    if bin(s).count('1') == k:
                        prod = 1
                        total = m
                        ways = 1
                        for i in range(n):
                            prod = prod * pow(nums[i], cnt[i], MOD) % MOD
                            ways = ways * comb(total, cnt[i]) % MOD
                            total -= cnt[i]
                        ans = (ans + prod * ways) % MOD
                return
            for i in range(left + 1):
                cnt[pos] = i
                dfs(pos + 1, left - i)
        dfs(0, m)
        return ans

 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


impl Solution {
    pub fn find_sum_of_array_product_of_magical_sequences(m: i32, k: i32, nums: Vec<i32>) -> i32 {
        fn comb(n: i32, k: i32) -> i64 {
            let mut res = 1i64;
            for i in 0..k {
                res = res * (n - i) as i64 / (i + 1) as i64;
            }
            res
        }
        let n = nums.len();
        let m = m as usize;
        let k = k as usize;
        let mut ans = 0i64;
        let mut cnt = vec![0; n];
        const MOD: i64 = 1_000_000_007;
        fn dfs(pos: usize, left: usize, n: usize, m: usize, k: usize, nums: &Vec<i32>, cnt: &mut Vec<usize>, ans: &mut i64) {
            if pos == n {
                if left == 0 {
                    let mut sum = 0u64;
                    let mut prod = 1i64;
                    let mut total = m as i32;
                    let mut ways = 1i64;
                    for i in 0..n {
                        sum += (1u64 << i) * cnt[i] as u64;
                        for _ in 0..cnt[i] {
                            prod = prod * nums[i] as i64 % MOD;
                        }
                        ways = ways * comb(total, cnt[i] as i32) % MOD;
                        total -= cnt[i] as i32;
                    }
                    if sum.count_ones() as usize == k {
                        *ans = (*ans + prod * ways % MOD) % MOD;
                    }
                }
                return;
            }
            for i in 0..=left {
                cnt[pos] = i;
                dfs(pos+1, left-i, n, m, k, nums, cnt, ans);
            }
        }
        dfs(0, m, n, m, k, &nums, &mut cnt, &mut ans);
        ans as i32
    }
}

 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


class Solution {
    findSumOfArrayProductOfMagicalSequences(m: number, k: number, nums: number[]): number {
        const MOD = 1e9 + 7, n = nums.length;
        function comb(n: number, k: number): number {
            let res = 1;
            for (let i = 0; i < k; ++i) res = res * (n - i) / (i + 1);
            return Math.round(res);
        }
        let ans = 0;
        const cnt = new Array(n).fill(0);
        function dfs(pos: number, left: number) {
            if (pos === n) {
                if (left === 0) {
                    let sum = 0, prod = 1, total = m, ways = 1;
                    for (let i = 0; i < n; ++i) {
                        sum += (1 << i) * cnt[i];
                        prod = prod * Math.pow(nums[i], cnt[i]) % MOD;
                        ways = ways * comb(total, cnt[i]) % MOD;
                        total -= cnt[i];
                    }
                    if (sum.toString(2).split('1').length - 1 === k)
                        ans = (ans + prod * ways % MOD) % MOD;
                }
                return;
            }
            for (let i = 0; i <= left; ++i) {
                cnt[pos] = i;
                dfs(pos + 1, left - i);
            }
        }
        dfs(0, m);
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n^m), since we enumerate all multisets of length m from n elements (with repetition), but for small m and n this is feasible.
🧺 Space complexity: O(m + n), for recursion stack and counters.

Problem#

Example 1#

Example 2#

Example 3#

Constraints#

Examples#

Solution#

Method 1 – Bitmask Enumeration and Combinatorics#

Intuition#

Approach#

Code#

Complexity#