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 ar

magicalSum.js

/**
 * @param {number} m
 * @param {number} k
 * @param {number[]} nums
 * @return {number}
 */
var magicalSum = function(m, k, nums) {
    const MOD = BigInt(1e9 + 7); // Modulo for large number arithmetic
    const n = nums.length;

    // Precompute binomial coefficients: comp[i][j] = C(i, j)
    const comp = Array.from({ length: m + 1 }, () => Array(m + 1).fill(0n));
    for (let i = 0; i <= m; i++) {
        comp[i][0] = 1n;
        comp[i][i] = 1n;
        for (let j = 1; j < i; j++) {
            comp[i][j] = (comp[i - 1][j - 1] + comp[i - 1][j]) % MOD;
        }
    }

    // Precompute powers of each nums[i] up to m: powA[i][t] = nums[i]^t
    const powA = Array.from({ length: n }, () => Array(m + 1).fill(1n));
    for (let i = 0; i < n; i++) {
        const a = BigInt(nums[i]) % MOD;
        powA[i][0] = 1n;
        for (let t = 1; t <= m; t++) {
            powA[i][t] = (powA[i][t - 1] * a) % MOD;
        }
    }

    const M = m;

    // 3D DP array: cur[r][flag][ones]
    // r = remaining slots to fill
    // flag = carry bits from binary sum
    // ones = number of set bits so far
    let cur = Array.from({ length: M + 1 }, () =>
        Array.from({ length: M + 1 }, () =>
            Array(M + 1).fill(0n)
        )
    );
    cur[M][0][0] = 1n; // Start with m slots to fill, no carry, no set bits

    // Process each number in nums
    for (let i = 0; i < n; i++) {
        // Prepare next DP state
        let nxt = Array.from({ length: M + 1 }, () =>
            Array.from({ length: M + 1 }, () =>
                Array(M + 1).fill(0n)
            )
        );

        // Iterate over all current DP states
        for (let r = 0; r <= M; r++) {
            for (let flag = 0; flag <= M; flag++) {
                for (let ones = 0; ones <= M; ones++) {
                    let val = cur[r][flag][ones];
                    if (val === 0n) continue;

                    // Try using t copies of nums[i] (from 0 to r)
                    for (let t = 0; t <= r; t++) {
                        let newr = r - t;
                        let sum = flag + t;
                        let bit = sum & 1; // Least significant bit
                        let newones = ones + bit;
                        if (newones > M) continue;

                        let newflag = sum >>> 1; // Carry to next bit
                        let mult = (comp[r][t] * powA[i][t]) % MOD;
                        let add = (val * mult) % MOD;

                        // Update next DP state
                        nxt[newr][newflag][newones] = (nxt[newr][newflag][newones] + add) % MOD;
                    }
                }
            }
        }

        // Move to next state
        cur = nxt;
    }

    // Final aggregation: check all states where r == 0 (sequence complete)
    let ans = 0n;
    for (let flag = 0; flag <= M; flag++) {
        for (let ones = 0; ones <= M; ones++) {
            let val = cur[0][flag][ones];
            if (val === 0n) continue;

            // Add remaining set bits from final carry
            let extra = popcount(flag);
            if (ones + extra === k) {
                ans = (ans + val) % MOD;
            }
        }
    }

    return Number(ans);

    // Count set bits in an integer
    function popcount(x) {
        let c = 0;
        while (x > 0) {
            c += x & 1;
            x >>>= 1;
        }
        return c;
    }
};