aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-10-11 22:00:35 -0600
committerJack Sangdahl <[email protected]>2025-10-11 22:00:35 -0600
commit34a6791c29e4c23dd299327a33247a77d39cc681 (patch)
tree385051502113e7b04e813a190cecc3f4123ba08e
parenta5f938a020f2ddb10668e8d10a146027ea1807cd (diff)
downloadleetcode-34a6791c29e4c23dd299327a33247a77d39cc681.tar.gz
leetcode-34a6791c29e4c23dd299327a33247a77d39cc681.zip
3539. find sum of array product of magical sequencesHEADmaster
-rw-r--r--find_sum_arr_product_seq.c119
-rw-r--r--find_sum_arr_product_seq.py76
2 files changed, 195 insertions, 0 deletions
diff --git a/find_sum_arr_product_seq.c b/find_sum_arr_product_seq.c
new file mode 100644
index 0000000..568eb09
--- /dev/null
+++ b/find_sum_arr_product_seq.c
@@ -0,0 +1,119 @@
+// 3539. Find Sum of Array Product of Magical Sequences
+#include "leetcode.h"
+
+/*
+ * 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.len', and the binary representation of '2^seq[0] + 2^seq[1]
+ * + ...' has 'k' set bits. the array product of this sequence is defined as
+ * 'prod(seq) = (nums[seq[0]] * nums[seq[1]] * ...)'. return the sum of the
+ * array products for all valid magical sequences. since the answer may be very
+ * large, return it modulo 10^9+7. a set bit refers to a bit in the binary
+ * represenation of a number that has a value of 1
+ */
+
+static int mod = 1e9 + 7;
+
+int magicalSum(int m, int k, int *nums, int numsSize) {
+ int **pow_tab = (int **)malloc(numsSize * sizeof(int *));
+ for (int i = 0; i < numsSize; i++) {
+ pow_tab[i] = (int *)malloc((m + 1) * sizeof(int));
+ pow_tab[i][0] = 1;
+ for (int j = 1; j <= m; j++) {
+ long long val = (1LL * pow_tab[i][j - 1] * nums[i]) % mod;
+ pow_tab[i][j] = (int)val;
+ }
+ }
+ int **cmb = (int **)malloc((m + 1) * sizeof(int *));
+ for (int i = 0; i <= m; i++) {
+ cmb[i] = (int *)malloc((m + 1) * sizeof(int));
+ memset(cmb[i], 0, (m + 1) * sizeof(int));
+ }
+ for (int i = 0; i <= m; i++) {
+ cmb[i][0] = 1;
+ for (int j = 1; j <= i; j++) {
+ cmb[i][j] = cmb[i - 1][j - 1] + cmb[i - 1][j];
+ if (cmb[i][j] >= mod)
+ cmb[i][j] -= mod;
+ }
+ }
+ int ***dp = (int ***)malloc((m + 1) * sizeof(int **));
+ int ***next = (int ***)malloc((m + 1) * sizeof(int **));
+ for (int i = 0; i <= m; i++) {
+ dp[i] = (int **)malloc((m + 1) * sizeof(int *));
+ next[i] = (int **)malloc((m + 1) * sizeof(int *));
+ for (int j = 0; j <= m; j++) {
+ dp[i][j] = (int *)calloc(k + 1, sizeof(int));
+ next[i][j] = (int *)calloc(k + 1, sizeof(int));
+ }
+ }
+ dp[m][0][0] = 1;
+ for (int i = 0; i < numsSize; i++) {
+ for (int j = 0; j <= m; j++)
+ for (int c = 0; c <= m; c++)
+ memset(next[j][c], 0, (k + 1) * sizeof(int));
+ for (int rem = 0; rem <= m; rem++) {
+ for (int carry = 0; carry <= m; carry++)
+ for (int ones = 0; ones <= k; ones++) {
+ int base = dp[rem][carry][ones];
+ if (!base)
+ continue;
+ for (int c = 0; c <= rem; c++) {
+ int tmp = c + carry;
+ int bit = tmp & 1;
+ int ones2 = ones + bit;
+ if (ones2 > k)
+ continue;
+ int carry2 = tmp >> 1;
+ int rem2 = rem - c;
+ long long add = base;
+ add = (add * cmb[rem][c]) % mod;
+ add = (add * pow_tab[i][c]) % mod;
+ int curr = next[rem2][carry2][ones2] + (int)add;
+ if (curr >= mod)
+ curr -= mod;
+ next[rem2][carry2][ones2] = curr;
+ }
+ }
+ }
+ int ***tmp = dp;
+ dp = next;
+ next = tmp;
+ }
+ long long ans = 0;
+ for (int carry = 0; carry <= m; carry++) {
+ int extra = __builtin_popcount(carry);
+ int need = k - extra;
+ if (need >= 0 && need <= k) {
+ ans += dp[0][carry][need];
+ if (ans >= mod)
+ ans -= mod;
+ }
+ }
+ for (int i = 0; i < numsSize; i++)
+ free(pow_tab[i]);
+ free(pow_tab);
+ for (int i = 0; i <= m; i++)
+ free(cmb[i]);
+ free(cmb);
+ for (int rem = 0; rem <= m; rem++) {
+ for (int carry = 0; carry <= m; carry++) {
+ free(dp[rem][carry]);
+ free(next[rem][carry]);
+ }
+ free(dp[rem]);
+ free(next[rem]);
+ }
+ free(dp);
+ free(next);
+ return (int)(ans % mod);
+}
+
+int main() {
+ int n1[] = {1, 10, 100, 10000, 1000000};
+ int n2[] = {5, 4, 3, 2, 1};
+ int n3[] = {28};
+ printf("%d\n", magicalSum(5, 5, n1, ARRAY_SIZE(n1))); // expect: 991600007
+ printf("%d\n", magicalSum(2, 2, n2, ARRAY_SIZE(n2))); // expect: 170
+ printf("%d\n", magicalSum(1, 1, n3, ARRAY_SIZE(n3))); // expect: 28
+}
diff --git a/find_sum_arr_product_seq.py b/find_sum_arr_product_seq.py
new file mode 100644
index 0000000..ebadb9f
--- /dev/null
+++ b/find_sum_arr_product_seq.py
@@ -0,0 +1,76 @@
+# 3539. 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.len', and the binary representation of '2^seq[0] + 2^seq[1]
++ ...' has 'k' set bits. the array product of this sequence is defined as
+'prod(seq) = (nums[seq[0]] nums[seq[1]] ...)'. return the sum of the
+array products for all valid magical sequences. since the answer may be very
+large, return it modulo 10^9+7. a set bit refers to a bit in the binary
+represenation of a number that has a value of 1
+"""
+
+
+class Solution(object):
+ def magicalSum(self, m, k, nums):
+ """
+ :type m: int
+ :type k: int
+ :type nums: List[int]
+ :rtype: int
+ """
+ mod = 10**9 + 7
+ n = len(nums)
+ powtab = [[1] * (m + 1) for _ in range(n)]
+ for i in range(n):
+ for c in range(1, m + 1):
+ powtab[i][c] = powtab[i][c - 1] * nums[i] % mod
+ comb = [[0] * (m + 1) for _ in range(m + 1)]
+ for i in range(m + 1):
+ comb[i][0] = 1
+ for j in range(1, i + 1):
+ comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % mod
+ dp = [[[0] * (k + 1) for _ in range(m + 1)] for __ in range(m + 1)]
+ dp[m][0][0] = 1
+ for i in range(n):
+ next_dp = [[[0] * (k + 1) for _ in range(m + 1)] for __ in range(m + 1)]
+ pow_i = powtab[i]
+ for rem in range(m + 1):
+ for carry in range(m + 1):
+ row = dp[rem][carry]
+ if not any(row_elt for row_elt in row):
+ continue
+ for ones in range(k + 1):
+ base_val = row[ones]
+ if base_val == 0:
+ continue
+ for c in range(rem + 1):
+ t = c + carry
+ bit = t & 1
+ ones2 = ones + bit
+ if ones2 > k:
+ continue
+ carry2 = t >> 1
+ rem2 = rem - c
+ add = base_val
+ add = add * comb[rem][c] % mod
+ add = add * pow_i[c] % mod
+ next_dp[rem2][carry2][ones2] = (
+ next_dp[rem2][carry2][ones2] + add
+ ) % mod
+ dp = next_dp
+ ans = 0
+ for carry in range(m + 1):
+ extra = bin(carry).count("1")
+ need = k - extra
+ if 0 <= need <= k:
+ ans = (ans + dp[0][carry][need]) % mod
+ return ans % mod
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.magicalSum(m=5, k=5, nums=[1, 10, 100, 10000, 1000000]))
+ print(obj.magicalSum(m=2, k=2, nums=[5, 4, 3, 2, 1]))
+ print(obj.magicalSum(m=1, k=1, nums=[28]))