From 34a6791c29e4c23dd299327a33247a77d39cc681 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Sat, 11 Oct 2025 22:00:35 -0600 Subject: 3539. find sum of array product of magical sequences --- find_sum_arr_product_seq.c | 119 ++++++++++++++++++++++++++++++++++++++++++++ find_sum_arr_product_seq.py | 76 ++++++++++++++++++++++++++++ 2 files changed, 195 insertions(+) create mode 100644 find_sum_arr_product_seq.c create mode 100644 find_sum_arr_product_seq.py 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])) -- cgit v1.2.3