我来为你提供 LeetCode 3145「大数组元素的乘积」的 TypeScript 实现。TypeScript 实现typescriptfunction findProductsOfElements(queries: number[][]): number[] {const MOD 1e9 7;// 快速幂计算 a^b % modfunction 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^iconst 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^01指数为0n | 1n;}// 剩余 k 个幂次由 n 的低 k 个1的位下标补充while (k 0n) {// n -n 得到最低位的1const lowbit n (-n);// 该1的位下标const tz BigInt(ctz(Number(lowbit)));res tz;// 去掉最低位的1n n - 1n;k - 1n;}return res;}// 计算二进制末尾0的个数ctz: count trailing zerosfunction 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;}更简洁的版本参考灵茶山艾府的试填法typescriptfunction 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 个元素的幂次之和试填法从高位到低位构造数字复杂度指标 复杂度时间 O(q \cdot \log U)约 O(q \cdot 50)空间 O(1)TypeScript 中使用 BigInt 处理大数因为 k 最大可达 10^{15}需要 64 位整数精度。
Kimi LeetCode 3145. 大数组元素的乘积 TypeScript实现
我来为你提供 LeetCode 3145「大数组元素的乘积」的 TypeScript 实现。TypeScript 实现typescriptfunction findProductsOfElements(queries: number[][]): number[] {const MOD 1e9 7;// 快速幂计算 a^b % modfunction 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^iconst 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^01指数为0n | 1n;}// 剩余 k 个幂次由 n 的低 k 个1的位下标补充while (k 0n) {// n -n 得到最低位的1const lowbit n (-n);// 该1的位下标const tz BigInt(ctz(Number(lowbit)));res tz;// 去掉最低位的1n n - 1n;k - 1n;}return res;}// 计算二进制末尾0的个数ctz: count trailing zerosfunction 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;}更简洁的版本参考灵茶山艾府的试填法typescriptfunction 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 个元素的幂次之和试填法从高位到低位构造数字复杂度指标 复杂度时间 O(q \cdot \log U)约 O(q \cdot 50)空间 O(1)TypeScript 中使用 BigInt 处理大数因为 k 最大可达 10^{15}需要 64 位整数精度。
