#3539

Find Sum of Array Product of Magical Sequences

expert · 1185 · lc hard +32 · 62% accepted · 217 likes · top 63%

Description

Given integers m, k, and array nums, a "magical" sequence seq of length m satisfies:

- Each seq[i] is a valid index into nums.

- The value 2^seq[0] + 2^seq[1] + ... + 2^seq[m-1] has exactly k set bits in binary.

The product of a magical sequence is the product of nums[seq[i]] for all i.

Return the sum of products over all magical sequences, modulo 10⁹ + 7.

Code

1

2

3

class Solution:
    def magicalSum(self, m: int, k: int, nums: List[int]) -> int:

class Solution:
    def magicalSum(self, m: int, k: int, nums: List[int]) -> int: