第 463 场周赛（GPT-3，Me-1）

不得不惊叹Deepseek 和 Kimi的算法能力了！

题目重述

给你一个整数数组 nums 和一个整数 k。你可以多次选择连续子数组 nums，其元素和可以被 k 整除，并将其删除；每次删除后，剩余元素会填补空缺。返回在执行任意次数此类删除操作后，nums 的最小可能和。

示例

假设输入：

nums = [1, 2, 3, 4, 5], k = 3

可能的删除操作：

• 删除子数组 [3]（和为3，可被3整除），剩余 [1, 2, 4, 5]。
• 删除子数组 [1, 2]（和为3，可被3整除），剩余 [3, 4, 5]，然后可以删除 [3]，剩余 [4, 5]。
• 删除子数组 [2, 1]（注意：子数组必须连续，这里 [2, 1] 不是连续的，不可行）。
• 删除子数组 [4, 5]（和为9，可被3整除），剩余 [1, 2, 3]，然后可以删除 [3]，剩余 [1, 2]。

看起来最小的和可能是 1 + 2 = 3。

解题思路

关键观察

要最小化剩余数组的和，我们需要尽可能多地删除和为 k 的倍数的连续子数组。这类似于从数组中删除一些元素，使得剩余元素的和最小。

动态规划

我们可以使用动态规划来解决这个问题。定义 dp[i] 为前 i 个元素（即 nums[0..i-1]）的最小剩余和。

状态转移

对于每个 i，我们有两种选择：

1. 不删除任何以 i 结尾的子数组：dp[i] = dp[i-1] + nums[i-1]。
2. 删除某个以 i 结尾的子数组 nums[j..i-1]，其中 sum(nums[j..i-1]) % k == 0。此时 dp[i] = dp[j]。

因此，状态转移方程为：

dp[i] = min(dp[i-1] + nums[i-1], min_{j < i and sum(nums[j..i-1]) % k == 0} dp[j])

优化求和

直接计算 sum(nums[j..i-1]) 的时间复杂度是 O(n^2)，对于较大的 n 会超时。我们可以用前缀和来优化：

• 定义前缀和数组 prefix，其中 prefix[i] = sum(nums[0..i-1])。
• 则 sum(nums[j..i-1]) = prefix[i] - prefix[j]。
• 条件 sum(nums[j..i-1]) % k == 0 等价于 (prefix[i] - prefix[j]) % k == 0，即 prefix[i] % k == prefix[j] % k。

因此，我们可以用哈希表记录每个余数 r 对应的最小 dp[j]，其中 prefix[j] % k == r。

初始化

• dp[0] = 0（前0个元素的和为0）。
• prefix[0] = 0。

算法步骤

1. 初始化 dp 数组，dp[0] = 0。
2. 计算前缀和 prefix[i]。
3. 使用哈希表 mod_map 记录余数 r 对应的最小 dp[j]。
   • 初始时 mod_map[0] = 0（对应 prefix[0] = 0）。
4. 对于每个 i 从 1 到 n：
   • 计算当前前缀和 prefix[i] 和余数 r = prefix[i] % k。
   • 如果 r 在 mod_map 中存在，则 dp[i] = min(dp[i-1] + nums[i-1], mod_map[r])。
   • 否则 dp[i] = dp[i-1] + nums[i-1]。
   • 更新 mod_map[r] = min(mod_map.get(r, inf), dp[i])（确保存储的是最小的 dp[j]）。

代码实现

from typing import Listclass Solution:def minSumAfterDeletion(self, nums: List[int], k: int) -> int:n = len(nums)dp = [0] * (n + 1)prefix = [0] * (n + 1)mod_map = {0: 0}  # 余数 -> 最小的dp[j]for i in range(1, n + 1):prefix[i] = prefix[i - 1] + nums[i - 1]r = prefix[i] % kif r in mod_map:dp[i] = min(dp[i - 1] + nums[i - 1], mod_map[r])else:dp[i] = dp[i - 1] + nums[i - 1]# 更新mod_map[r]为dp[i]和mod_map[r]的较小值if r in mod_map:mod_map[r] = min(mod_map[r], dp[i])else:mod_map[r] = dp[i]return dp[n]

示例验证

