3145. 大数组元素的乘积（24.8.23）
前言
今日每日一题难度较大，根据 灵茶山艾府 的代码进行学习研究
题目
一个非负整数x的强数组指的是满足元为 2 的且元素总和为x的有序数。下表说明了如何确定强数的示例,可以证明,对应的数组是独一无二的。
| 数字 | 二进制表示 | 强数组 |
|---|---|---|
| 1 | 00001 | [1] |
| 8 | 01000 | [8] |
| 10 | 01010 | [2, 8] |
| 13 | 01101 | [1, 4, 8] |
| 23 | 10111 | [1, 2, 4, 16] |
我们将一个升序的正整数 1(即 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 = [[3,7]]
输出：[4]
解释：
只有一个查询。
big_ums[1..3] = [2.1.2]，它们的积为 4，结果为4 mod 7 = 4。
示例 2:
输入：queries = [[1,2,5],[3,7,3],[7,7,4]]
输出：[2,2]
解释：
有两个查询。
第一个查询：big_nua[2..5] = [1.2,4,2]，它们的所积为 8，结果为8 mod 3 = 2。
第二个查询：big_nuas[7]，结果为2 mod 4 = 2。
提示:
· 1 <= queries.length <= 500
· queries[i].length = 3
· queris[i][0] <= quers[i][1] <= 10^15
· 1 <= queries[i][2] <= 10^5
解题思路
强数组：
###概念说明：###（1） 强数组 ：例如： 10 【强数组为：2，8】位数： 4 | 3 | 2 | 1 | 0 【二进制的位数】转化： 0 | 1 | 0 | 1 | 0 【转化为二进制】强数组： 第 1 位是 1 则有一个强数组的数：2^1 --> 2 第 3 位是 3 则有一个强数组的数：2^3 --> 8强数组为这些数的集合：[2,8]总结为：第 i 位是 1 则有一个强数组的数：2^i 由这样的数组成的集合为 强数组###（2） big_nums ：由 1，2，3，4，...，n 的强数组拼接而成的强数组###（3） (big_nums[fromi] * big_nums[fromi + 1] * ... * big_nums[toi]) % modi ：假设 big_nums 第 i 个数的幂表示为 2^k(i)假设 queries[i] = [a, b, modi]设：SUM( fromi , toi ) = big_nums[fromi] * big_nums[fromi + 1] * ... * big_nums[toi]则计算变为： SUM( a , b ) % modi对于此处 SUM 而言：SUM( a , b ) = big_nums[a] * big_nums[a + 1] * ... * big_nums[b]= (2^k(a))*(2^k(a+1))*(2^k(a+2))*...*(2^k(b))= 2^(k(a)+k(a+1)+...+k(b))###问题转化：通过上述的（3），我们可以将 big_nums 记录强数组 转化为 记录强数组当中 2 的幂将 big_nums 之间的乘 转化为 幂的加法， 假设强数组前 i 个幂之和为 sum(i),则上方（3）中的SUM( a , b )=2^[sum(b)-sum(a)]
###列举：
数字(n) 强数组 转化为2的幂 big_nums(转化后的) 数组当中的个数(i) sum(i)
0 [] [] [] 0 0
1 [1] [0] [0] 1 0
2 [2] [1] [0,1] 2 1
3 [1,2] [0,1] [0,1,0,1] 4 2
4 [4] [2] [0,1,0,1,2] 5 4
5 [1,4] [0,2] [0,1,0,1,2,0,2] 7 6
6 [2,4] [1,2] [0,1,0,1,2,0,2,1,2] 9 9
7 [1,2,4] [0,1,2] [0,1,0,1,2,0,2,1,2,0,1,2] 12 12
8 [8] [3] [0,1,0,1,2,0,2,1,2,0,1,2,3] 13 15
... [...] [...] [0,1,0,1,2,0,2,1,2,0,1,2,3,...] ??? ???###规律找寻：对于 i 而言，其值是其二进制当中 1 出现的个数：!!! 设 前 2^i 个强数组有 a(i) 个,则 前 2^(i+1) 个强数组有 a(i+1) 个
**********************数字(n) 强数组 转化为2的幂
0 [] []
1 [1] [0]
2 [2] [1]
3 [1,2] [0,1] 4 [4] [2] = [ ] + [2]
5 [1,4] [0,2] = [0] + [2]
6 [2,4] [1,2] = [1] + [2]
7 [1,2,4] [0,1,2] = [0,1] + [2] a(i+1) = a(i)*2 + 2^i**********************
前 1 个强数组的个数为 0
前 2 个强数组的个数为 1
前 4 个强数组的个数为 4
前 8 个强数组的个数为 12 a(0)=0 a(1)=1 a(2)=4 a(3)=12
==> a(i+1) = a(i)*2 + 2^i ==>a(i+1)/(2^(i+1)) = a(i)/(2^i) + 1/2 【等差数列】
--> a(i)=i*2^(i-1)求前 k 个幂之和，则需要求的 k 个幂次是由多少个强数组组成的，即要找到一个最大的 n 使得 a(n)<=k
!!! 采用 试填法 见下方代码求 幂次 之和：同上方 a() 的推倒过程
sum(i) = (i*(i-1)/2)*2^(i-1)代码
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(long long k) {long long res = 0, n = 0, cnt1 = 0, sum_i = 0;for (long long i = __lg(k + 1); i; i--) {long long 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 的个数n |= 1LL << i; // 填 1}}// 最低位单独计算if (cnt1 <= k) {k -= cnt1;res += sum_i;n |= 1; // 最低位填 1}// 剩余的 k 个幂次，由 n 的低 k 个 1 补充while (k--) {res += __builtin_ctzll(n);n &= n - 1; // 去掉最低位的 1（置为 0）}return res;}public:vector<int> findProductsOfElements(vector<vector<long long>>& queries) {vector<int> ans;for (auto& q : queries) {auto r = sum(q[1] + 1);auto l = sum(q[0]);ans.push_back(pow(2, r - l, q[2]));}return ans;}
};