Hướng dẫn giải của CAU4
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
Tích ~a_i \cdot a_j~ có chữ số tận cùng là 0 khi và chỉ khi nó chia hết cho 2 và cho 5. Mỗi số thuộc một trong bốn loại theo tính chia hết cho 2 và cho 5; các cặp được đếm theo loại.
Sub 1: Vét cạn cặp — ~O(n^2)~, dùng khi ~n \le 10^4~
Duyệt mọi cặp ~i < j~ và kiểm tra ~(a_i \bmod 10) \cdot (a_j \bmod 10) \bmod 10 = 0~.
Nếu chỉ nộp sub này: đúng 12/16 test.
Sub 2: Đếm theo loại — ~O(n)~
Gán mỗi số một mặt nạ 2 bit (bit 0: chia hết cho 2, bit 1: chia hết cho 5). Cặp hợp lệ khi hợp hai mặt nạ bằng 3. Đếm số lượng từng mặt nạ rồi tính tổ hợp.
Nếu chỉ nộp sub này: đúng 16/16 test.
Chương trình hoàn chỉnh
Dữ liệu ~n \le 10^4~ dùng sub 1, còn lại dùng sub 2. Kết quả lấy dư ~10^9 + 7~.
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;
int n;
vector<long long> a;
// Tich a[i]*a[j] co chu so tan cung la 0 <=> tich chia het cho 10 <=> tich chia het cho 2 va cho 5.
// Sub 1: vet can O(n^2) tren cac cap i < j, chi can chu so tan cung cua moi so. Dung khi n <= 10^4.
void sub1() {
long long cnt = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if ((a[i] % 10) * (a[j] % 10) % 10 == 0) cnt++;
cout << cnt % MOD << "\n";
}
// Sub 2: moi so co mat na 1 trong 4 loai theo (chia het 2?, chia het 5?) - bit 0 va bit 1.
// Cap (i, j) hop le khi hop bit cua hai so bang 3 (tuc la co du 2 va 5).
// Dem so luong moi loai roi tinh to hop. O(n).
void sub2() {
long long cnt[4] = {0, 0, 0, 0};
for (int i = 0; i < n; i++) {
int m = 0;
if (a[i] % 2 == 0) m |= 1;
if (a[i] % 5 == 0) m |= 2;
cnt[m]++;
}
long long total = 0;
for (int m1 = 0; m1 < 4; m1++)
for (int m2 = m1; m2 < 4; m2++) {
if (m1 == m2) {
if ((m1 | m2) == 3) total += cnt[m1] * (cnt[m1] - 1) / 2;
} else if ((m1 | m2) == 3) {
total += cnt[m1] * cnt[m2];
}
}
cout << total % MOD << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 10000) sub1();
else sub2();
return 0;
}
Bình luận