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.

Examples

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

Solution

Method 1 - Naive brute-force enumeration (explanatory, no code)

Intuition

The most straightforward way is to generate every ordered sequence seq of length m where each element is an index in [0..n-1] (where n = nums.length), compute the integer S = sum(2^{seq[i]}) for that sequence, check if popcount(S) == k, and if so add the product nums[seq[0]] * ... * nums[seq[m-1]] to the running total (modulo 1e9+7). This is conceptually simple but quickly becomes infeasible because there are n^m ordered sequences.

Approach

  1. Recursively (or with m nested loops) enumerate every ordered sequence seq of length m. At each recursion depth you pick an index in 0..n-1.
  2. Maintain the running product of chosen nums values and the running integer sum of powers-of-two (S). When you reach depth m, compute popcount(S). If it equals k, add the product to the answer modulo MOD.
  3. Simple pruning: if at any point you detect that even with the best/worst possible remaining contributions you cannot reach k set bits, you could skip (but in the naive approach this pruning is weak).

Why this is insufficient in practice

  • The number of sequences is n^m. With constraints up to n = 50 and m = 30 the naive method is astronomically large and unusable.
  • Even for moderate values (e.g., n=10, m=10) it’s usually too slow.

Why memoization or combinatorics is needed (lead-in to Method 2)

  • There is a great deal of repeated work in the naive enumeration: different orderings that share the same counts of each index produce the same product up to permutation multiplicity, and the binary addition behavior depends only on counts (and carries), not on order.
  • Recasting the problem to iterate over counts of each index (a multiset view) and accounting for permutations with combinatorial coefficients reduces the search space dramatically. Likewise, memoizing states keyed by (remaining, odd_needed, idx, carry) (or equivalent) collapses repeated subproblems.

We’ll implement the memoized DP that uses these observations in Method 2, and then provide a bottom-up DP variant in Method 3.

Complexity

  • ⏰ Time complexity: O(n^m * m) – Enumerating every ordered sequence (n^m) and computing product/popcount for each sequence costs another O(m) per sequence; hence the naive upper bound is O(n^m * m).
  • 🧺 Space complexity: O(m) – recursion stack and O(m) temporary workspace for product/bit-sum calculations.

Method 2 - Memoized DP (carry-by-binary-digit + combinatorics)

Intuition

We can avoid enumerating every ordered sequence by processing indices one-by-one and choosing how many times to include each index (0..remaining). The binary sum’s behavior depends only on counts and carries per binary digit, and permutations of identical choices can be accounted for with combinatorics (binomial coefficients). Memoizing states keyed by (remaining, odd_needed, idx, carry) collapses repeated subproblems.

Approach

  1. Precompute combinatorics (either factorials/inverses or a Pascal table C) up to m, and optionally precompute pow(nums[i], t, MOD) for t in 0..m to avoid repeated exponentiation.
  2. Define a memoized recursion dfs(remaining, odd_needed, idx, carry) that returns the total sum of array-products modulo MOD for selecting exactly remaining items from indices idx..n-1 with current carry and still needing odd_needed set bits overall.
  3. For the current idx, iterate take from 0..remaining:
    • ways = C[remaining][take]
    • prod_contrib = nums[idx]^take % MOD
    • new_carry = carry + take
    • lsb = new_carry & 1 (this bit contributes to the current bitcount)
    • recurse on dfs(remaining - take, odd_needed - lsb, idx+1, new_carry >> 1) and multiply by ways * prod_contrib.
  4. Sum these contributions modulo MOD and memoize the result.

State Definition

  • dfs(remaining, odd_needed, idx, carry) returns the total modular sum of products for selecting remaining more elements from indices idx..n-1 with pending carry and odd_needed remaining set bits to form.

Recurrence Relation

1

ans = sum_{take=0..remaining} C(remaining, take) * nums[idx]^take * dfs(remaining-take, odd_needed - ((carry+take)&1), idx+1, (carry+take)>>1)

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
38
39
40
41
42

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int64 MOD = 1000000007LL;