以 nums = [1, 2, 3, 4, 5], k = 3 为例：

初始化：

• dp = [0, 0, 0, 0, 0, 0]
• prefix = [0, 0, 0, 0, 0, 0]
• mod_map = {0: 0}

计算 i = 1：

• nums[0] = 1
• prefix[1] = 1
• r = 1 % 3 = 1
• mod_map 中没有 1，所以 dp[1] = dp[0] + 1 = 1
• mod_map = {0: 0, 1: 1}

计算 i = 2：

• nums[1] = 2
• prefix[2] = 1 + 2 = 3
• r = 3 % 3 = 0
• mod_map 中有 0，所以 dp[2] = min(dp[1] + 2, mod_map[0]) = min(1 + 2, 0) = 0
• mod_map[0] 更新为 min(0, 0) = 0，mod_map = {0: 0, 1: 1}

计算 i = 3：

• nums[2] = 3
• prefix[3] = 3 + 3 = 6
• r = 6 % 3 = 0
• mod_map 中有 0，所以 dp[3] = min(dp[2] + 3, mod_map[0]) = min(0 + 3, 0) = 0
• mod_map[0] 更新为 min(0, 0) = 0，mod_map = {0: 0, 1: 1}

计算 i = 4：

• nums[3] = 4
• prefix[4] = 6 + 4 = 10
• r = 10 % 3 = 1
• mod_map 中有 1，所以 dp[4] = min(dp[3] + 4, mod_map[1]) = min(0 + 4, 1) = 1
• mod_map[1] 更新为 min(1, 1) = 1，mod_map = {0: 0, 1: 1}

计算 i = 5：

• nums[4] = 5
• prefix[5] = 10 + 5 = 15
• r = 15 % 3 = 0
• mod_map 中有 0，所以 dp[5] = min(dp[4] + 5, mod_map[0]) = min(1 + 5, 0) = 0
• mod_map[0] 更新为 min(0, 0) = 0，mod_map = {0: 0, 1: 1}

最终 dp[5] = 0，表示可以删除所有元素，和为 0。这与直觉一致：

• 删除 [1, 2]（和为3），剩余 [3, 4, 5]。
• 删除 [3]（和为3），剩余 [4, 5]。
• 删除 [4, 5]（和为9），剩余 []。

然而，题目描述似乎暗示“删除”是选择连续子数组并将其移除，剩余元素会填补空缺，但“最小可能和”是剩余元素的和。因此，0 是正确的。

修正理解

可能的误解：题目描述“删除连续子数组”后，剩余元素填补空缺，但“最小可能和”是剩余元素的和。因此，可以删除所有可能的子数组，使得剩余和最小。

因此，动态规划的方法是合理的。
2.
为了解决这个问题，我们需要高效地处理多个区间乘法查询，并在所有查询完成后计算数组所有元素的按位异或结果。由于直接模拟每个查询的更新操作会导致超时（时间复杂度为O(n*q)），我们采用根号分治策略，将查询分为大步长（k > sqrt(n)）和小步长（k <= sqrt(n)）两类，分别处理，以优化时间复杂度。

方法思路

1. 问题分析：

   • 给定数组nums和查询数组queries，每个查询指定一个区间[l_i, r_i]、步长k_i和乘数v_i。
   • 对于每个查询，从l_i开始，以步长k_i遍历区间，将每个位置的元素乘以v_i并取模。
   • 最终返回数组所有元素的异或结果。

2. 根号分治：

   • 大步长查询（k > sqrt(n)）：每个查询修改的位置数不超过sqrt(n)，直接暴力更新。
   • 小步长查询（k <= sqrt(n)）：按步长k分组，对每个k的同余类（模k余数相同的序列）使用差分数组处理区间乘法。

3. 处理零值查询：

   • 若v_i = 0，则标记覆盖的位置为零，最终这些位置的结果为0。
   • 非零查询通过差分数组记录乘法因子，最后计算前缀积。

4. 最终计算：

   • 对每个位置，若被零查询覆盖则结果为0；否则，结果为初始值、小步长乘法因子和大步长乘法因子的乘积取模。
   • 所有位置的结果进行异或运算。

解决代码

