Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Choosing index i several times adds that many copies of 2^i. Binary addition carries into higher bits, so the number of set bits is not simply the number of distinct chosen indices. Process indices from low to high while carrying the unfinished binary sum.

Approach

Memoize a state with the carry, remaining sequence positions, remaining required set bits, and current index. Choose a frequency from zero through the remaining positions for this index. Add it to the carry: the low bit is now finalized, and shifting right gives the carry for the next index. Subtract that finalized bit from the required count.

For a positive frequency, weight the continuation by nums[i]^frequency and C(remainingPositions, frequency). The binomial factor chooses which ordered sequence positions receive this index, so repeated indices are counted without losing sequence order. The zero-frequency transition simply skips the index.

When no positions remain, accept precisely when the remaining carry has the required number of set bits. If indices run out with positions still unfilled, reject. Combine the weighted transitions using modular arithmetic and return the final sum modulo 1,000,000,007.

class Solution:
    def magicalSum(self, m: int, k: int, nums: List[int]) -> int:
        MOD = 10**9 + 7
        # time: O(m^3 * k * n)
        # space: O(m^2 * k * n)

        @cache
        def dp(mask, m, k, i):
            if m == 0 and mask.bit_count() == k:
                return 1
            if m == 0 or i == len(nums):
                return 0

            total = 0
            total += (dp(mask >> 1, m, k - (mask & 1), i + 1)) % MOD # skip i

            for freq in range(1, m + 1):
                nmask = mask + freq
                next = (dp(nmask >> 1, m - freq, k - (nmask & 1), i + 1)) % MOD
                total += (
                    pow(nums[i], freq, MOD) * next # curr element * next element
                    * comb(m, freq) # add combinations of freq in m
                ) % MOD

            return total

        return (dp(0, m, k, 0)) % MOD

Complexity analysis

Let N = nums.length and m be the initial sequence length. Neither implementation prunes negative remaining-bit counts. At most m one-bits can have been finalized, so that coordinate ranges from k-m through k, giving O(m) possibilities even for small k. Carry and remaining positions also have O(m) possibilities: O(Nm^3) memo states. Each has O(m) frequency choices, and the repeated exact binomial computation costs up to O(m) arithmetic steps; modular exponentiation costs O(log(m+1)). A conservative bound is O(Nm^5) time and O(N*m^3) auxiliary space, with O(N) recursion depth, using bounded-integer arithmetic under m<=30. Each transition is reduced before addition, so a cached total is below (m+1)*MOD in BOTH versions despite the lack of a final per-state reduction. Python's unreduced binomial-weighted product has fewer than 90 bits under these bounds; this is not an unbounded-count DP.