题目：
一个非负整数 x 的 强数组 指的是满足元素为 2 的幂且元素总和为 x 的最短有序数组。下表说明了如何确定 强数组 的示例。可以证明，x 对应的强数组是独一无二的。
| 数字 | 二进制表示 | 强数组 |
|---|---|---|
| 1 | 00001 | [1] |
| 8 | 01000 | [8] |
| 10 | 01010 | [2, 8] |
| 13 | 01101 | [1, 4, 8] |
| 23 | 10111 | [1, 2, 4, 16] |
我们将每一个升序的正整数 i （即1，2，3等等）的 强数组 连接得到数组 big_nums ，big_nums 开始部分为 [1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, ...] 。
给你一个二维整数数组 queries ，其中 queries[i] = [fromi, toi, modi] ，你需要计算 (big_nums[fromi] * big_nums[fromi + 1] * ... * big_nums[toi]) % modi 。
请你返回一个整数数组 answer ，其中 answer[i] 是第 i 个查询的答案。
示例 1：
输入：queries = [[1,3,7]]
输出：[4]
解释：
只有一个查询。
big_nums[1..3] = [2,1,2] 。它们的乘积为 4。结果为 4 % 7 = 4。
示例 2：
输入：queries = [[2,5,3],[7,7,4]]
输出：[2,2]
解释：
有两个查询。
第一个查询：big_nums[2..5] = [1,2,4,1] 。它们的乘积为 8 。结果为 8 % 3 = 2。
第二个查询：big_nums[7] = 2 。结果为 2 % 4 = 2。
提示：
1 <= queries.length <= 500queries[i].length == 30 <= queries[i][0] <= queries[i][1] <= 10151 <= queries[i][2] <= 105
思路：
真看不懂一点，直接看LeetCode题解吧
根据题意可知，大数组由升序的正整数组成。那么对于 query 中的 from 与 to，希望能找出分别属于哪一个数字。记 l1 与 l2 分别表示数字 l 贡献出的序列的左端点以及右端点，假设 from 实际对应整数 l 贡献出的序列中，那么有 l1 <= from <= l2 。同理可得到 r1 <= to <= r2 。不难发现答案可以分为三部分统计：
[from .. l2]
[l2 + 1 .. r1 − 1]
[r1 .. to]
其中 [from .. l2] 与 [r1 .. to] 部分可以直接暴力求解，因为一个整数 x 最多能贡献 logx 个数字到大数组中。而 [l2 + 1 .. r1 − 1] 恰好就是整数 l + 1 .. r − 1 之间所贡献出的数字。在此之前，我们先讨论如何找到 from 所处的整数。
由于整数 [1..x] 所贡献出的序列长度随着 x 增大有单调性，可以采用二分查找。然后对于 [1..x] 所贡献出的序列长度，转化为求小于等于 x 的所有数字数位中 1 的个数之和，可以采用类似数位 DP 的方式进行计数。从高位开始枚举 x 的二进制，并假设目前是一直受到数字的上界限制的，如果这一位 i 为 1，那么此时有两种方案可以枚举：
枚举这一位为 1，继续遍历。
枚举这一位为 0，因为不满足上界了所以后面的数位可以任意选择。此时答案有两部分，对于小于 i 的数位，每一位都可以贡献出 2^(i−1) 个 1，一共有 i 个数位，故此部分贡献为 i * 2^(i−1) 。而对于数位 i 前面的部分，记枚举过来一共有 sum 个 1，可贡献 sum * 2^i 个 1。
所以我们只需要在枚举 x 中二进制为 1 的时候，统计下答案即可。
以数字 12，二进制为 1100 进行举例。第一位为 1，此时先计算假设第一位为 0 时的答案，此时还剩 3 个数位可以任意填，当每个数位试填为 1 时，有 2^(3−1) = 4 种方案，故三个数位一共有 12 次贡献。然后继续以第一位为 1 进行后续枚举，第二位也为 1，假设第二位为 0，还剩下 2 个数位可以任意填一共可以有 4 次贡献，并且需要加上此时的前缀 10 有一个 1 并且能出现 4 次。继续以第二位为 1继续枚举，此时没有数位 1 了，直接枚举到结束，再加上 1100 中包含的两个 1。综上所述，小于等于 12 的所有整数的数位中含有 12 + 4 + 4 + 2 = 22 个 1。
继续讨论 [l2 + 1 .. r1 − 1] 这部分，由于 2^a * 2^b = 2^(a + b)，在计算这部分的乘积时，我们将其转化为用 2 的幂次进行表示，然后把幂加起来，最后再进行幂运算，从而把问题转化为求整数 [l + 1 .. r − 1] 之间所有数位之和。比如数字 6 的二进制为 110，在此题中的数位之和为 1 + 2 = 3，有 4 × 2 = 2^(1 + 2)。而 [l + 1 .. r − 1] 可转化为求 [1 .. r − 1] − [1 .. l]，我们同样可以采用类似数位 DP 的方法进行计数，与上述讨论类似，只不过每次贡献不是 1 而是其相应的数位了。这里不做赘述，详情参考代码中 countPow 函数。
综上所述，将三部分答案统计即可。
代码：
class Solution {
public:
// 计算 <= x 所有数的数位1的和
long long countOne(long long x) {
long long res = 0;
int sum = 0;
for (int i = 60; i >= 0; i--) {
if (1LL << i & x) {
res += 1LL * sum * (1LL << i);
sum += 1;
if (i > 0) {
res += 1LL * i * (1LL << (i - 1));
}
}
}
res += sum;
return res;
}
// 计算 <= x 所有数的数位对幂的贡献之和
long long countPow(long long x) {
long long res = 0;
int sum = 0;
for (int i = 60; i >= 0; i--) {
if (1LL << i & x) {
res += 1LL * sum * (1LL << i);
sum += i;
if (i > 0) {
res += 1LL * i * (i - 1) / 2 * (1LL << (i - 1));
}
}
}
res += sum;
return res;
}
int pow_mod(long long x, long long y, int mod) {
int res = 1;
while (y) {
if (y & 1) {
res = res * x % mod;
}
x = x * x % mod;
y >>= 1;
}
return res;
}
long long mid_check(long long x) {
long long l = 1, r = 1e15;
while (l < r) {
long long mid = (l + r) >> 1;
if (countOne(mid) >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return r;
}
vector<int> findProductsOfElements(vector<vector<long long>>& queries) {
vector<int> ans;
for (int i = 0; i < queries.size(); i++) {
// 偏移让数组下标从1开始
queries[i][0]++;
queries[i][1]++;
long long l = mid_check(queries[i][0]);
long long r = mid_check(queries[i][1]);
int mod = queries[i][2];
long long res = 1;
long long pre = countOne(l - 1);
for (int j = 0; j < 60; j++) {
if (1LL << j & l) {
pre++;
if (pre >= queries[i][0] && pre <= queries[i][1]) {
res = res * (1LL << j) % mod;
}
}
}
if (r > l) {
long long bac = countOne(r - 1);
for (int j = 0; j < 60; j++) {
if (1LL << j & r) {
bac++;
if (bac >= queries[i][0] && bac <= queries[i][1]) {
res = res * (1LL << j) % mod;
}
}
}
}
if (r - l > 1) {
long long xs = countPow(r - 1) - countPow(l);
res = res * pow_mod(2LL, xs, mod) % mod;
}
ans.push_back(res);
}
return ans;
}
};