class Solution {
public:
    int magicalSum(int m, int k, vector<int>& nums) {
        int n = nums.size();
        vector<vector<int64>> C(m + 1, vector<int64>(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;
        }

        vector<vector<int64>> pw(n, vector<int64>(m + 1, 1));
        for (int i = 0; i < n; ++i) for (int t = 1; t <= m; ++t) pw[i][t] = pw[i][t - 1] * nums[i] % MOD;

        unordered_map<string, int> memo;
        function<int(int,int,int,long long)> dfs = [&](int remaining, int oddNeeded, int idx, long long carry) -> int {
            if (remaining < 0 || oddNeeded < 0) return 0;
            if (remaining + __builtin_popcountll((unsigned long long)carry) < oddNeeded) return 0;
            if (remaining == 0) return (oddNeeded == (int)__builtin_popcountll((unsigned long long)carry)) ? 1 : 0;
            if (idx >= n) return 0;
            string key = to_string(remaining) + ":" + to_string(oddNeeded) + ":" + to_string(idx) + ":" + to_string(carry);
            if (memo.count(key)) return memo[key];
            int64 res = 0;
            for (int take = 0; take <= remaining; ++take) {
                int64 ways = C[remaining][take];
                int64 prod = pw[idx][take];
                long long nc = carry + take;
                int lsb = nc & 1LL;
                int sub = dfs(remaining - take, oddNeeded - lsb, idx + 1, nc >> 1);
                res = (res + ways % MOD * prod % MOD * sub) % MOD;
            }
            memo[key] = (int)res;
            return memo[key];
        };

        return dfs(m, k, 0, 0);
    }
};
 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

package main

import (
    "fmt"
    "strconv"
)

const MOD = 1000000007

func magicalSum(m int, k int, nums []int) int {
    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
        }
    }

    pw := make([][]int, n)
    for i := 0; i < n; i++ {
        pw[i] = make([]int, m+1)
        pw[i][0] = 1
        for t := 1; t <= m; t++ {
            pw[i][t] = int((int64(pw[i][t-1]) * int64(nums[i])) % MOD)
        }
    }

    memo := make(map[string]int)

    var dfs func(remaining, oddNeeded, idx int, carry int) int
    dfs = func(remaining, oddNeeded, idx int, carry int) int {
        if remaining < 0 || oddNeeded < 0 {
            return 0
        }
        if remaining + bitsSet(carry) < oddNeeded {
            return 0
        }
        if remaining == 0 {
            if oddNeeded == bitsSet(carry) {
                return 1
            }
            return 0
        }
        if idx >= n {
            return 0
        }
        key := strconv.Itoa(remaining) + ":" + strconv.Itoa(oddNeeded) + ":" + strconv.Itoa(idx) + ":" + strconv.Itoa(carry)
        if v, ok := memo[key]; ok { return v }
        res := 0
        for take := 0; take <= remaining; take++ {
            ways := C[remaining][take]
            prod := pw[idx][take]
            nc := carry + take
            lsb := nc & 1
            sub := dfs(remaining - take, oddNeeded - lsb, idx+1, nc>>1)
            res = (res + int((int64(ways) * int64(prod) % MOD) * int64(sub) % MOD)) % MOD
        }
        memo[key] = res
        return res
    }

    return dfs(m, k, 0, 0)
}

func bitsSet(x int) int {
    cnt := 0
    for x > 0 {
        cnt += x & 1
        x >>= 1
    }
    return cnt
}

func main(){
    // placeholder
    fmt.Println(magicalSum(1,1,[]int{28}))
}
 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

class Solution {
    private static final int MOD = 1_000_000_007;

    public int magicalSum(int m, int k, int[] nums) {
        int 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[][] pw = new long[n][m + 1];
        for (int i = 0; i < n; i++) {
            pw[i][0] = 1;
            for (int t = 1; t <= m; t++) {
                pw[i][t] = pw[i][t - 1] * nums[i] % MOD;
            }
        }

        Map<String, Integer> memo = new HashMap<>();
        return dfs(m, k, 0, 0L, nums, C, pw, memo);
    }

    private int dfs(int remaining, int oddNeeded, int idx, long carry, int[] nums, long[][] C, long[][] pw, Map<String, Integer> memo) {
        if (remaining < 0 || oddNeeded < 0) return 0;
        if (remaining + Long.bitCount(carry) < oddNeeded) return 0;
        if (remaining == 0) return (oddNeeded == Long.bitCount(carry)) ? 1 : 0;
        if (idx >= nums.length) return 0;

        String key = remaining + ":" + oddNeeded + ":" + idx + ":" + carry;
        if (memo.containsKey(key)) return memo.get(key);

        long res = 0;
        for (int take = 0; take <= remaining; ++take) {
            long ways = C[remaining][take];
            long prod = pw[idx][take];
            long nc = carry + take;
            int lsb = (int) (nc & 1L);
            int sub = dfs(remaining - take, oddNeeded - lsb, idx + 1, nc >> 1, nums, C, pw, memo);
            res = (res + ways % MOD * prod % MOD * sub) % MOD;
        }
        memo.put(key, (int) res);
        return (int) res;
    }
}
 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

class Solution {
    private val MOD = 1000000007L

    fun magicalSum(m: Int, k: Int, nums: IntArray): Int {
        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
        }

        val pw = Array(n) { LongArray(m + 1) }
        for (i in 0 until n) {
            pw[i][0] = 1L
            for (t in 1..m) pw[i][t] = pw[i][t - 1] * nums[i] % MOD
        }

        val memo = HashMap<String, Int>()

        fun dfs(remaining: Int, oddNeeded: Int, idx: Int, carry: Long): Int {
            if (remaining < 0 || oddNeeded < 0) return 0
            if (remaining + java.lang.Long.bitCount(carry) < oddNeeded) return 0
            if (remaining == 0) return if (oddNeeded == java.lang.Long.bitCount(carry)) 1 else 0
            if (idx >= n) return 0

            val key = "$remaining:$oddNeeded:$idx:$carry"
            if (memo.containsKey(key)) return memo[key]!!

            var res = 0L
            for (take in 0..remaining) {
                val ways = C[remaining][take]
                val prod = pw[idx][take]
                val nc = carry + take
                val lsb = (nc and 1L).toInt()
                val sub = dfs(remaining - take, oddNeeded - lsb, idx + 1, nc shr 1)
                res = (res + ways % MOD * prod % MOD * sub) % MOD
            }
            memo[key] = res.toInt()
            return res.toInt()
        }

        return dfs(m, k, 0, 0L)
    }
}
 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

from functools import lru_cache
from typing import List
import math

class Solution:
    def magicalSum(self, m: int, k: int, nums: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)

        @lru_cache(None)
        def dfs(remaining: int, odd_needed: int, index: int, carry: int) -> int:
            if remaining < 0 or odd_needed < 0:
                return 0
            if remaining + carry.bit_count() < odd_needed:
                return 0
            if remaining == 0:
                return 1 if odd_needed == carry.bit_count() else 0
            if index >= n:
                return 0

            ans = 0
            for take in range(remaining + 1):
                ways = math.comb(remaining, take) * pow(nums[index], take, MOD) % MOD
                new_carry = carry + take
                ans = (ans + ways * dfs(remaining - take, odd_needed - (new_carry & 1), index + 1, new_carry >> 1)) % MOD
            return ans

        return dfs(m, k, 0, 0)
 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

use std::collections::HashMap;

const MOD: i64 = 1_000_000_007;

pub struct Solution;

