Find Sum of Array Product of Magical Sequences - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
3539. Find Sum of Array Product of Magical Sequences
Hard
50 Points
Array
Math
Dynamic Programming
Bit Manipulation
Combinatorics
Bitmask
You are given two integers, m and k, and an integer array nums.
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.
Examples
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 10 13 .
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
3539. Find Sum of Array Product of Magical Sequences
Hard
50 Points
Array
Math
Dynamic Programming
Bit Manipulation
Combinatorics
Bitmask
You are given two integers, m and k, and an integer array nums.
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.
Examples
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 10 13 .