Skip to content

3851. Find Sum Of Array Product Of Magical Sequences

Array Math Dynamic Programming Bit Manipulation Combinatorics Bitmask

Problem - Find Sum Of Array Product Of Magical Sequences

Hard

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 109 + 7.

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

 

Example 1:

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:

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:

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] <= 108

Solutions

 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
class Solution:
    def mul_with_mod(self, x: int, y: int, mod: int) -> int:
        result, current = 1, x % mod
        while y:
            if y & 1:
                result = result * current % mod
            y >>= 1
            current = current * current % mod
        return result

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

        fac = [1] * (m + 1)
        for i in range(1, m + 1):
            fac[i] = fac[i - 1] * i % mod

        ifac = [1] * (m + 1)
        for i in range(2, m + 1):
            ifac[i] = self.mul_with_mod(i, mod - 2, mod)
        for i in range(2, m + 1):
            ifac[i] = ifac[i - 1] * ifac[i] % mod

        numsPower = [[1] * (m + 1) for _ in range(n)]
        for i in range(n):
            for j in range(1, m + 1):
                numsPower[i][j] = numsPower[i][j - 1] * nums[i] % mod

        dp = [[[[0] * (k + 1) for _ in range(m * 2 + 1)] for _ in range(m + 1)] for _ in range(n)]

        for j in range(m + 1):
            dp[0][j][j][0] = numsPower[0][j] * ifac[j] % mod

        for i in range(n - 1):
            for j in range(m + 1):
                for p in range(m * 2 + 1):
                    for q in range(k + 1):
                        if dp[i][j][p][q] == 0:
                            continue
                        q2 = (p % 2) + q

                        if q2 > k:
                            break

                        for r in range(m - j + 1):
                            p2 = (p // 2) + r
                            if p2 > m * 2:
                                continue
                            dp[i + 1][j + r][p2][q2] = (dp[i + 1][j + r][p2][q2] + dp[i][j][p][q] 
                                                    * numsPower[i + 1][r] % mod * ifac[r] % mod
                                                    ) % mod

        result = 0
        for p in range(m * 2 + 1):
            for q in range(k + 1):
                if bin(p).count("1") + q == k:
                    result = (result + dp[n - 1][m][p][q] * fac[m] % mod) % mod

        return result

Submission Stats:

  • Runtime: 1787 ms (51.15%)
  • Memory: 55.7 MB (7.86%)