impl Solution {
    pub fn magical_sum(m: i32, k: i32, nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let m_usize = m as usize;
        // comb table
        let mut c = vec![vec![0i64; m_usize + 1]; m_usize + 1];
        for i in 0..=m_usize {
            c[i][0] = 1;
            for j in 1..=i {
                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
            }
        }

        // pow table
        let mut pw = vec![vec![1i64; m_usize + 1]; n];
        for i in 0..n {
            for t in 1..=m_usize {
                pw[i][t] = pw[i][t - 1] * nums[i] as i64 % MOD;
            }
        }

        let mut memo: HashMap<String, i64> = HashMap::new();

        fn popcount64(x: i64) -> i32 { x.count_ones() as i32 }

        fn dfs(remaining: i32, odd_needed: i32, idx: usize, carry: i64, n: usize, m_usize: usize, c: &Vec<Vec<i64>>, pw: &Vec<Vec<i64>>, memo: &mut HashMap<String, i64>) -> i64 {
            if remaining < 0 || odd_needed < 0 { return 0; }
            if remaining as usize + popcount64(carry) as usize < odd_needed as usize { return 0; }
            if remaining == 0 { return if odd_needed == popcount64(carry) { 1 } else { 0 }; }
            if idx >= n { return 0; }
            let key = format!("{}:{}:{}:{}", remaining, odd_needed, idx, carry);
            if let Some(&v) = memo.get(&key) { return v; }
            let mut res = 0i64;
            for take in 0..=remaining as usize {
                let ways = c[remaining as usize][take] % MOD;
                let prod = pw[idx][take] % MOD;
                let nc = carry + take as i64;
                let lsb = (nc & 1) as i32;
                let sub = dfs(remaining - take as i32, odd_needed - lsb, idx + 1, nc >> 1, n, m_usize, c, pw, memo);
                res = (res + ways % MOD * prod % MOD * sub % MOD) % MOD;
            }
            memo.insert(key, res);
            res
        }

        dfs(m, k, 0, 0, n, m_usize, &c, &pw, &mut memo) 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
35
36
37
38
39

class Solution {
    magicalSum(m: number, k: number, nums: number[]): number {
        const MOD = 1_000_000_007;
        const n = nums.length;
        const C: number[][] = Array.from({length: m+1}, () => new Array(m+1).fill(0));
        for (let i = 0; i <= m; ++i) {
            C[i][0] = 1;
            for (let j = 1; j <= i; ++j) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
        const pw: number[][] = Array.from({length: n}, () => new Array(m+1).fill(1));
        for (let i = 0; i < n; ++i) for (let t = 1; t <= m; ++t) pw[i][t] = Math.floor(pw[i][t-1] * nums[i] % MOD);

        const memo = new Map<string, number>();

        function dfs(remaining: number, oddNeeded: number, idx: number, carry: number): number {
            if (remaining < 0 || oddNeeded < 0) return 0;
            if (remaining + popcount(carry) < oddNeeded) return 0;
            if (remaining === 0) return oddNeeded === popcount(carry) ? 1 : 0;
            if (idx >= n) return 0;
            const key = `${remaining}:${oddNeeded}:${idx}:${carry}`;
            if (memo.has(key)) return memo.get(key)!;
            let res = 0;
            for (let take = 0; take <= remaining; ++take) {
                const ways = C[remaining][take];
                const prod = pw[idx][take];
                const nc = carry + take;
                const lsb = nc & 1;
                const sub = dfs(remaining - take, oddNeeded - lsb, idx + 1, nc >> 1);
                res = (res + (((ways * prod) % MOD) * sub) % MOD) % MOD;
            }
            memo.set(key, res);
            return res;
        }

        function popcount(x: number): number { return x.toString(2).split('1').length - 1; }

        return dfs(m, k, 0, 0);
    }
}

Complexity

  • ⏰ Time complexity: O(n * m * m * states) – each memo state iterates take up to m, and the number of distinct states is bounded by O(n * m * maxCarry) where maxCarry is O(m); overall polynomial in n and m versus exponential n^m.
  • 🧺 Space complexity: O(n * m * maxCarry) – for memoization and recursion stack.

Notes: For production performance, pack the memo key into a fixed-size integer or use an iterative 4D DP table when memory allows (see Method 3 planned next).

Method 3 - Bottom-up DP (iterative 4D DP)

Intuition

We can convert the memoized recursion into an iterative DP that fills a 4D table: dp[pos][bits][carry][chosen] — the total sum of products (mod MOD) after processing the first pos indices, having accumulated bits set bits so far, with carry pending and having chosen chosen elements in total. Transitions enumerate how many copies cnt of the current index to take and update the next state’s bits/carry/chosen accordingly while multiplying by combinatorial placement counts and power contributions.

Approach

  1. Precompute binomial coefficients C[a][b] for 0..m and precompute pw[i][t] = nums[i]^t % MOD for t in 0..m.
  2. Initialize dp[0][0][0][0] = 1 and iterate pos from 0 to n-1.
  3. For each reachable state (bits, carry, chosen) at pos, iterate cnt from 0..remaining (remaining = m - chosen) and update dp[pos+1][new_bits][new_carry][chosen+cnt] += dp[pos][bits][carry][chosen] * C[remaining][cnt] * pw[pos][cnt].
  4. After filling dp[n], aggregate the answer by considering leftover carry values: for each carry, compute carry_bits = popcount(carry) and add dp[n][k - carry_bits][carry][m] if carry_bits <= k.

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int MOD = 1000000007;

class Solution {
public:
    int magicalSum(int m, int k, vector<int>& nums) {
        int n = nums.size();
        // binomial table
        vector<vector<int64>> C(m+1, vector<int64>(m+1, 0));
        for (int i = 0; i <= m; ++i) {
            C[i][0] = C[i][i] = 1;
            for (int j = 1; j < i; ++j) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }

        // pow table
        vector<vector<int64>> pw(n, vector<int64>(m+1, 1));
        for (int i = 0; i < n; ++i) for (int t = 1; t <= m; ++t) pw[i][t] = pw[i][t-1] * nums[i] % MOD;

        // dp[pos][bits][carry][chosen]
        vector<vector<vector<vector<int64>>>> dp(
            n+1,
            vector<vector<vector<int64>>>(k+1, vector<vector<int64>>(m+1, vector<int64>(m+1, 0)))
        );

        dp[0][0][0][0] = 1;
        for (int pos = 0; pos < n; ++pos) {
            for (int bits = 0; bits <= k; ++bits) {
                for (int carry = 0; carry <= m; ++carry) {
                    for (int chosen = 0; chosen <= m; ++chosen) {
                        int64 cur = dp[pos][bits][carry][chosen];
                        if (cur == 0) continue;
                        int remaining = m - chosen;
                        for (int cnt = 0; cnt <= remaining; ++cnt) {
                            int total = carry + cnt;
                            int new_bits = bits + (total & 1);
                            int new_carry = total >> 1;
                            if (new_bits <= k && new_carry <= m) {
                                int64 add = cur * C[remaining][cnt] % MOD * pw[pos][cnt] % MOD;
                                dp[pos+1][new_bits][new_carry][chosen+cnt] = (dp[pos+1][new_bits][new_carry][chosen+cnt] + add) % MOD;
                            }
                        }
                    }
                }
            }
        }

        int64 res = 0;
        for (int carry = 0; carry <= m; ++carry) {
            int carry_bits = __builtin_popcount(carry);
            if (carry_bits <= k) {
                res = (res + dp[n][k - carry_bits][carry][m]) % MOD;
            }
        }
        return (int)res;
    }
};
 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

package main

import (
	"fmt"
)

const MOD = 1000000007

type Solution struct{}

func (s *Solution) magicalSum(m int, k int, nums []int) int {
	n := len(nums)
	C := make([][]int64, m+1)
	for i := range C {
		C[i] = make([]int64, m+1)
		C[i][0] = 1
		C[i][i] = 1
		for j := 1; j < i; j++ {
			C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD
		}
	}

	pw := make([][]int64, n)
	for i := 0; i < n; i++ {
		pw[i] = make([]int64, m+1)
		pw[i][0] = 1
		for t := 1; t <= m; t++ {
			pw[i][t] = (pw[i][t-1] * int64(nums[i])) % MOD
		}
	}

	// dp[pos][bits][carry][chosen]
	dp := make([][][][]int64, n+1)
	for pos := 0; pos <= n; pos++ {
		dp[pos] = make([][][]int64, k+1)
		for bits := 0; bits <= k; bits++ {
			dp[pos][bits] = make([][]int64, m+1)
			for carry := 0; carry <= m; carry++ {
				dp[pos][bits][carry] = make([]int64, m+1)
			}
		}
	}

	dp[0][0][0][0] = 1
	for pos := 0; pos < n; pos++ {
		for bits := 0; bits <= k; bits++ {
			for carry := 0; carry <= m; carry++ {
				for chosen := 0; chosen <= m; chosen++ {
					cur := dp[pos][bits][carry][chosen]
					if cur == 0 { continue }
					remaining := m - chosen
					for cnt := 0; cnt <= remaining; cnt++ {
						total := carry + cnt
						newBits := bits + (total & 1)
						newCarry := total >> 1
						if newBits <= k && newCarry <= m {
							add := cur * C[remaining][cnt] % MOD * pw[pos][cnt] % MOD
							dp[pos+1][newBits][newCarry][chosen+cnt] = (dp[pos+1][newBits][newCarry][chosen+cnt] + add) % MOD
						}
					}
				}
			}
		}
	}

	var res int64 = 0
	for carry := 0; carry <= m; carry++ {
		carryBits := bitsSet(carry)
		if carryBits <= k {
			res = (res + dp[n][k-carryBits][carry][m]) % MOD
		}
	}
	return int(res)
}

func bitsSet(x int) int {
	cnt := 0
	for x > 0 {
		cnt += x & 1
		x >>= 1
	}
	return cnt
}

func main() {
	s := &Solution{}
	fmt.Println(s.magicalSum(1,1,[]int{28}))
}
 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


class Solution {
    private static final int MOD = 1_000_000_007;

    public int magicalSum(int m, int k, int[] nums) {
        int n = nums.length;
        long[][] C = new long[m+1][m+1];
        for (int i = 0; i <= m; i++) {
            C[i][0] = C[i][i] = 1;
            for (int j = 1; j < i; j++) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }

        long[][] pw = new long[n][m+1];
        for (int i = 0; i < n; i++) {
            pw[i][0] = 1;
            for (int t = 1; t <= m; t++) pw[i][t] = pw[i][t-1] * nums[i] % MOD;
        }

        long[][][][] dp = new long[n+1][k+1][m+1][m+1];
        dp[0][0][0][0] = 1;

        for (int pos = 0; pos < n; pos++) {
            for (int bits = 0; bits <= k; bits++) {
                for (int carry = 0; carry <= m; carry++) {
                    for (int chosen = 0; chosen <= m; chosen++) {
                        long cur = dp[pos][bits][carry][chosen];
                        if (cur == 0) continue;
                        int remaining = m - chosen;
                        for (int cnt = 0; cnt <= remaining; cnt++) {
                            int total = carry + cnt;
                            int newBits = bits + (total & 1);
                            int newCarry = total >> 1;
                            if (newBits <= k && newCarry <= m) {
                                long add = cur * C[remaining][cnt] % MOD * pw[pos][cnt] % MOD;
                                dp[pos+1][newBits][newCarry][chosen+cnt] = (dp[pos+1][newBits][newCarry][chosen+cnt] + add) % MOD;
                            }
                        }
                    }
                }
            }
        }

        long res = 0;
        for (int carry = 0; carry <= m; carry++) {
            int carryBits = Integer.bitCount(carry);
            if (carryBits <= k) {
                res = (res + dp[n][k - carryBits][carry][m]) % MOD;
            }
        }
        return (int) res;
    }
}
 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

class Solution {
	private val MOD = 1_000_000_007L

	fun magicalSum(m: Int, k: Int, nums: IntArray): Int {
		val n = nums.size
		val C = Array(m + 1) { LongArray(m + 1) }
		for (i in 0..m) {
			C[i][0] = 1L
			C[i][i] = 1L
			for (j in 1 until i) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD
		}

		val pw = Array(n) { LongArray(m + 1) }
		for (i in 0 until n) {
			pw[i][0] = 1L
			for (t in 1..m) pw[i][t] = pw[i][t-1] * nums[i] % MOD
		}

		// dp[pos][bits][carry][chosen]
		val dp = Array(n+1) { Array(k+1) { Array(m+1) { LongArray(m+1) } } }
		dp[0][0][0][0] = 1L

		for (pos in 0 until n) {
			for (bits in 0..k) {
				for (carry in 0..m) {
					for (chosen in 0..m) {
						val cur = dp[pos][bits][carry][chosen]
						if (cur == 0L) continue
						val remaining = m - chosen
						for (cnt in 0..remaining) {
							val total = carry + cnt
							val newBits = bits + (total and 1)
							val newCarry = total shr 1
							if (newBits <= k && newCarry <= m) {
								val add = cur * C[remaining][cnt] % MOD * pw[pos][cnt] % MOD
								dp[pos+1][newBits][newCarry][chosen+cnt] = (dp[pos+1][newBits][newCarry][chosen+cnt] + add) % MOD
							}
						}
					}
				}
			}
		}

		var res = 0L
		for (carry in 0..m) {
			val carryBits = Integer.bitCount(carry)
			if (carryBits <= k) res = (res + dp[n][k - carryBits][carry][m]) % MOD
		}
		return res.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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

from typing import List

class Solution:
	MOD = 10**9 + 7

	def magicalSum(self, m: int, k: int, nums: List[int]) -> int:
		n = len(nums)

		# binomial table
		C = [[0] * (m + 1) for _ in range(m + 1)]
		for i in range(m + 1):
			C[i][0] = 1
			C[i][i] = 1
			for j in range(1, i):
				C[i][j] = (C[i-1][j-1] + C[i-1][j]) % self.MOD

		# pow table
		pw = [[1] * (m + 1) for _ in range(n)]
		for i in range(n):
			for t in range(1, m + 1):
				pw[i][t] = pw[i][t-1] * nums[i] % self.MOD

		# dp[pos][bits][carry][chosen]
		dp = [ [ [ [0] * (m + 1) for _ in range(m + 1)] for _ in range(k + 1)] for _ in range(n + 1) ]
		dp[0][0][0][0] = 1

		for pos in range(n):
			for bits in range(k + 1):
				for carry in range(m + 1):
					for chosen in range(m + 1):
						cur = dp[pos][bits][carry][chosen]
						if cur == 0:
							continue
						remaining = m - chosen
						for cnt in range(remaining + 1):
							total = carry + cnt
							new_bits = bits + (total & 1)
							new_carry = total >> 1
							if new_bits <= k and new_carry <= m:
								add = cur * C[remaining][cnt] % self.MOD * pw[pos][cnt] % self.MOD
								dp[pos+1][new_bits][new_carry][chosen+cnt] = (dp[pos+1][new_bits][new_carry][chosen+cnt] + add) % self.MOD

		res = 0
		for carry in range(m + 1):
			carry_bits = bin(carry).count('1')
			if carry_bits <= k:
				res = (res + dp[n][k - carry_bits][carry][m]) % self.MOD
		return res
 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

use std::cmp;

const MOD: i64 = 1_000_000_007;

pub struct Solution;

impl Solution {
	pub fn magical_sum(m: i32, k: i32, nums: Vec<i32>) -> i32 {
		let n = nums.len();
		let m_us = m as usize;

		// comb table
		let mut c = vec![vec![0i64; m_us + 1]; m_us + 1];
		for i in 0..=m_us {
			c[i][0] = 1;
			c[i][i] = 1;
			for j in 1..i {
				c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
			}
		}

		// pow table
		let mut pw = vec![vec![1i64; m_us + 1]; n];
		for i in 0..n {
			for t in 1..=m_us {
				pw[i][t] = pw[i][t-1] * nums[i] as i64 % MOD;
			}
		}

		// dp[pos][bits][carry][chosen]
		let mut dp = vec![vec![vec![vec![0i64; m_us + 1]; m_us + 1]; (k as usize) + 1]; n + 1];
		dp[0][0][0][0] = 1;

		for pos in 0..n {
			for bits in 0..=(k as usize) {
				for carry in 0..=m_us {
					for chosen in 0..=m_us {
						let cur = dp[pos][bits][carry][chosen];
						if cur == 0 { continue }
						let remaining = m_us - chosen;
						for cnt in 0..=remaining {
							let total = carry + cnt;
							let new_bits = bits + (total & 1);
							let new_carry = total >> 1;
							if new_bits <= (k as usize) && new_carry <= m_us {
								let add = cur * c[remaining][cnt] % MOD * pw[pos][cnt] % MOD;
								dp[pos+1][new_bits][new_carry][chosen+cnt] = (dp[pos+1][new_bits][new_carry][chosen+cnt] + add) % MOD;
							}
						}
					}
				}
			}
		}

		let mut res = 0i64;
		for carry in 0..=m_us {
			let carry_bits = (carry as u32).count_ones() as usize;
			if carry_bits <= (k as usize) {
				res = (res + dp[n][(k as usize) - carry_bits][carry][m_us]) % MOD;
			}
		}
		res 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

class Solution {
	magicalSum(m: number, k: number, nums: number[]): number {
		const MOD = 1_000_000_007;
		const n = nums.length;
		const C: number[][] = Array.from({length: m+1}, () => new Array(m+1).fill(0));
		for (let i = 0; i <= m; ++i) {
			C[i][0] = C[i][i] = 1;
			for (let j = 1; j < i; ++j) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
		}

		const pw: number[][] = Array.from({length: n}, () => new Array(m+1).fill(1));
		for (let i = 0; i < n; ++i) for (let t = 1; t <= m; ++t) pw[i][t] = Math.floor(pw[i][t-1] * nums[i] % MOD);

		// dp[pos][bits][carry][chosen]
		const dp: number[][][][] = new Array(n+1);
		for (let pos = 0; pos <= n; ++pos) {
			dp[pos] = new Array(k+1);
			for (let bits = 0; bits <= k; ++bits) {
				dp[pos][bits] = new Array(m+1);
				for (let carry = 0; carry <= m; ++carry) dp[pos][bits][carry] = new Array(m+1).fill(0);
			}
		}

		dp[0][0][0][0] = 1;
		for (let pos = 0; pos < n; ++pos) {
			for (let bits = 0; bits <= k; ++bits) {
				for (let carry = 0; carry <= m; ++carry) {
					for (let chosen = 0; chosen <= m; ++chosen) {
						const cur = dp[pos][bits][carry][chosen];
						if (!cur) continue;
						const remaining = m - chosen;
						for (let cnt = 0; cnt <= remaining; ++cnt) {
							const total = carry + cnt;
							const newBits = bits + (total & 1);
							const newCarry = total >> 1;
							if (newBits <= k && newCarry <= m) {
								const add = (cur * C[remaining][cnt] % MOD) * pw[pos][cnt] % MOD;
								dp[pos+1][newBits][newCarry][chosen+cnt] = (dp[pos+1][newBits][newCarry][chosen+cnt] + add) % MOD;
							}
						}
					}
				}
			}
		}

		let res = 0;
		for (let carry = 0; carry <= m; ++carry) {
			const carryBits = carry.toString(2).split('1').length - 1;
			if (carryBits <= k) res = (res + dp[n][k - carryBits][carry][m]) % MOD;
		}
		return res;
	}
}

Complexity

  • ⏰ Time complexity: O(n * k * m^3) – we iterate over pos (n), bits (k), carry (O(m)), chosen (O(m)) and for each state try up to O(m) values of cnt, yielding O(n * k * m^3).
  • 🧺 Space complexity: O(n * k * m^2) – the 4D DP table has size O(n * k * (m+1) * (m+1)).