目标
给你一个长度为 n 的整数数组 nums 和一个大小为 q 的二维整数数组 queries，其中 queries[i] = [li, ri, ki, vi]。
对于每个查询，需要按以下步骤依次执行操作：
- 设定 idx = li。
- 当 idx <= ri 时：
- 更新：nums[idx] = (nums[idx] * vi) % (10^9 + 7)。
- 将 idx += ki。
在处理完所有查询后，返回数组 nums 中所有元素的 按位异或 结果。
示例 1：
输入： nums = [1,1,1], queries = [[0,2,1,4]]
输出： 4
解释：
唯一的查询 [0, 2, 1, 4] 将下标 0 到下标 2 的每个元素乘以 4。
数组从 [1, 1, 1] 变为 [4, 4, 4]。
所有元素的异或为 4 ^ 4 ^ 4 = 4。示例 2：
输入： nums = [2,3,1,5,4], queries = [[1,4,2,3],[0,2,1,2]]
输出： 31
解释：
第一个查询 [1, 4, 2, 3] 将下标 1 和 3 的元素乘以 3，数组变为 [2, 9, 1, 15, 4]。
第二个查询 [0, 2, 1, 2] 将下标 0、1 和 2 的元素乘以 2，数组变为 [4, 18, 2, 15, 4]。
所有元素的异或为 4 ^ 18 ^ 2 ^ 15 ^ 4 = 31。说明：
- 1 <= n == nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 1 <= q == queries.length <= 10^5
- queries[i] = [li, ri, ki, vi]
- 0 <= li <= ri < n
- 1 <= ki <= n
- 1 <= vi <= 10^5
思路
有一个长度为 n 的数组，对该数组执行 n 次查询，每次查询从 li 开始，对相距 ki 个位置上的元素执行 nums[idx] = (nums[idx] * vi) % (10^9 + 7) 直到下标 idx > ri。求处理完所有查询后 nums 中所有元素的 按位异或 结果。
可以参考差分数组的思想，采用商分数组。为每一个 ki 创建一个商分数组，需要更新的下标为 l、l + ki、l + 2 * ki、……、l + x * ki。如何确定最后一个下标？使用 r - l 将区间平移至 [0, r - l]，距离右端点最近的距离为 (r - l) % k，因此原区间 [l, r] 的最后一个下标是 r - (r - l) % k。对于商分数组，需要在 l 处乘以 vi，在 r - (r - l) % k + k 处除以 vi。由于涉及到取模，这里需要求 vi 的逆元，根据 费马小定理 等价于计算 vi^(p - 2) % p，可以使用快速幂。
暴力解法的时间复杂度为 O(q * n / k)，其中 q 为查询数组长度，n 为 nums 长度，k 为所有查询中 ki 的均值，商分数组的时间复杂度为 O(q * logM + k * n)，logM 为快速幂求逆元的时间复杂度，M = 10^9 + 7，k * n 的复杂度用于遍历每一个 ki 的商分数组，内部是根据起点分组的 0 ~ ki - 1，步长为 ki。
可以发现暴力解法的复杂度 k 越大越好，而商分数组的解法 k 越小越好。可以设置一个阈值 S，小于 S 使用商分数组，大于等于 S 使用暴力解法，时间复杂度为 O(q * n / S + S * n)。根据基本不等式 a + b >= 2sqrt(ab)，当 a == b 时取等号，因此 q/S + S >= 2 * sqrt(q)，当 S = sqrt(q) 时取得最小值。
代码