我来搜索一下 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 实现试填法 快速幂javaclass Solution {// 快速幂计算 a^b % modprivate 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的位下标之和// 从高位到低位试填最低位 i0 单独处理// __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^01指数为0n | 1; // 最低位填1}// 剩余的 k 个幂次由 n 的低 k 个1的位下标补充while (k-- 0) {// n -n 得到最低位的1long lowbit n -n;// 该1的位下标res Long.numberOfTrailingZeros(lowbit);// 去掉最低位的1n 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];// 前 to1 个元素的幂次和 - 前 from 个元素的幂次和 [from, to] 区间的幂次和long power calc(to 1) - calc(from);ans[i] (int) qpow(2, power, mod);}return ans;}}核心思路图解数字 n 的强数组 n 的二进制中所有1对应的 2^ibig_nums: [1] [2] [1,2] [4] [1,4] [2,4] [1,2,4] [8] ...↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓幂次数组: [0] [1] [0,1] [2] [0,2] [1,2] [0,1,2] [3] ...问题转化为求幂次数组区间和然后 2^和 % modcalc(k): 求 big_nums 前 k 个元素的幂次之和 所有数字 1..n 的二进制中1的位下标之和前k个复杂度分析指标 复杂度时间 O(q \cdot \log U)其中 q 是查询数U \approx 10^{15}空间 O(1)试填法从高位到低位逐位确定每位 O(1)最多 50 位因为 2^{50} 10^{15}所以单次 calc 约 O(\log U)。