3145：大数组元素的乘积（2859 分）

力扣第 130 场双周赛第 4 题

题目

一个非负整数 x 的 强数组 指的是满足元素为 2 的幂且元素总和为 x 的最短有序数组。下表说明了如何确定 强数组 的示例。可以证明，x 对应的强数组是独一无二的。

我们将每一个升序的正整数 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 <= 500
• queries[i].length == 3
• 0 <= queries[i][0] <= queries[i][1] <= 1015
• 1 <= queries[i][2] <= 105

分析

• 由于 big_nums 的数都是2的幂，令A[i]=log2(big_nums[i])，转为求 A的 [from,to] 区间和，令 g(a) 代表 A[:a] 的和，即转为求 g(to+1) 和 g(from)
• 要求 g(a)，可以先二分找到 a 对应的最后整数 x
  • 先考虑这个问题：令 f(x) 代表 1到 x 所对应的强数组总长度，如何求 f(x)
  • f(x) 其实就是 1到x 的二进制位上 1 的总数， 这可以用贡献法解决：
    • 枚举每个二进制位 i，每 2^(i+1) 个数为一个循环，贡献 2^i 个 1，且都在后 2^i 个数，因此计算有多少个完整循环，并特判最后一个循环即可
  • 于是二分找到第一个 x 使得 f(x)>=a，即是 a 对应的最后整数
• 接着求 g(a)，同样可以用贡献法：
  • 区别仅在于二进制位 i 上的权重位 2^i，因此算出个数后乘以 2^i 即可
  • 注意最后整数 x 的强数组不一定完整，需要特判

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def findProductsOfElements(self, queries: List[List[int]]) -> List[int]:
        def f(x):
            s = 0
            for i in range(x.bit_length()):
                q,r = divmod(x,1<<(i+1))
                s += q*(1<<i)+max(0,r-(1<<i)+1)
            return s
        def get(a):
            x = bisect_left(range(a*2),a,key=f)-1
            s = 0
            for i in range(x.bit_length()):
                q,r = divmod(x,1<<(i+1))
                s += (q*(1<<i)+max(0,r-(1<<i)+1))*i
            A = [i for i in range((x+1).bit_length()) if (x+1)&1<<i]
            return s+sum(A[:a-f(x)])
        return [pow(2,get(b+1)-get(a),mod) for a,b,mod in queries]

718 ms