import math
from collections import defaultdictMOD = 10**9 + 7class Solution:def solve(self, nums, queries):n = len(nums)if n == 0:return 0B = int(math.isqrt(n)) + 1zero = [False] * nsmall_mul = [1] * nbig_mul = [1] * nbig_queries = []small_queries = []for query in queries:l, r, k, v = queryif k > B:big_queries.append((l, r, k, v))else:small_queries.append((l, r, k, v))for l, r, k, v in big_queries:if v == 0:idx = lwhile idx <= r:zero[idx] = Trueidx += kelse:idx = lwhile idx <= r:big_mul[idx] = (big_mul[idx] * v) % MODidx += kqueries_by_k = defaultdict(list)for l, r, k, v in small_queries:queries_by_k[k].append((l, r, v))for k, q_list in queries_by_k.items():diff_mul_list = []diff_cover_list = []len_list = []for r in range(k):if r >= n:len_r = 0else:len_r = (n - 1 - r) // k + 1len_list.append(len_r)diff_mul_list.append([1] * (len_r + 1))diff_cover_list.append([0] * (len_r + 1))for l, r, v in q_list:r0 = l % kif r0 >= n:continuestart_idx = (l - r0) // klen_r = len_list[r0]if start_idx >= len_r:continueend_idx = (r - r0) // kif end_idx >= len_r:end_idx = len_r - 1else:end_idx = min(end_idx, len_r - 1)if v != 0:diff_mul = diff_mul_list[r0]diff_mul[start_idx] = (diff_mul[start_idx] * v) % MODif end_idx + 1 < len_r + 1:inv_v = pow(v, MOD - 2, MOD)diff_mul[end_idx + 1] = (diff_mul[end_idx + 1] * inv_v) % MODelse:diff_cover = diff_cover_list[r0]diff_cover[start_idx] += 1if end_idx + 1 < len_r + 1:diff_cover[end_idx + 1] -= 1for r in range(k):len_r = len_list[r]if len_r == 0:continuediff_mul = diff_mul_list[r]prod = [1] * len_rcur = 1for i in range(len_r):cur = (cur * diff_mul[i]) % MODprod[i] = curdiff_cover = diff_cover_list[r]cover_sum = 0cover_arr = [0] * len_rfor i in range(len_r):cover_sum += diff_cover[i]cover_arr[i] = cover_sumfor i in range(len_r):pos = r + i * kif pos >= n:breakif cover_arr[i] > 0:zero[pos] = Trueelse:small_mul[pos] = (small_mul[pos] * prod[i]) % MODres = 0for i in range(n):if zero[i]:total = 0else:total = nums[i] * small_mul[i] % MODtotal = total * big_mul[i] % MODres ^= totalreturn res

方法解释

1. 初始化：

   • 设置阈值B = sqrt(n) + 1，用于区分大步长和小步长查询。
   • 初始化zero数组标记被零查询覆盖的位置，small_mul和big_mul数组分别记录小步长和大步长查询的乘法因子。

2. 查询分类：

   • 将查询按步长k分为大步长（k > B）和小步长（k <= B）两类。

3. 处理大步长查询：

   • 对每个大步长查询，若v_i = 0，则遍历所有覆盖位置并标记zero数组；否则，更新big_mul数组。

4. 处理小步长查询：

   • 按步长k分组，对每组中的每个同余类（模k余数相同的序列）初始化差分数组。
   • 对每个查询，若v_i = 0，更新差分覆盖数组；否则，更新差分乘法数组（使用乘法逆元处理区间结束）。
   • 计算前缀积和前缀和，更新small_mul和zero数组。

5. 结果计算：

   • 遍历每个位置，若被零查询覆盖则结果为0；否则，计算初始值与乘法因子的乘积取模。
   • 所有位置的结果进行异或运算，返回最终结果。

该方法的时间复杂度为O(n * sqrt(n))，空间复杂度为O(n)，能高效处理大规模数据。

小步长查询处理算法详解（k ≤ √n）

该算法利用分组+同余类+差分数组的思想高效处理区间乘法查询，核心是通过数学变换将区间操作转化为单点操作，最后通过前缀计算得到最终结果。

算法步骤：

1. 分组处理：

   • 将步长 k ≤ √n 的查询按 k 值分组
   • 对每个 k 值独立处理其所有查询

