Kimi LeetCode 3145. 大数组元素的乘积 TypeScript实现

稚辉君.MCA.P9.JAVA

25人浏览 · 2026-06-11 07:27:43

稚辉君.MCA.P9.JAVA · 2026-06-11 07:27:43 发布

我来为你提供 LeetCode 3145「大数组元素的乘积」的 TypeScript 实现。

TypeScript 实现

```typescript
function findProductsOfElements(queries: number[][]): number[] {
const MOD = 1e9 + 7;

// 快速幂：计算 a^b % mod
function qpow(a: bigint, b: bigint, mod: number): number {
let res: bigint = 1n % BigInt(mod);
a = a % BigInt(mod);
while (b > 0n) {
if ((b & 1n) === 1n) {
res = res * a % BigInt(mod);
}
a = a * a % BigInt(mod);
b >>= 1n;
}
return Number(res);
}

/**
* 计算 big_nums 前 k 个元素的幂次之和
* big_nums 中每个元素都是 2^i 的形式，乘积 = 2^(所有幂次之和)
*/
function calc(k: bigint): bigint {
let res: bigint = 0n; // 幂次之和
let n: bigint = 0n; // 当前确定的数字
let cnt1: bigint = 0n; // 已填的1的个数
let sum_i: bigint = 0n; // 已填的1的位下标之和

// 从高位到低位试填
// 最高可能的位数：找到最大的 i 使得 (cnt1 << i) + (i << (i-1)) 有意义
// 对于 k <= 1e15，最多约 50 位
let maxBit = 0;
let temp = k;
while (temp > 0n) {
maxBit++;
temp >>= 1n;
}
maxBit = Math.max(maxBit, 1);

for (let i = maxBit; i > 0; i--) {
const bi = BigInt(i);
const twoPowI = 1n << bi; // 2^i
const twoPowI_1 = 1n << (bi - 1n); // 2^(i-1)

// 如果在第 i 位填1，新增的幂次个数
const c = (cnt1 << bi) + (bi * twoPowI_1);

if (c <= k) {
k -= c;
// 新增幂次之和
res += (sum_i << bi) + ((bi * (bi - 1n) / 2n) * twoPowI_1);
sum_i += bi;
cnt1 += 1n;
n |= 1n << bi;
}
}

// 最低位（i = 0）单独处理
if (cnt1 <= k) {
k -= cnt1;
res += sum_i; // 最低位填1，已有1贡献0次幂（2^0=1，指数为0）
n |= 1n;
}

// 剩余 k 个幂次，由 n 的低 k 个1的位下标补充
while (k > 0n) {
// n & -n 得到最低位的1
const lowbit = n & (-n);
// 该1的位下标
const tz = BigInt(ctz(Number(lowbit)));
res += tz;
// 去掉最低位的1
n &= n - 1n;
k -= 1n;
}

return res;
}

// 计算二进制末尾0的个数（ctz: count trailing zeros）
function ctz(x: number): number {
if (x === 0) return 0;
let count = 0;
while ((x & 1) === 0) {
count++;
x >>= 1;
}
return count;
}

const ans: number[] = [];
for (const [from, to, mod] of queries) {
const power = calc(BigInt(to) + 1n) - calc(BigInt(from));
ans.push(qpow(2n, power, mod));
}

return ans;
}
```

更简洁的版本（参考灵茶山艾府的试填法）

```typescript
function findProductsOfElements(queries: number[][]): number[] {
// 快速幂
function qpow(a: bigint, b: bigint, mod: number): number {
let res = 1n % BigInt(mod);
a %= BigInt(mod);
while (b > 0n) {
if ((b & 1n) === 1n) res = res * a % BigInt(mod);
a = a * a % BigInt(mod);
b >>= 1n;
}
return Number(res);
}

// 计算 big_nums 前 k 个元素的幂次之和
function calc(k: bigint): bigint {
let res = 0n;
let n = 0n; // 当前构造的数字
let cnt1 = 0n; // n 中1的个数
let sum_i = 0n; // n 中1的位下标之和

// 从高位到低位试填
for (let i = 50; i > 0; i--) {
const bi = BigInt(i);
const add = (cnt1 << bi) + (bi << (bi - 1n)); // 填1新增的幂次个数

if (add <= k) {
k -= add;
res += (sum_i << bi) + ((bi * (bi - 1n) / 2n) << (bi - 1n));
sum_i += bi;
cnt1 += 1n;
n |= 1n << bi;
}
}

// 最低位
if (cnt1 <= k) {
k -= cnt1;
res += sum_i;
n |= 1n;
}

// 剩余 k 个
while (k > 0n) {
const lowbit = n & -n;
res += BigInt(Math.log2(Number(lowbit)));
n ^= lowbit;
k -= 1n;
}

return res;
}

return queries.map(([from, to, mod]) => {
const power = calc(BigInt(to) + 1n) - calc(BigInt(from));
return qpow(2n, power, mod);
});
}
```

核心思路

```
big_nums: 每个正整数的强数组（二进制中1对应的2^i）拼接而成

1 -> [1] -> 幂次: [0]
2 -> [2] -> 幂次: [1]
3 -> [1,2] -> 幂次: [0,1]
4 -> [4] -> 幂次: [2]
5 -> [1,4] -> 幂次: [0,2]
...

big_nums 中每个元素都是 2^i，所以乘积 = 2^(幂次之和)

calc(k): 求前 k 个元素的幂次之和（试填法从高位到低位构造数字）
```

复杂度