2438. 二的幂数组中查询范围内的乘积 - 位运算解法

题目：2438. 二的幂数组中查询范围内的乘积

思路：位运算，时间复杂度 O(m + log n * log n)。

C++ 版本：

class Solution {
public:
    vector<int> productQueries(int n, vector<vector<int>>& queries) {
        int mod = 1000000007;
        // 得到元素 n 二进制形式的数组
        vector<int> v;
        while (n != 0) {
            // n&-n 得到的是 n 的最低位
            v.push_back(n & -n);
            n ^= (n & -n);
        }
        int m = v.size();
        // 预处理出所有可能的范围，时间复杂度 O(log n * log n)
        vector<vector<int>> f(m + 1, vector<int>(m + 1, 1));
        for (int i = 1; i <= m; i++) {
            f[i][i] = v[i - 1];
            for (int j = i + 1; j <= m; j++) {
                f[i][j] = (1LL * f[i][j - 1] * v[j - 1]) % mod;
            }
        }
        vector<int> ans;
        for (auto query : queries) {
            ans.push_back(f[query[0] + 1][query[1] + 1]);
        }
        return ans;
    }
};

JAVA 版本：

class Solution {
    public int[] productQueries(int n, int[][] queries) {
        int mod = 1000000007;
        List<Integer> v = new ArrayList<>();
        while (n != 0) {
            v.add(n & -n);
            n ^= (n & -n);
        }
        int m = v.size();
        long[][] f = new long[m + 1][m + 1];
        for (int i = 1; i <= m; i++) {
            f[i][i] = v.get(i - 1);
            for (int j = i + 1; j <= m; j++) {
                f[i][j] = (1L * f[i][j - 1] * v.get(j - 1)) % mod;
            }
        }
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            ans[i] = (int) f[queries[i][0] + 1][queries[i][1] + 1];
        }
        return ans;
    }
}

GO 版本：

func productQueries(n int, queries [][]int) []int {
    mod := 1000000007
    v := []int{}
    for n != 0 {
        lowbit := n & -n
        v = append(v, lowbit)
        n ^= lowbit
    }
    m := len(v)
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, m+1)
    }
    for i := 1; i <= m; i++ {
        f[i][i] = v[i-1]
        for j := i + 1; j <= m; j++ {
            f[i][j] = (f[i][j-1] * v[j-1]) % mod
        }
    }
    ans := make([]int, len(queries))
    for i := 0; i < len(queries); i++ {
        ans[i] = f[queries[i][0]+1][queries[i][1]+1]
    }
    return ans
}