dona10khoa_nhd - Nguyễn Hồ Đăng Khoa - Luong The Vinh high school for the gifted
# 🧠 Bài toán: Đếm số lượng mảng con có tổng chia hết cho `d`
## 💡 Ý tưởng
Bài này là sự kết hợp giữa:
- **Kỹ thuật tiền tố (prefix sum)**: để tính tổng đoạn con nhanh O(1)
- **Kỹ thuật "lùa bò vào chuồng"**: để đếm số lượng đoạn con có tổng chia hết cho `d`
---
## 📘 Phân tích chi tiết
Giả sử mảng ban đầu là `a[1..n]`, ta định nghĩa:
- `pre[i]`: tổng tiền tố từ 1 đến i (tức `a[1] + a[2] + ... + a[i]`)
- Một đoạn `a[l..r]` có tổng chia hết cho `d` khi:
pre[r] - pre[l - 1] ≡ 0 (mod d)
⟺ pre[r] % d == pre[l - 1] % d
=> Vấn đề trở thành: **đếm số lượng cặp (l, r) sao cho `pre[l-1] % d == pre[r] % d`**
---
## 🚜 Kỹ thuật "lùa bò vào chuồng"
Ta dùng một `map<ll, ll>` hoặc `unordered_map<ll, ll>` để lưu số lượng các giá trị `prefix % d` đã xuất hiện.
Đối với mỗi vị trí `r` từ 1 đến `n`, ta thực hiện:
- **Nếu đề yêu cầu `l < r`**, thì ta sẽ:
1. Cộng vào `ans` trước: `ans += cnt[(pre[r] % d + d) % d]`
2. Sau đó mới cập nhật: `cnt[(pre[r - 1] % d + d) % d]++`
- **Nếu đề yêu cầu `l ≤ r`** (trường hợp bài này), thì làm ngược lại:
1. Cập nhật trước: `cnt[(pre[r - 1] % d + d) % d]++`
2. Sau đó mới cộng vào `ans`: `ans += cnt[(pre[r] % d + d) % d]`
> Lưu ý: Vì `a[i]` có thể âm, ta dùng `(x % d + d) % d` để đảm bảo kết quả dương.
---
## ✅ Code mẫu
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll, ll> cnt;
int n, d;
ll ans = 0;
const int N = 1e5 + 5;
ll a[N], pre[N] = {0};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> d;
for(int i = 1; i <= n; i++){
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
for(int r = 1; r <= n; r++){
// Vì l <= r nên ta cập nhật trước rồi mới cộng vào kết quả
cnt[(pre[r - 1] % d + d) % d]++;
ans += cnt[(pre[r] % d + d) % d];
}
cout << ans;
}
dona10khoa_nhd
Created at
0 likes