Đếm số dãy con liên tiếp có tổng chia hết cho k trong Python

Cho mảng nums và số k. Tìm số dãy con liên tiếp (subarray) có tổng chia hết cho k.

Ví dụ: k = 3, nums = [1,2,3,4,1] → kết quả 4. Các dãy con: [3], [1,2], [1,2,3], [2,3,4].

Giải thuật

• Tạo mảng x kích thước k, khởi tạo 0. Đặt x[0] = 1.
• Biến r = 0 (kết quả), s = 0 (tổng tiền tố modulo k).
• Duyệt từng phần tử elem trong nums:
  • s = (s + elem) % k
  • r += x[s]
  • x[s] += 1
• Trả về r.

Ví dụ mã Python

def solve(k, nums):
    x = [0] * k
    x[0] = 1
    r = s = 0
    for elem in nums:
        s = (s + elem) % k
        r += x[s]
        x[s] += 1
    return r

k = 3
nums = [1, 2, 3, 4, 1]
print(solve(k, nums))  # Output: 4

Đầu vào

3, [1,2,3,4,1]

Đầu ra

4