当前没有测试数据。

核心思路

直接暴力枚举所有子数组会超时，我们可以利用前缀和和同余定理来优化。

1. 前缀和定义： 我们定义一个前缀和数组 prefix，其中 prefix[i] 表示数组 nums 中前 i 个元素的和。

   • prefix[0] = 0 (前 0 个元素的和为 0)
   • prefix[1] = nums[0]
   • prefix[2] = nums[0] + nums[1]
   • ...
   • prefix[k] = nums[0] + nums[1] + ... + nums[k-1]

2. 子数组和与前缀和的关系： 数组中从索引 i 到 j 的子数组和（包含 i 和 j）可以表示为： sum(nums[i...j]) = prefix[j+1] - prefix[i]

3. 同余定理的应用： 我们的目标是找到 sum(nums[i...j]) 是 7 的倍数的子数组，即： sum(nums[i...j]) % 7 == 0

   代入前缀和的表达式： (prefix[j+1] - prefix[i]) % 7 == 0

   根据同余定理，这个等式成立的充分必要条件是： prefix[j+1] % 7 == prefix[i] % 7

4. 结论： 如果两个前缀和 prefix[a] 和 prefix[b] (其中 a < b) 对 7 取模的结果相同，那么从索引 a 到 b-1 的子数组和就是 7 的倍数。

5. 计数方法：

   • 我们可以用一个数组 count 来记录每种余数出现的次数。count[r] 表示当前前缀和中余数为 r 的数量。
   • 初始时，prefix[0] = 0，它的余数是 0，所以 count[0] = 1。
   • 我们遍历数组，计算当前前缀和 current_sum。
   • 计算 current_sum % 7 得到余数 rem。
   • 如果 count[rem] 的值大于 0，说明之前已经出现过 count[rem] 个前缀和与当前前缀和有相同的余数。这意味着我们找到了 count[rem] 个符合条件的子数组。我们将 count[rem] 的值加到最终答案 result 中。
   • 然后，我们将当前余数 rem 在 count 数组中的计数加 1。

C++ 代码实现

#include <iostream>
#include <vector>

// 为了效率，使用 C 风格的输入输出会更快
#include <cstdio>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    // count[0] 到 count[6] 分别记录余数 0 到 6 的出现次数
    vector<long long> count(7, 0);
    // 初始化，前缀和为 0 时，余数 0 已经出现了一次
    count[0] = 1;

    long long current_sum = 0;
    long long result = 0;

    for (int i = 0; i < n; ++i) {
        int num;
        cin>>num;
        
        current_sum += num;
        
        // 计算当前前缀和的余数
        // C++ 中负数取模可能为负，+7 再 %7 确保结果为正
        int rem = (current_sum % 7 + 7) % 7;
        
        // 如果这个余数之前出现过，那么之前出现的次数就是能组成的子数组数量
        result += count[rem];
        
        // 将当前余数的计数加 1
        count[rem]++;
    }

    cout << result << endl;

    return 0;
}

代码解析

• vector<long long> count(7, 0);：我们使用一个大小为 7 的 vector 来代替哈希表，因为任何整数对 7 取模，余数只可能是 0, 1, 2, 3, 4, 5, 6 这七种情况。
• count[0] = 1;：这是整个算法的关键初始化步骤。它代表了前缀和为 0 的情况，为我们寻找从数组开头开始的子数组（如 [7], [7, 14]）提供了依据。
• current_sum % 7：计算当前前缀和对 7 的余数。
• result += count[rem];：这是算法的核心。如果 count[rem] 的值是 k，就说明有 k 个之前的前缀和与当前前缀和余数相同，因此形成了 k 个新的符合条件的子数组。
• count[rem]++;：更新 count 数组，将当前余数的出现次数加一，以便后续元素进行配对。

这种方法只需要遍历一次数组，并且每次遍历的操作都是常数时间 O(1)，因此整个算法的时间复杂度是 O(n)，空间复杂度是 O(1)（因为 count 数组的大小是固定的 7），是解决此类问题的最优方案。