To solve this problem, we need to find the number of subarrays in a given sequence of integers where the sum of elements is divisible by a given integer ( k ). The solution leverages prefix sums and modular arithmetic to efficiently count these subarrays.
Approach
- Prefix Sum & Modulo: Compute the prefix sum of the array and take its modulo ( k ). For a subarray from index ( j+1 ) to ( i ), the sum is divisible by ( k ) if the prefix sum at ( i+1 ) modulo ( k ) equals the prefix sum at ( j ) modulo ( k ).
- Frequency Map: Use a frequency map to count occurrences of each modulo value. For each current modulo value, add the frequency of this value to the result (since all previous occurrences are valid starting points for the subarray).
- Handle Negative Modulo: Ensure the modulo value is non-negative by adjusting it with ( (mod + k) \% k ).
Solution Code
from collections import defaultdict
n = int(input())
arr = list(map(int, input().split()))
k = int(input())
freq = defaultdict(int)
freq[0] = 1 # Prefix sum 0 (before the array starts)
current_sum = 0
result = 0
for num in arr:
current_sum += num
mod = current_sum % k
mod = (mod + k) % k # Ensure non-negative remainder
result += freq[mod]
freq[mod] += 1
print(result)
Explanation
- Initialization: We start with a frequency map initialized to
{0:1}because the prefix sum before the array starts is 0, which is divisible by any ( k ). - Iterate Through Array: For each element, update the current sum and compute its modulo ( k ). Adjust the modulo to be non-negative.
- Count Valid Subarrays: For each modulo value, add the number of times it has occurred before (from the frequency map) to the result. This count represents the number of valid subarrays ending at the current position.
- Update Frequency: Increment the frequency of the current modulo value to include it in future calculations.
This approach efficiently counts the valid subarrays in ( O(n) ) time complexity, where ( n ) is the length of the array, making it suitable for large input sizes. The space complexity is ( O(k) ) due to the frequency map, which is optimal for this problem.
Example: For the array [4,5,0,-2,-3,1] and ( k=5 ), the result is 7, which is the number of subarrays whose sum is divisible by 5. This is correctly computed using the above method.
Another example: For the array [0,0,0] and ( k=5 ), the result is 6, as all subarrays (6 in total) have a sum of 0, which is divisible by any ( k ).
This solution handles all edge cases, including negative numbers and ( k=1 ), correctly. It is both efficient and easy to understand.


作者声明:本文包含人工智能生成内容。