Đếm dãy chia hết (Thi thử cụm thi Cửa Lò 2021)
Cho một dãy số nguyên dương, yêu cầu hãy đếm số lượng dãy con liên tiếp có tổng chia hết cho d. Hai dãy con được gọi là khác nhau nếu ít nhất một trong hai điểm đầu hoặc điểm cuối hai dãy con đó trong dãy đã cho là khác nhau. Ví dụ với d = 4, dãy: (2, 1, 2, 1, 4, 1) có 4 dãy con thỏa mãn là (1,2,1), (1,2,1,4), (4), (2,1,4,1). Với d = 2 và dãy: (1, 1, 1, 1) thì có 4 dãy con thỏa mãn.
Dữ liệu vào gồm 2 dòng:
Dòng đầu là 2 số nguyên dương \(d\) và \(N (d ≤ 10^6, N ≤ 10^5)\)
Dòng thứ 2 chứa \(N\) số nguyên dương biểu diễn dãy số, các số trong dãy không quá \(10^9\)
Kết quả:
- Ghi ra 1 số duy nhất là kết quả tìm được.
Ví dụ:
| INPUT | OUTPUT |
|---|---|
| \(4\ 6\) \(2\ 1\ 2\ 1\ 4\ 1\) |
\(4\) |
Ràng buộc:
- Có 1/3 số test tương ứng với 1/3 số điểm có \(N ≤ 10^3\)
- Có 2/3 số test tương ứng với 2/3 số điểm có \(10^3 < N ≤ 10^5\)
Comments
hi
ví dụ: a[l]+a[l+1]+...+a[r]=s[r]-s[l-1] đoạn con a[l]+a[l+1]+...+a[r] chia hết cho d thì chứng tỏ s[r] và s[l-1] đồng dư.
Dùng phép toán đồng dư để giải: s[i]=(S[i-1]+a[i])%d; Khi đó chỉ cần tìm cặp s[i]=s[j] Sau thì chỉ việc lùa bò vào chuồng và giải thôi. Chúc các bạn làm bài tốt