class Solution {
public:
vector<int> findProductsOfElements(vector<vector<long long>>& queries) {
}
};
100295. 大数组元素的乘积
一个整数 x 的 强数组 指的是满足和为 x 的二的幂的最短有序数组。比方说，11 的强数组为 [1, 2, 8] 。
我们将每一个正整数 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原站题解
rust 解法, 执行用时: 32 ms, 内存消耗: 2.2 MB, 提交时间: 2024-08-23 09:33:36
impl Solution {
pub fn find_products_of_elements(queries: Vec<Vec<i64>>) -> Vec<i32> {
let mut ans = Vec::new();
for query in queries.iter() {
// 偏移让数组下标从1开始
let mut query = query.clone();
query[0] += 1;
query[1] += 1;
let l = Self::mid_check(query[0]);
let r = Self::mid_check(query[1]);
let mod_val = query[2];
let mut res = 1i64;
let mut pre = Self::count_one(l - 1);
for j in 0..60 {
if (1i64 << j) & l != 0 {
pre += 1;
if pre >= query[0] && pre <= query[1] {
res = res * (1i64 << j) % mod_val;
}
}
}
if r > l {
let mut bac = Self::count_one(r - 1);
for j in 0..60 {
if (1i64 << j) & r != 0 {
bac += 1;
if bac >= query[0] && bac <= query[1] {
res = res * (1i64 << j) % mod_val;
}
}
}
}
if r - l > 1 {
let xs = Self::count_pow(r - 1) - Self::count_pow(l);
res = res * Self::pow_mod(2, xs, mod_val) % mod_val;
}
ans.push(res as i32);
}
ans
}
// 计算 <= x 所有数的数位1的和
fn count_one(mut x: i64) -> i64 {
let mut res = 0i64;
let mut sum = 0i64;
for i in (0..=60).rev() {
if (1i64 << i) & x != 0 {
res += sum * (1i64 << i);
sum += 1;
if i > 0 {
res += i * (1i64 << (i - 1));
}
}
}
res += sum;
res
}
// 计算 <= x 所有数的数位对幂的贡献之和
fn count_pow(mut x: i64) -> i64 {
let mut res = 0i64;
let mut sum = 0i64;
for i in (0..=60).rev() {
if (1i64 << i) & x != 0 {
res += sum * (1i64 << i);
sum += i;
if i > 0 {
res += i * (i - 1) / 2 * (1i64 << (i - 1));
}
}
}
res += sum;
res
}
fn pow_mod(mut x: i64, mut y: i64, mod_val: i64) -> i64 {
let mut res = 1i64;
while y != 0 {
if y & 1 != 0 {
res = res * x % mod_val;
}
x = x * x % mod_val;
y >>= 1;
}
res
}
fn mid_check(x: i64) -> i64 {
let mut l = 1i64;
let mut r = 1_000_000_000_000_000i64;
while l < r {
let mid = (l + r) >> 1;
if Self::count_one(mid) >= x {
r = mid;
} else {
l = mid + 1;
}
}
r
}
}
python3 解法, 执行用时: 57 ms, 内存消耗: 16.7 MB, 提交时间: 2024-05-13 14:54:27
class Solution:
def findProductsOfElements(self, queries: List[List[int]]) -> List[int]:
def sum_e(k: int) -> int:
res = n = cnt1 = sum_i = 0
for i in range((k + 1).bit_length() - 1, 0, -1):
c = (cnt1 << i) + (i << (i - 1)) # 新增的幂次个数
if c <= k:
k -= c
res += (sum_i << i) + ((i * (i - 1) // 2) << (i - 1))
sum_i += i # 之前填的 1 的幂次之和
cnt1 += 1 # 之前填的 1 的个数
n |= 1 << i # 填 1
# 最低位单独计算
if cnt1 <= k:
k -= cnt1
res += sum_i
n += 1 # 填 1
# 剩余的 k 个幂次，由 n 的低 k 个 1 补充
for _ in range(k):
lb = n & -n
res += lb.bit_length() - 1
n ^= lb
return res
return [pow(2, sum_e(r + 1) - sum_e(l), mod) for l, r, mod in queries]
java 解法, 执行用时: 2 ms, 内存消耗: 43.8 MB, 提交时间: 2024-05-13 14:54:12
class Solution {
public int[] findProductsOfElements(long[][] queries) {
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
long[] q = queries[i];
long er = sumE(q[1] + 1);
long el = sumE(q[0]);
ans[i] = pow(2, er - el, q[2]);
}
return ans;
}
private long sumE(long k) {
long res = 0, n = 0, cnt1 = 0, sumI = 0;
for (long i = 63 - Long.numberOfLeadingZeros(k + 1); i > 0; i--) {
long c = (cnt1 << i) + (i << (i - 1)); // 新增的幂次个数
if (c <= k) {
k -= c;
res += (sumI << i) + ((i * (i - 1) / 2) << (i - 1));
sumI += i; // 之前填的 1 的幂次之和
cnt1++; // 之前填的 1 的个数
n |= 1L << i; // 填 1
}
}
// 最低位单独计算
if (cnt1 <= k) {
k -= cnt1;
res += sumI;
n++; // 填 1
}
// 剩余的 k 个幂次，由 n 的低 k 个 1 补充
while (k-- > 0) {
res += Long.numberOfTrailingZeros(n);
n &= n - 1;
}
return res;
}
private int pow(long x, long n, long mod) {
long res = 1 % mod;
for (; n > 0; n /= 2) {
if (n % 2 == 1) {
res = (res * x) % mod;
}
x = (x * x) % mod;
}
return (int) res;
}
}
cpp 解法, 执行用时: 13 ms, 内存消耗: 26.6 MB, 提交时间: 2024-05-13 14:53:59
class Solution {
int pow(long long x, long long n, long long mod) {
long long res = 1 % mod;
for (; n; n /= 2) {
if (n % 2) {
res = res * x % mod;
}
x = x * x % mod;
}
return res;
}
long long sum_e(long long k) {
long long res = 0, n = 0, cnt1 = 0, sumI = 0;
for (long long i = 63 - __builtin_clzll(k + 1); i; i--) {
long long c = (cnt1 << i) + (i << (i - 1)); // 新增的幂次个数
if (c <= k) {
k -= c;
res += (sumI << i) + ((i * (i - 1) / 2) << (i - 1));
sumI += i; // 之前填的 1 的幂次之和
cnt1++; // 之前填的 1 的个数
n |= 1LL << i; // 填 1
}
}
// 最低位单独计算
if (cnt1 <= k) {
k -= cnt1;
res += sumI;
n++; // 填 1
}
// 剩余的 k 个幂次，由 n 的低 k 个 1 补充
while (k--) {
res += __builtin_ctzll(n);
n &= n - 1;
}
return res;
}
public:
vector<int> findProductsOfElements(vector<vector<long long>>& queries) {
vector<int> ans;
for (auto& q : queries) {
auto er = sum_e(q[1] + 1);
auto el = sum_e(q[0]);
ans.push_back(pow(2, er - el, q[2]));
}
return ans;
}
};
golang 解法, 执行用时: 3 ms, 内存消耗: 3 MB, 提交时间: 2024-05-13 14:53:42
func sumE(k int) (res int) {
var n, cnt1, sumI int
for i := bits.Len(uint(k+1)) - 1; i > 0; i-- {
c := cnt1<<i + i<<(i-1) // 新增的幂次个数
if c <= k {
k -= c
res += sumI<<i + i*(i-1)/2<<(i-1)
sumI += i // 之前填的 1 的幂次之和
cnt1++ // 之前填的 1 的个数
n |= 1 << i // 填 1
}
}
// 最低位单独计算
if cnt1 <= k {
k -= cnt1
res += sumI
n++ // 填 1
}
// 剩余的 k 个幂次，由 n 的低 k 个 1 补充
for ; k > 0; k-- {
res += bits.TrailingZeros(uint(n))
n &= n - 1
}
return
}
func findProductsOfElements(queries [][]int64) []int {
ans := make([]int, len(queries))
for i, q := range queries {
er := sumE(int(q[1]) + 1)
el := sumE(int(q[0]))
ans[i] = pow(2, er-el, int(q[2]))
}
return ans
}
func pow(x, n, mod int) int {
res := 1 % mod
for ; n > 0; n /= 2 {
if n%2 > 0 {
res = res * x % mod
}
x = x * x % mod
}
return res
}