2. 同余类分解：

   • 对每个 k 值，将数组分为 k 个同余类（余数 0 到 k-1）
   • 例如 k=3 时：
     • 余数0类：下标 0, 3, 6, 9, …
     • 余数1类：下标 1, 4, 7, 10, …
     • 余数2类：下标 2, 5, 8, 11, …

3. 差分数组构建（每类两个差分数组）：

   • diff_mul：乘法操作的差分数组
     • 初始化为全1（乘法单位元）
     • 区间 [L,R] 乘以 v → L 位置乘 v，R+1 位置乘 v⁻¹（模逆元）
   • diff_cover：零覆盖标记的差分数组
     • 初始化为全0
     • 区间 [L,R] 置零 → L 位置+1，R+1 位置-1

4. 查询转换（原下标→同余类下标）：

   • 对于查询 [l, r, k, v]：
     • 余数 r₀ = l % k
     • 在余数 r₀ 类中的起始位置：start_idx = (l - r₀) // k
     • 结束位置：end_idx = (r - r₀) // k（需边界检查）

5. 前缀计算（处理每个同余类）：

   • 计算 diff_mul 的前缀积 → 得到每个位置的累积乘积
   • 计算 diff_cover 的前缀和 → 标记被零覆盖的位置

6. 更新原数组：

   • 遍历每个位置：
     • 若被零覆盖 → 标记 zero[i] = True
     • 否则 → 将累积乘积乘到 small_mul[i]

关键技巧：

1. 乘法逆元撤销操作：

   inv_v = pow(v, MOD-2, MOD)  # 费马小定理求逆元
   

   • 在 R+1 位置乘以逆元，确保只在 [L,R] 区间生效

2. 零查询特殊处理：

   • 使用独立的覆盖标记数组
   • 优先级高于乘法操作

3. 空间优化：

   • 不实际创建子序列数组
   • 通过索引映射直接操作原数组

时间复杂度分析：

• 分组：O(q)
• 每类查询处理：O(查询数量)
• 每类前缀计算：O(n/k)
• 总复杂度：O(k × n/k) = O(n) 每 k 值 → O(n√n)

示例说明：

假设 n=6，k=2，查询：[[1, 5, 2, 3]]

1. 同余类分解：

   • 余数0类：下标 0, 2, 4 → 子序列 [a0, a2, a4]
   • 余数1类：下标 1, 3, 5 → 子序列 [a1, a3, a5]

2. 查询转换：

   • l=1, r=5 → 余数 r₀=1
   • 在余数1类：start_idx=(1-1)//2=0, end_idx=(5-1)//2=2

3. 差分数组操作：

   • diff_mul[0] *= 3
   • diff_mul[3] *= 3⁻¹（实际忽略，因超出范围）

4. 前缀计算：

   • 前缀积：[3, 3, 3]（子序列所有位置乘以3）

5. 更新原数组：

   • a1, a3, a5 的 small_mul 乘以3

优势：

• 将区间操作转化为O(1)的差分操作
• 通过分组控制总复杂度在O(n√n)
• 完美处理零值查询的特殊情况
• 利用模逆元实现乘法操作的精确撤销

这种设计巧妙结合了数论（逆元）、分组处理（根号分治）和差分数组技巧，是处理此类区间更新问题的经典范式。
6.

```cpp
class Solution {
public:long long maxProfit(vector<int>& prices, vector<int>& strategy, int k) {int n = prices.size();vector<long long> nums1(n,0);vector<long long> nums2(n,0);nums1[0] = prices[0];for (int i = 1;i < n;i ++) {nums1[i] = nums1[i-1]+prices[i];}long long nums_mon = 0;nums2[0] = prices[0] * strategy[0];nums_mon = nums2[0];for (int i = 1;i < n;i ++) {nums2[i] = nums2[i-1]+prices[i]*strategy[i];nums_mon += prices[i]*strategy[i];}long long ans = nums_mon;for (int i = k/2;i + k/2 -1 < n;i ++) {long long tmp = (nums1[i+k/2-1]-nums1[i-1]) + (nums2[n-1]-nums2[i+k/2-1]) ;if (i >= k/2+1)tmp += nums2[i-k/2-1];ans = max(ans,tmp);}return ans;}
};