Find Products of Elements of Big Array

A powerful array for an integer x is the shortest sorted array of powers of two that sum up to x. For example, the powerful array for 11 is [1, 2, 8].

The array big_nums is created by concatenating the powerful arrays for every positive integer i in ascending order: 1, 2, 3, and so forth. Thus, big_nums starts as [1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, ...].

You are given a 2D integer matrix queries, where for queries[i] = [fromi, toi, modi] you should calculate (big_nums[fromi] * big_nums[fromi + 1] * ... * big_nums[toi]) % modi.

Return an integer array answer such that answer[i] is the answer to the ith query.

Example 1:

Input: queries = [[1,3,7]]

Output: [4]

Explanation:

There is one query.

big_nums[1..3] = [2,1,2]. The product of them is 4. The remainder of 4 under 7 is 4.

Example 2:

Input: queries = [[2,5,3],[7,7,4]]

Output: [2,2]

Explanation:

There are two queries.

First query: big_nums[2..5] = [1,2,4,1]. The product of them is 8. The remainder of 8 under 3 is 2.

Second query: big_nums[7] = 2. The remainder of 2 under 4 is 2.

Constraints:

• 1 <= queries.length <= 500
• queries[i].length == 3
• 0 <= queries[i][0] <= queries[i][1] <= 1015
• 1 <= queries[i][2] <= 105

解题思路

  看完了题解感觉也不是那么难，但代码超难写。赛时罚坐了 1 个多小时都没想到正解，感觉最近变笨了好多简单题都不会做。

  为了方便这里规定强数组的下标从 $1$ 开始，且下标为 $0$ 的元素是 $0$。因此每个询问对应的三元组 $(p_0,p_1,p_2)$，应有 $p_0 \gets p_0+1$ 和 $p_1 \gets p_1+1$。

  容易知道强数组中的每个元素表示从数值 $0$ 开始的每个数，在二进制下为 $1$ 的位对应的 $2$ 的幂。因此要求的乘积也是 $2$ 的多少次幂，为此我们只需关注强数组 $[p_0,p_1]$ 内次幂的总和即可。而下标 $x$ 则表示从数值 $0$ 到某个数 $v$ 的某个二进制位内，$1$ 的数量。现在的问题是给定 $x$ 如何快速求出对应的 $v$，即找到最小的一个 $v$，使得 $0 \sim v$ 在二进制下 $1$ 的数量大于等于 $x$。

  显然可以二分出 $v$，那么对于二分出的某个值 $\text{mid}$ 如何快速知道 $0 \sim \text{mid}$ 在二进制下 $1$ 的数量？规定二分的范围是 $\left[0, 10^{15}\right]$，其中 $2^{49} < 10^{15} < 2^{50}$。对此我们可以分别统计 $0 \sim \text{mid}$ 在第 $0$ 位到第 $49$ 位的 $1$ 的数量。打表可以发现规律，对于第 $i$ 位，$2^i$ 个 $0$ 与 $2^i$ 个 $1$ 依次交替出现，因此第 $i$ 位 $1$ 的数量就是 $\left\lfloor \frac{\text{mid}+1}{2^{i+1}} \right\rfloor \times 2^{i} \, + \, \left[ x \bmod 2^{i+1}> 2^{i} \right] \cdot \left( x \bmod 2^{i} \right)$。

  对此我们可以先求出 $p_0$ 对应的 $l$，及 $p_1$ 对应的 $r$。如果 $l = r$，先求出 $0 \sim l-1$ 在二进制下 $1$ 的数量，记为 $c$。暴力枚举 $l$ 的二进制数位，当第 $i$ 位是 $1$ 时，令 $c \gets c + 1$，如果 $p_0 \leq c \leq p_1$ 就累加 $i$。

  如果 $l < r$，先统计 $l$ 在强数组内为 $1$ 的位，具体做法为先求出 $0 \sim l-1$ 在二进制下 $1$ 的数量 $c$，暴力枚举 $l$ 的二进制数位，当第 $i$ 位是 $1$ 时，令 $c \gets c + 1$，如果 $p_0 \leq c$ 就累加 $i$。同理统计 $r$ 在强数组内为 $1$ 的位，具体做法为先求出 $0 \sim r-1$ 在二进制下 $1$ 的数量 $c$，暴力枚举 $r$ 的二进制数位，当第 $i$ 位是 $1$ 时，令 $c \gets c + 1$，如果 $c \leq p_1$ 就累加 $i$。最后统计 $[l+1,r-1]$ 为 $1$ 的位的和，可以用前缀和的思想，分别求 $0 \sim r$ 和 $0 \sim l-1$ 为 $1$ 的位的和，然后做减法。只需在求二进制下第 $i$ 位为 $1$ 的数量的基础上乘上 $i$ 即可。

  在累加了次幂后，只需用快速幂计算 $2$ 的多少次幂即可。

  AC 代码如下，时间复杂度为 $O(q \log^2{R})$，其中 $R = 10^{15}$：

class Solution {
public:
    vector<int> findProductsOfElements(vector<vector<long long>>& queries) {
        vector<int> ans;
        for (auto &p : queries) {
            p[0]++, p[1]++;
            function<long long(long long)> get = [&](long long x) {
                x++;
                long long s = 0;
                for (int i = 0; i <= 49; i++) {
                    s += x / (1ll << i + 1) * (1ll << i);
                    if (x % (1ll << i + 1) > 1ll << i) s += x % (1ll << i);
                }
                return s;
            };
            function<long long(long long)> find = [&](long long x) {
                long long l = 0, r = 1e15;
                while (l < r) {
                    long long mid = l + r >> 1;
                    if (get(mid) >= x) r = mid;
                    else l = mid + 1;
                }
                return l;
            };
            function<int(int, long long, int)> qmi = [&](int a, long long k, int p) {
                int ret = 1 % p;
                while (k) {
                    if (k & 1) ret = 1ll * ret * a % p;
                    a = 1ll * a * a % p;
                    k >>= 1;
                }
                return ret;
            };
            long long l = find(p[0]), r = find(p[1]);
            if (l == r) {
                long long s = 0, c = get(l - 1);
                for (int i = 0; i <= 49; i++) {
                    if (l >> i & 1) {
                        c++;
                        if (c >= p[0] && c <= p[1]) s += i;
                    }
                }
                ans.push_back(qmi(2, s, p[2]));
            }
            else {
                long long s = 0, c = get(l - 1);
                for (int i = 0; i <= 49; i++) {
                    if (l >> i & 1) {
                        c++;
                        if (c >= p[0]) s += i;
                    }
                }
                c = get(r - 1);
                for (int i = 0; i <= 49; i++) {
                    if (r >> i & 1) {
                        c++;
                        if (c <= p[1]) s += i;
                    }
                }
                function<long long(long long)> get = [&](long long x) {
                    x++;
                    long long s = 0;
                    for (int i = 0; i <= 49; i++) {
                        long long c = x / (1ll << i + 1) * (1ll << i);
                        if (x % (1ll << i + 1) > 1ll << i) c += x % (1ll << i);
                        s += i * c;
                    }
                    return s;
                };
                if (l + 1 <= r - 1) s += get(r - 1) - get(l);
                ans.push_back(qmi(2, s, p[2]));
            }
        }
        return ans;
    }
};

参考资料

  第 130 场力扣夜喵双周赛 - 力扣（LeetCode）：https://leetcode.cn/circle/discuss/FpYgO6/view/L5Vk47/