Hướng dẫn giải của Đoạn con
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Yêu cầu: đếm số đoạn con liên tiếp có tổng chia hết cho ~k~.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 1000~
Tính tổng tiền tố ~P~, rồi thử mọi cặp ~(i, j)~ với ~P_j - P_i~ chia hết cho ~k~.
Nếu chỉ nộp sub này: đúng 4/10 test.
Sub 2: Đếm theo số dư — ~O(n + k)~
Đoạn ~(i+1..j)~ chia hết cho ~k~ khi và chỉ khi ~P_i~ và ~P_j~ có cùng số dư mod ~k~. Đếm số lần xuất hiện mỗi số dư và cộng dồn. Số dư âm được đưa về khoảng ~[0, k)~.
Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
Với ~n \le 1000~ gọi sub 1, còn lại gọi sub 2. Sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n;
long long k;
vector<long long> a; // a[1..n]
// Sub 1: vét cạn mọi đoạn O(n^2) — dùng khi n <= 1000
void sub1() {
vector<long long> P(n + 1, 0);
for (int i = 1; i <= n; i++) P[i] = P[i - 1] + a[i];
long long ans = 0;
// đoạn (i+1..j) có tổng P[j]-P[i]
for (int i = 0; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if ((P[j] - P[i]) % k == 0) ans++;
cout << ans << "\n";
}
// Sub 2: đếm theo số dư của tổng tiền tố O(n + k) — lời giải đầy đủ
// Đoạn (i+1..j) chia hết cho k <=> P[i] và P[j] có cùng số dư mod k.
void sub2() {
vector<long long> cnt(k, 0);
long long r = 0, ans = 0;
cnt[0] = 1; // tiền tố P[0] = 0
for (int i = 1; i <= n; i++) {
r = ((r + a[i]) % k + k) % k; // số dư của P[i]
ans += cnt[r];
cnt[r]++;
}
cout << ans << "\n";
}
int main() {
freopen("CAU3.INP", "r", stdin);
freopen("CAU3.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
a.assign(n + 1, 0);
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận