Skip to content

3539. Find Sum of Array Product of Magical Sequences 👍

  • Time: $O(m^3kn)$
  • Space: $O(m^2kn)$
 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
class Solution {
 public:
  int magicalSum(int m, int k, vector<int>& nums) {
    const vector<vector<int>> comb = getComb(m, m);
    vector<vector<vector<vector<int>>>> mem(
        m + 1, vector<vector<vector<int>>>(
                   k + 1, vector<vector<int>>(nums.size() + 1,
                                              vector<int>(m + 1, -1))));
    return dp(m, k, 0, 0, nums, mem, comb);
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  int dp(int m, int k, int i, unsigned carry, const vector<int>& nums,
         vector<vector<vector<vector<int>>>>& mem,
         const vector<vector<int>>& comb) {
    if (m < 0 || k < 0 || (m + popcount(carry) < k))
      return 0;
    if (m == 0)
      return k == popcount(carry) ? 1 : 0;
    if (i == nums.size())
      return 0;
    if (mem[m][k][i][carry] != -1)
      return mem[m][k][i][carry];
    int res = 0;
    for (int count = 0; count <= m; ++count) {
      const long contribution = comb[m][count] * modPow(nums[i], count) % kMod;
      const int newCarry = carry + count;
      res = (res + static_cast<long>(dp(m - count, k - (newCarry % 2), i + 1,
                                        newCarry / 2, nums, mem, comb)) *
                       contribution) %
            kMod;
    }
    return mem[m][k][i][carry] = res;
  }

  // C(n, k) = C(n - 1, k) + C(n - 1, k - 1)
  vector<vector<int>> getComb(int n, int k) {
    vector<vector<int>> comb(n + 1, vector<int>(k + 1));
    for (int i = 0; i <= n; ++i)
      comb[i][0] = 1;
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= k; ++j)
        comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
    return comb;
  }

  long modPow(long x, long n) {
    if (n == 0)
      return 1;
    if (n % 2 == 1)
      return x * modPow(x % kMod, (n - 1)) % kMod;
    return modPow(x * x % kMod, (n / 2)) % kMod;
  }
};

 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
class Solution {
  public int magicalSum(int m, int k, int[] nums) {
    int[][] comb = getComb(m, m);
    Integer[][][][] mem = new Integer[m + 1][k + 1][nums.length + 1][m + 1];
    return dp(m, k, 0, 0, nums, mem, comb);
  }

  private static final int MOD = 1_000_000_007;

  private int dp(int m, int k, int i, int carry, int[] nums, Integer[][][][] mem, int[][] comb) {
    if (m < 0 || k < 0 || (m + Integer.bitCount(carry) < k))
      return 0;
    if (m == 0)
      return k == Integer.bitCount(carry) ? 1 : 0;
    if (i == nums.length)
      return 0;
    if (mem[m][k][i][carry] != null)
      return mem[m][k][i][carry];
    int res = 0;
    for (int count = 0; count <= m; count++) {
      final long contribution = comb[m][count] * modPow(nums[i], count) % MOD;
      final int newCarry = carry + count;
      res = (int) ((res +
                    (long) dp(m - count, k - (newCarry % 2), i + 1, newCarry / 2, nums, mem, comb) *
                        contribution) %
                   MOD);
    }
    return mem[m][k][i][carry] = res;
  }

  // C(n, k) = C(n - 1, k) + C(n - 1, k - 1)
  private int[][] getComb(int n, int k) {
    int[][] comb = new int[n + 1][k + 1];
    for (int i = 0; i <= n; i++)
      comb[i][0] = 1;
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= k; j++)
        comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD;
    return comb;
  }

  private long modPow(long x, long n) {
    if (n == 0)
      return 1;
    if (n % 2 == 1)
      return x * modPow(x % MOD, n - 1) % MOD;
    return modPow(x * x % MOD, n / 2) % MOD;
  }
}

 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
class Solution:
  def magicalSum(self, m: int, k: int, nums: list[int]) -> int:
    MOD = 1_000_000_007

    @functools.lru_cache(None)
    def dp(m: int, k: int, i: int, carry: int) -> int:
      """
      Returns the number of magical sequences of length `k` that can be formed
      from the first `i` numbers in `nums` with at most `m` elements.
      """
      if m < 0 or k < 0 or (m + carry.bit_count() < k):
        return 0
      if m == 0:
        return int(k == carry.bit_count())
      if i == len(nums):
        return 0
      res = 0
      for count in range(m + 1):
        contribution = math.comb(m, count) * pow(nums[i], count, MOD) % MOD
        newCarry = carry + count
        res += dp(m - count, k - (newCarry % 2),
                  i + 1, newCarry // 2) * contribution
        res %= MOD
      return res

    return dp(m, k, 0, 0)