当前位置：首页 > news >正文

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

news 2026/6/11 8:56:18

我来搜索一下 LeetCode 3145 这道题的详细信息
根据搜索结果，我来为你提供 LeetCode 3145「大数组元素的乘积」的 Java 实现。

题目理解

- 强数组：一个非负整数 `x` 的强数组是由 `x` 的二进制表示中所有为1的位对应的2的幂组成的有序数组。例如 `10 = 1010₂`，强数组为 `[2, 8]`。
- big_nums：将每个正整数的强数组拼接起来：`[1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, ...]`
- 查询 `queries[i] = [from, to, mod]`，求 `big_nums[from..to]` 的乘积对 `mod` 取模

关键洞察：big_nums 中每个元素都是 2 的幂，所以乘积也是 2 的幂。设幂次之和为 `power`，答案就是 `2^power % mod`。因此问题转化为求区间内所有元素的幂次之和。

Java 实现（试填法 + 快速幂）

```java
class Solution {

// 快速幂：计算 a^b % mod
private long qpow(long a, long b, long mod) {
long res = 1 % mod;
a %= mod;
while (b > 0) {
if ((b & 1) == 1) {
res = res * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return res;
}

/**
* 计算 big_nums 前 k 个元素的幂次之和
* 即：big_nums[0] 到 big_nums[k-1] 中所有 2 的幂的指数之和
*
* 核心思想（试填法）：
* 对于数字 n，其二进制表示中1的个数为 popcount(n)
* 前 n 个正整数的强数组总长度 = 所有 popcount(1..n) 之和
*
* 我们维护：
* - n: 当前已确定的数字（二进制形式）
* - cnt1: n 中已填的1的个数
* - sum_i: n 中已填的1的位下标之和
*
* 从高位到低位试填，如果填1后新增的幂次个数不超过k，就填1
*/
private long calc(long k) {
long res = 0; // 幂次之和
long n = 0; // 当前确定的数字
long cnt1 = 0; // 已填的1的个数
long sum_i = 0; // 已填的1的位下标之和

// 从高位到低位试填（最低位 i=0 单独处理）
// __lg(k + 1) 找到最高可能的位数
for (long i = 63 - Long.numberOfLeadingZeros(k + 1); i > 0; i--) {
// 如果在第 i 位填1，新增的幂次个数：
// 1. 之前已填的 cnt1 个1，每个都会在新分支中重复 2^i 次 -> cnt1 * 2^i
// 2. 新填的1在第 i 位，会在 [0, 2^i) 的每个数字中出现一次 -> i * 2^(i-1)
long c = (cnt1 << i) + (i << (i - 1));

if (c <= k) {
k -= c;
// 新增幂次之和：
// 1. 之前已填的 sum_i 个幂次，每个重复 2^i 次 -> sum_i * 2^i
// 2. 新填的第 i 位，在 [0, 2^i) 中每个数字贡献 i -> i * (i-1)/2 * 2^(i-1)
res += (sum_i << i) + ((i * (i - 1) / 2) << (i - 1));
sum_i += i;
cnt1++;
n |= 1L << i; // 在第 i 位填1
}
}

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

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

return res;
}

public int[] findProductsOfElements(long[][] queries) {
int m = queries.length;
int[] ans = new int[m];

for (int i = 0; i < m; i++) {
long from = queries[i][0];
long to = queries[i][1];
long mod = queries[i][2];

// 前 to+1 个元素的幂次和 - 前 from 个元素的幂次和 = [from, to] 区间的幂次和
long power = calc(to + 1) - calc(from);

ans[i] = (int) qpow(2, power, mod);
}

return ans;
}
}
```