2025-10-12 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's October LeetCoding Challenge with cpp.

October LeetCoding Challenge 12

Description

Find Sum of Array Product of Magical Sequences

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

Solution

class Solution {
  using ll = long long;
  const int MOD = 1e9 + 7;
  ll dp[55][35][35][35] = {};
  bool vis[55][35][35][35] = {};
  vector<vector<ll>> powNum;
  vector<vector<ll>> C;
  int len;
  int k;
  int m;
  void init(const vector<int>& nums) {
    powNum.resize(len, vector<ll>(m + 1, 1));
    for(int i = 0; i < len; ++i) {
      for(int j = 1; j <= m; ++j) {
        powNum[i][j] = powNum[i][j - 1] * nums[i] % MOD;
      }
    }
    C.resize(m + 1, vector<ll>(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;
      }
    }
  }
  ll dfs(int pos, int carry, int used, int ones) {
    if(pos == len) {
      int extra = 0;
      int c = carry;
      while(c) {
        if(c & 1) extra += 1;
        c >>= 1;
      }
      return (used == m && ones + extra == k) ? 1 : 0;
    }
    if(dp[pos][carry][used][ones] != -1) return dp[pos][carry][used][ones];
    ll answer = 0;
    for(int count = 0; count + used <= m; ++count) {
      int total = carry + count;
      int bit = total & 1;
      int ncarry = total >> 1;
      int nones = ones + bit;
      ll sub = dfs(pos + 1, ncarry, used + count, nones);
      if(!sub) continue;
      ll ways = C[m - used][count];
      ll prod = powNum[pos][count];
      answer += sub * ways % MOD * prod % MOD;
      answer %= MOD;
    }
    // cout << pos << ' ' << carry << ' ' << used << ' ' << ones << ' ' << answer << endl;
    return dp[pos][carry][used][ones] = answer;
  }
public:
  int magicalSum(int m, int k, vector<int>& nums) {
    memset(dp, -1, sizeof(dp));
    this->m = m;
    this->k = k;
    len = nums.size();
    init(nums);
    return dfs(0, 0, 0, 0);
  }
};

// Accepted
// 528/528 cases passed (700 ms)
// Your runtime beats 8.57 % of cpp submissions
// Your memory usage beats 40 % of cpp submissions (45.2 MB)
Algorithm