Chuyên đề cơ bản 4: Đếm và tìm quy luật trong C++ và Python: quy tắc cộng, quy tắc nhân, đếm bằng đóng góp, lập bảng đoán công thức, chu kỳ
Lời mở đầu
Trong đề HSG có một nhóm bài rất đặc biệt: đề ngắn, dữ liệu vào chỉ một hai con số, nhưng $n$ lên tới $10^9$ hay $10^{18}$. Không có cấu trúc dữ liệu nào cứu được, chỉ có đếm khéo và tìm quy luật. Chuyên đề cuối của nhóm Thuật toán cơ bản gom lại những “mẹo nhà nghề” mà các bạn đội tuyển hay dùng: đếm phần bù, đếm bằng đóng góp, lập bảng vét cạn để đoán công thức, phát hiện chu kỳ và các công thức tổng quen thuộc.
Em sẽ dùng lại vòng lặp ở bài 4, ước lượng thời gian và bẫy tràn số ở bài 9, ƯCLN và chia lấy dư ở bài 12. Bao hàm – loại trừ đã có ở chuyên đề 6, cách viết vét cạn gọn và nhanh ở chuyên đề 10. Phần tổ hợp $C(n, k)$ và chia trong modulo để dành cho bài 26, ở đây mình chỉ dùng phép đếm “bằng tay”.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Quy tắc cộng, quy tắc nhân và đếm phần bù
Hai quy tắc dưới đây nghe rất “toán lớp 11”, nhưng hiểu chắc chúng thì em đếm được gần như mọi thứ trong đề HSG cơ bản:
- Quy tắc cộng: công việc làm theo phương án A hoặc phương án B; A có $a$ cách, B có $b$ cách, và không cách nào thuộc cả hai. Khi đó có $a + b$ cách.
- Quy tắc nhân: công việc gồm bước 1 rồi bước 2; bước 1 có $a$ cách, và ứng với mỗi cách đó bước 2 đều có $b$ cách. Khi đó có $a \cdot b$ cách.
Ví dụ: biển số gồm 2 chữ cái in hoa rồi 3 chữ số có $26 \cdot 26 \cdot 10 \cdot 10 \cdot 10 = 676\,000$ biển. Số có 3 chữ số đôi một khác nhau: chữ số hàng trăm có 9 cách (khác 0), hàng chục còn 9 cách (khác hàng trăm, được là 0), hàng đơn vị còn 8 cách, tổng $9 \cdot 9 \cdot 8 = 648$ số. Để ý: ở bước sau các chữ số được chọn thay đổi theo bước trước, nhưng số lượng cách thì không đổi, nên vẫn nhân được.
Đếm phần bù. Hỏi: có bao nhiêu số có $n$ chữ số chứa ít nhất một chữ số 7? Đếm trực tiếp phải chia trường hợp “có đúng một số 7 ở vị trí nào”, “có hai số 7”… rất rối. Đếm ngược lại dễ hơn nhiều: số có $n$ chữ số không có chữ số 7 nào thì chữ số đầu có 8 cách (bỏ 0 và 7), mỗi chữ số còn lại có 9 cách, tức $8 \cdot 9^{n-1}$ số. Lấy tất cả trừ đi:
$$\text{có ít nhất một số 7} = \underbrace{9 \cdot 10^{n-1}}_{\text{tất cả}} - \underbrace{8 \cdot 9^{n-1}}_{\text{không có số 7}}$$
| n | Tất cả | Không có số 7 | Có ít nhất một số 7 | Vét cạn kiểm tra |
|---|---|---|---|---|
| 1 | 9 | 8 | 1 | 1 (chỉ số 7) |
| 2 | 90 | 72 | 18 | 18 |
| 3 | 900 | 648 | 252 | 252 |
| 4 | 9000 | 5832 | 3168 | 3168 |
Bảng 1. Đếm phần bù số có $n$ chữ số chứa chữ số 7. Cột cuối là kết quả của vòng for duyệt từng số, khớp hoàn toàn.
Cùng ý tưởng cho một bài rất hay gặp: cho dãy $n$ số, đếm số cặp $(i, j)$ với $i < j$ và $a_i \ne a_j$. Cặp “khác nhau” thì khó đếm, cặp “bằng nhau” lại rất dễ: nếu giá trị $v$ xuất hiện $c_v$ lần thì có $\frac{c_v(c_v - 1)}{2}$ cặp bằng $v$. Đáp án là $\frac{n(n-1)}{2} - \sum_v \frac{c_v(c_v-1)}{2}$. Với dãy 1 2 1 3 1: tất cả 10 cặp, số 1 xuất hiện 3 lần cho 3 cặp bằng nhau, đáp án 7. Đếm số lần xuất hiện bằng map như ở chuyên đề cơ bản 1:
Xem code C++ / Python: đếm cặp khác nhau bằng phần bù (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
map<long long, long long> cnt;
for(int i = 0; i < n; i++){
long long x;
cin >> x;
cnt[x]++;
}
long long total = 1LL * n * (n - 1) / 2; // tất cả các cặp i < j
long long same = 0; // các cặp KHÔNG thỏa: hai số bằng nhau
for(auto &p : cnt) same += p.second * (p.second - 1) / 2;
cout << total - same; // phần bù
return 0;
}import sys
from collections import Counter
data = sys.stdin.buffer.read().split()
n = int(data[0])
cnt = Counter(data[1:n + 1])
total = n * (n - 1) // 2 # tất cả các cặp i < j
same = sum(c * (c - 1) // 2 for c in cnt.values()) # các cặp KHÔNG thỏa: hai số bằng nhau
print(total - same) # phần bù2. Nhân khi số cách của bước sau phụ thuộc bước trước. Ví dụ đếm số có 3 chữ số tăng dần: chọn chữ số đầu là 1 thì chữ số thứ hai có 8 cách, chọn 8 thì chỉ còn 1 cách. Lúc đó phải chia trường hợp (quy tắc cộng) hoặc dùng tổ hợp ở bài 26.
Phần 2Đếm bằng đóng góp: đổi vai “đối tượng” và “phần tử”
Bài toán: cho dãy $a_1, a_2, \ldots, a_n$, tính tổng các tổng của mọi đoạn con liên tiếp. Cách thẳng thắn là duyệt mọi đoạn $[l, r]$ rồi cộng tổng của nó (dùng cộng dồn ở bài 13 thì $O(n^2)$). Với $n = 2 \cdot 10^5$ có tới $2 \cdot 10^{10}$ đoạn, quá chậm.
Kỹ thuật đóng góp (contribution) đổi câu hỏi: thay vì “mỗi đoạn có tổng bao nhiêu”, ta hỏi “mỗi phần tử $a_i$ được cộng vào bao nhiêu đoạn?”. Đoạn $[l, r]$ chứa vị trí $i$ khi và chỉ khi $l \le i \le r$: đầu trái $l$ chọn trong $1..i$ ($i$ cách), đầu phải $r$ chọn trong $i..n$ ($n - i + 1$ cách), hai lựa chọn độc lập. Theo quy tắc nhân:
$$\text{số đoạn chứa } a_i = i \cdot (n - i + 1) \qquad\Rightarrow\qquad \sum_{\text{mọi đoạn}} \text{tổng đoạn} = \sum_{i=1}^{n} a_i \cdot i \cdot (n - i + 1)$$
Hình 1. Dãy 5 phần tử: vị trí 3 nằm trong đúng $3 \cdot 3 = 9$ đoạn con. Màu của thanh cho biết đầu trái $l$, độ dài thanh cho biết đầu phải $r$.
Em bấm Tiếp để xem từng phần tử “đếm” số đoạn chứa nó, rồi thử dãy của riêng em. Bước cuối mô phỏng tự kiểm tra lại bằng vét cạn:
| i | $a_i$ | cách chọn l | cách chọn r | số đoạn chứa $a_i$ | đóng góp |
|---|---|---|---|---|---|
| 1 | 3 | 1 | 4 | 4 | 12 |
| 2 | −1 | 2 | 3 | 6 | −6 |
| 3 | 4 | 3 | 2 | 6 | 24 |
| 4 | 2 | 4 | 1 | 4 | 8 |
| tổng | 38 |
Bảng 2. Dãy 3, −1, 4, 2 có 10 đoạn con, tổng các tổng là 38. Để ý số đoạn chứa $a_i$ đối xứng: phần tử ở giữa nằm trong nhiều đoạn nhất.
Xem code C++ / Python: tổng các tổng của mọi đoạn con bằng đóng góp (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
long long total = 0;
for(long long i = 1; i <= n; i++){
long long x;
cin >> x;
total += x * i * (n - i + 1); // a[i] nằm trong i * (n - i + 1) đoạn
}
cout << total;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
total = 0
for i in range(1, n + 1):
total += int(data[i]) * i * (n - i + 1) # a[i] nằm trong i * (n - i + 1) đoạn
print(total)Chạy tay từng dòng để thấy chương trình không hề “nhìn” thấy đoạn con nào. Code dưới đánh số từ 0 nên công thức thành $(i + 1)(n - i)$:
Tổng chênh lệch của mọi cặp. Tính $\sum_{i < j} |a_i - a_j|$. Dấu giá trị tuyệt đối làm khó, nhưng nếu dãy đã sắp xếp tăng thì với $i < j$ luôn có $|a_i - a_j| = a_j - a_i$. Xét phần tử ở vị trí $i$ (đánh số từ 0) sau khi sắp xếp: nó là số lớn hơn trong $i$ cặp với các số đứng trước (được cộng $i$ lần) và là số nhỏ hơn trong $n - 1 - i$ cặp với các số đứng sau (bị trừ $n - 1 - i$ lần). Vậy:
$$\sum_{i<j} |a_i - a_j| = \sum_{i=0}^{n-1} a_i \cdot \big(i - (n - 1 - i)\big) = \sum_{i=0}^{n-1} a_i \cdot (2i - n + 1) \quad (\text{dãy đã sắp xếp})$$
Ví dụ dãy 3 1 4 2, sắp xếp thành 1 2 3 4: $1 \cdot (-3) + 2 \cdot (-1) + 3 \cdot 1 + 4 \cdot 3 = 10$, đúng bằng $1 + 2 + 3 + 1 + 2 + 1$ của 6 cặp. Thời gian $O(n \log n)$ cho bước sắp xếp.
Xem code C++ / Python: tổng chênh lệch mọi cặp sau khi sắp xếp (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for(auto &x : a) cin >> x;
sort(a.begin(), a.end());
long long total = 0;
for(long long i = 0; i < n; i++)
total += a[i] * (2 * i - n + 1); // lớn hơn i số đứng trước, nhỏ hơn n-1-i số đứng sau
cout << total;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = sorted(map(int, data[1:n + 1]))
total = 0
for i in range(n):
total += a[i] * (2 * i - n + 1) # lớn hơn i số đứng trước, nhỏ hơn n-1-i số đứng sau
print(total)Bước 2. Đổi thứ tự lấy tổng: $\sum_{\text{đối tượng}} \sum_{\text{phần tử trong đó}} = \sum_{\text{phần tử}} (\text{giá trị}) \times (\text{số đối tượng chứa nó})$.
Bước 3. Đếm “số đối tượng chứa phần tử” bằng quy tắc nhân. Các kết quả hay dùng: số đoạn chứa vị trí $i$ là $i(n - i + 1)$; số tập con chứa một phần tử cố định là $2^{n-1}$; số cặp mà phần tử thứ $i$ (sau sắp xếp) là số lớn hơn là $i$.
int. Phải tính bằng long long và viết 1LL * i * (n - i + 1) (hoặc khai báo i là long long), nếu không phép nhân int * int tràn trước khi được gán vào biến long long. Trước khi nộp, em nhân thử giá trị lớn nhất của từng thừa số xem đáp án có vượt $9 \cdot 10^{18}$ không.Phần 3Lập bảng nhỏ bằng vét cạn để tìm quy luật
Nhiều bài “tìm quy luật” có đáp án là một công thức đơn giản, nhưng nhìn đề thì không thể đoán ra ngay. Cách làm của dân thi đấu là để máy tính làm phần khó:
2. In bảng: in $f(1), f(2), \ldots, f(20)$, có thể thêm cột hiệu liên tiếp, tỉ số, $n \bmod 2$, $n \bmod 4$…
3. Đoán: nhìn bảng, đối chiếu với các dạng quen thuộc (đa thức, lũy thừa, chu kỳ, Fibonacci…).
4. Kiểm chứng: cài công thức, so với vét cạn cho mọi $n$ tới vài trăm. Chỉ nộp khi khớp hết.
Ví dụ. Trên bàn cờ $n \times n$ ô có bao nhiêu hình vuông (mọi kích thước, cạnh nằm trên đường kẻ)? Với $n = 2$ có 4 hình vuông nhỏ và 1 hình vuông lớn, tổng 5. Vét cạn: duyệt cạnh $k$, rồi duyệt góc trên trái $(i, j)$ sao cho hình vuông không lòi ra ngoài. In bảng và tính hiệu liên tiếp $\Delta_1(n) = f(n) - f(n-1)$, rồi hiệu của hiệu:
| n | f(n) | $\Delta_1$ | $\Delta_2$ | $\Delta_3$ |
|---|---|---|---|---|
| 1 | 1 | |||
| 2 | 5 | 4 | ||
| 3 | 14 | 9 | 5 | |
| 4 | 30 | 16 | 7 | 2 |
| 5 | 55 | 25 | 9 | 2 |
| 6 | 91 | 36 | 11 | 2 |
| 7 | 140 | 49 | 13 | 2 |
| 8 | 204 | 64 | 15 | 2 |
Bảng 3. Số hình vuông trên bàn cờ $n \times n$. Hiệu bậc 1 là 4, 9, 16, 25… (số chính phương!), hiệu bậc 3 không đổi bằng 2.
Đọc bảng: hiệu bậc 1 là $n^2$, tức là $f(n) = f(n - 1) + n^2$, suy ra $f(n) = 1^2 + 2^2 + \cdots + n^2$. Hiệu bậc 3 là hằng số nên $f$ là đa thức bậc 3, khớp với công thức quen thuộc $f(n) = \frac{n(n+1)(2n+1)}{6}$. Lý giải lại cho chắc: hình vuông cạnh $k$ có $(n - k + 1)^2$ vị trí đặt góc, cộng lại theo $k$ đúng là tổng các bình phương. Chương trình dưới in bảng so sánh vét cạn với công thức, có dòng nào lệch sẽ báo ngay:
Xem code C++ / Python: in bảng vét cạn và so với công thức đoán được (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
long long brute(int n){ // vét cạn: chắc chắn đúng, chậm cũng được
long long cnt = 0;
for(int k = 1; k <= n; k++) // cạnh hình vuông
for(int i = 0; i + k <= n; i++) // hàng của góc trên trái
for(int j = 0; j + k <= n; j++) // cột của góc trên trái
cnt++;
return cnt;
}
long long formula(long long n){ // công thức đoán được
return n * (n + 1) * (2 * n + 1) / 6;
}
int main(){
int N;
cin >> N;
for(int n = 1; n <= N; n++){
cout << n << " " << brute(n) << " " << formula(n);
if(brute(n) != formula(n)) cout << " <-- SAI";
cout << "\n";
}
return 0;
}def brute(n): # vét cạn: chắc chắn đúng, chậm cũng được
cnt = 0
for k in range(1, n + 1): # cạnh hình vuông
for i in range(n - k + 1): # hàng của góc trên trái
for j in range(n - k + 1):
cnt += 1
return cnt
def formula(n): # công thức đoán được
return n * (n + 1) * (2 * n + 1) // 6
N = int(input())
for n in range(1, N + 1):
line = f"{n} {brute(n)} {formula(n)}"
if brute(n) != formula(n):
line += " <-- SAI"
print(line)Mô phỏng dưới đây làm đúng 4 bước trên cho ba bài khác nhau. Bài “XOR 1..n” không phải đa thức: hiệu lộn xộn, nhưng thêm cột $n \bmod 4$ thì quy luật hiện ra ngay. Em đổi bài và đổi $N$ để tự quan sát:
| Dấu hiệu trong bảng | Dạng quy luật | Ví dụ |
|---|---|---|
| Hiệu bậc $k$ không đổi | đa thức bậc $k$ của $n$ | $\Delta_2$ hằng số → $an^2 + bn + c$, giải hệ từ 3 dòng đầu |
| Tỉ số $f(n)/f(n-1)$ không đổi | lũy thừa (cấp số nhân) | 1, 3, 9, 27 → $3^{n-1}$ |
| Mỗi số bằng tổng hai số trước | Fibonacci | số cách lát hành lang $2 \times n$ bằng gạch $1 \times 2$ |
| Lặp lại sau $p$ dòng | chu kỳ, dùng $n \bmod p$ | XOR $1..n$, chữ số tận cùng của $2^n$ |
| Khác nhau theo chẵn lẻ | chia hai trường hợp | $n$ chẵn: $n/2$, $n$ lẻ: $0$ |
Bảng 4. Những dạng quy luật hay gặp nhất khi nhìn bảng số.
Phần 4Chu kỳ: khi dãy số lặp lại
Chữ số tận cùng của $a^n$. Chữ số tận cùng của tích chỉ phụ thuộc chữ số tận cùng của các thừa số, nên chữ số tận cùng của $2^n$ là: 2, 4, 8, 6, 2, 4, 8, 6, … lặp lại sau 4 bước. Mọi chữ số đều có chu kỳ 1, 2 hoặc 4:
| Chữ số cuối của a | Chữ số cuối của $a^1, a^2, a^3, a^4, a^5$ | Chu kỳ |
|---|---|---|
| 0 | 0, 0, 0, 0, 0, … | 1 |
| 1 | 1, 1, 1, 1, 1, … | 1 |
| 2 | 2, 4, 8, 6, 2, … | 4 |
| 3 | 3, 9, 7, 1, 3, … | 4 |
| 4 | 4, 6, 4, 6, 4, … | 2 |
| 5 | 5, 5, 5, 5, 5, … | 1 |
| 6 | 6, 6, 6, 6, 6, … | 1 |
| 7 | 7, 9, 3, 1, 7, … | 4 |
| 8 | 8, 4, 2, 6, 8, … | 4 |
| 9 | 9, 1, 9, 1, 9, … | 2 |
Bảng 5. Chữ số tận cùng của lũy thừa. Chu kỳ luôn chia hết 4, nên chữ số cuối của $a^n$ (với $n \ge 1$) bằng chữ số cuối của $a^{((n-1) \bmod 4) + 1}$.
Vì thế dù $n = 10^{18}$, chữ số tận cùng của $7^n$ chỉ cần $(n - 1) \bmod 4 + 1 = 4$, tức là bằng chữ số cuối của $7^4 = 2401$, là 1. Nhớ trường hợp đặc biệt $n = 0$: $a^0 = 1$.
Vì sao dãy nào cũng phải lặp? Xét dãy $x_{k+1} = f(x_k)$ với mọi giá trị nằm trong $0..m-1$ (ví dụ $f(x) = (x^2 + c) \bmod m$). Chỉ có $m$ giá trị khác nhau, nên trong $m + 1$ số hạng đầu chắc chắn có hai số bằng nhau (nguyên lý Dirichlet: $m + 1$ chú chim, $m$ cái chuồng). Và vì số hạng sau chỉ phụ thuộc số hạng trước, một khi $x_t = x_\mu$ thì $x_{t+1} = x_{\mu+1}$, $x_{t+2} = x_{\mu+2}$… dãy đi lại đúng con đường cũ mãi mãi. Hình dạng của dãy giống chữ ρ: một đuôi dài $\mu$ rồi một vòng dài $\lambda = t - \mu$.
Hình 2. Dãy $x_{k+1} = (x_k^2 + 1) \bmod 10$ từ $x_0 = 3$: số 3 chỉ xuất hiện một lần (đuôi), sau đó 0, 1, 2, 5, 6, 7 lặp mãi (chu kỳ dài 6).
Tìm chu kỳ bằng mảng đánh dấu. Dùng mảng first[v] = bước đầu tiên gặp giá trị $v$ (khởi tạo $-1$). Sinh lần lượt $x_0, x_1, \ldots$; với mỗi $x_t$:
- nếu
first[x_t] = -1: giá trị mới, ghifirst[x_t] = tvà lưu $x_t$ vào mảngxs; - nếu đã có
first[x_t] = μ: tìm được chu kỳ, $\lambda = t - \mu$. Khi đó số hạng thứ $N \ge \mu$ là $x_{\mu + (N - \mu) \bmod \lambda}$, còn $N < t$ thì có sẵn trongxs.
Chỉ sinh tối đa $m + 1$ số hạng, bộ nhớ $O(m)$, rồi trả lời cho $N$ tới $10^{18}$ bằng một phép chia lấy dư. Em xem mảng first được lấp dần và đúng lúc gặp lại thì chu kỳ hiện ra:
Xem code C++ / Python: tìm chu kỳ bằng mảng đánh dấu, tính số hạng thứ N (N tới 10^18) (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long x, c, m, N;
cin >> x >> c >> m >> N;
vector<int> first(m, -1); // first[v]: bước đầu tiên gặp giá trị v
vector<long long> xs; // các số hạng đã sinh
for(int t = 0; ; t++){
if(first[x] != -1){ // gặp lại: chu kỳ bắt đầu từ first[x]
long long mu = first[x], lam = t - mu;
long long idx = (N < t) ? N : mu + (N - mu) % lam;
cout << xs[idx];
return 0;
}
first[x] = t;
xs.push_back(x);
x = (x * x + c) % m; // sinh số hạng tiếp theo
}
}x, c, m, N = map(int, input().split())
first = [-1] * m # first[v]: bước đầu tiên gặp giá trị v
xs = [] # các số hạng đã sinh
t = 0
while first[x] == -1:
first[x] = t
xs.append(x)
x = (x * x + c) % m # sinh số hạng tiếp theo
t += 1
mu = first[x] # gặp lại: chu kỳ bắt đầu từ first[x]
lam = t - mu
idx = N if N < t else mu + (N - mu) % lam
print(xs[idx])first trả lời đúng cả hai câu hỏi “bắt đầu lặp từ đâu” ($\mu$) và “lặp sau bao lâu” ($\lambda$). Cũng nhớ kiểm tra riêng các trường hợp $N = 0$ và $N < \mu$.first[a][b] hoặc map. Tương tự với robot trên lưới (trạng thái = ô + hướng) hay lịch (chu kỳ 400 năm ở chuyên đề 4). Bài tập 6 và 8 luyện đúng kỹ thuật này.Phần 5Những công thức hay dùng và bẫy tràn số
| Đại lượng | Công thức | Ghi chú |
|---|---|---|
| $1 + 2 + \cdots + n$ | $\frac{n(n+1)}{2}$ | cũng là số đoạn con của dãy $n$ phần tử |
| $1^2 + 2^2 + \cdots + n^2$ | $\frac{n(n+1)(2n+1)}{6}$ | số hình vuông trên bàn cờ $n \times n$ |
| $1^3 + 2^3 + \cdots + n^3$ | $\left(\frac{n(n+1)}{2}\right)^2$ | số hình chữ nhật trên bàn cờ $n \times n$ |
| Số cặp $i < j$ trong $n$ phần tử | $\frac{n(n-1)}{2}$ | số cái bắt tay, số đoạn thẳng nối $n$ điểm |
| Cấp số cộng: số số hạng từ $u$ tới $v$, công sai $d$ | $\frac{v - u}{d} + 1$ | tổng = (đầu + cuối) × số số hạng / 2 |
| Cấp số nhân: $1 + q + \cdots + q^{n-1}$ | $\frac{q^n - 1}{q - 1}$ | $q \ne 1$; có modulo thì xem bài 26 |
| Số điểm nguyên trên đoạn nối $(x_1, y_1)$, $(x_2, y_2)$ | $\gcd(|x_2 - x_1|, |y_2 - y_1|) + 1$ | tính cả hai đầu mút |
Bảng 6. Bảng công thức nên thuộc. Mọi công thức đều kiểm chứng được bằng một vòng for nhỏ, đúng như quy trình ở phần 3.
Cấp số cộng trong đề thi. Tính tổng các số chia hết cho $k$ trong đoạn $[L, R]$ (với $L, R \ge 1$): số đầu tiên là $u = \lceil L / k \rceil \cdot k$, số cuối là $v = \lfloor R / k \rfloor \cdot k$; nếu $u \le v$ thì có $c = (v - u)/k + 1$ số, tổng là $(u + v) \cdot c / 2$. Ví dụ $k = 3$, đoạn $[10, 25]$: $u = 12$, $v = 24$, $c = 5$, tổng $= 36 \cdot 5 / 2 = 90$ (12 + 15 + 18 + 21 + 24). Đếm bội trong đoạn đã học kỹ ở chuyên đề 6.
Điểm nguyên trên đoạn thẳng. Đoạn nối $(0, 0)$ với $(6, 4)$: bước nhỏ nhất để từ một điểm nguyên sang điểm nguyên kế tiếp là $(6/g, 4/g)$ với $g = \gcd(6, 4) = 2$, tức $(3, 2)$. Có $g$ bước nên có $g + 1 = 3$ điểm nguyên: $(0, 0)$, $(3, 2)$, $(6, 4)$. ƯCLN bằng thuật toán Euclid ở bài 12.
Bẫy tràn số. Công thức thì ngắn nhưng các thừa số rất to. $\frac{n(n+1)}{2}$ với int n = 100000 đã tràn ($n(n+1) \approx 10^{10}$). $n(n+1)(2n+1)$ với $n = 3 \cdot 10^6$ khoảng $5{,}4 \cdot 10^{19}$, tràn cả long long dù kết quả cuối $\approx 9 \cdot 10^{18}$ vẫn vừa. Hai cách chữa:
- Chia trước, nhân sau: trong $n$ và $n + 1$ có đúng một số chẵn, chia số đó cho 2 trước; trong $n$, $n + 1$, $2n + 1$ luôn có một số chia hết cho 3, chia số đó cho 3 trước. Sau đó các thừa số nhỏ hơn hẳn.
- Lấy modulo từng thừa số khi đề yêu cầu in kết quả $\bmod (10^9 + 7)$, nhưng chỉ sau khi đã chia xong (không được chia cho 6 sau khi lấy modulo, phải dùng nghịch đảo ở bài 26).
Xem code C++ / Python: tổng bình phương 1..n theo modulo với n tới 10^18 (chia trước rồi mới nhân) (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int main(){
long long n;
cin >> n;
long long a = n, b = n + 1, c = 2 * n + 1; // 2n + 1 <= 2*10^18 + 1 vẫn vừa long long
if(a % 2 == 0) a /= 2; else b /= 2; // chia 2 TRƯỚC khi nhân
if(a % 3 == 0) a /= 3; // một trong ba thừa số chia hết cho 3
else if(b % 3 == 0) b /= 3;
else c /= 3;
cout << (a % MOD) * (b % MOD) % MOD * (c % MOD) % MOD;
return 0;
}MOD = 10**9 + 7
n = int(input())
# Python không tràn số, nhưng phải dùng // (chia nguyên), KHÔNG dùng /
print(n * (n + 1) * (2 * n + 1) // 6 % MOD)n * (n + 1) / 2 trong Python cho ra số thực (float). Với $n = 10^{17}$, float chỉ giữ khoảng 16 chữ số có nghĩa nên kết quả bị làm tròn sai. Luôn dùng phép chia nguyên // và chia sau cùng khi tích chắc chắn chia hết. Trong C++, kiểm tra nhanh: giá trị lớn nhất của mỗi thừa số nhân với nhau có vượt $9{,}2 \cdot 10^{18}$ không? Nếu có, chia trước hoặc dùng __int128.- Bánh Rán (Dễ)
- Two Sets (CSES 1092) (Dễ)
- Con Ốc Sên (SNAIL) (Dễ)
- Loop (Trung bình)
- Tìm xn (Trung bình)
- Đếm Cặp Version 2 (Trung bình)
- Trọng Số Của Xâu (Khá)
Bài tậpLuyện đếm và tìm quy luật
Mật khẩu là một xâu gồm đúng $n$ chữ số (được bắt đầu bằng 0). Đếm số mật khẩu chứa ít nhất một chữ số 7. Vì đáp án rất lớn, in phần dư khi chia cho $10^9 + 7$. Giới hạn: $1 \le n \le 10^6$.
219📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
pow(10, n, MOD)). Cẩn thận: sau khi lấy dư, $10^n \bmod p$ có thể nhỏ hơn $9^n \bmod p$, nên phải cộng thêm $p$ trước khi lấy dư lần cuối. Với $n = 2$: $100 - 81 = 19$ (07, 17, …, 97, 70, 71, …, 79, trừ 77 bị đếm hai lần).Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int main(){
int n;
cin >> n;
long long p10 = 1, p9 = 1;
for(int i = 0; i < n; i++){
p10 = p10 * 10 % MOD;
p9 = p9 * 9 % MOD;
}
cout << ((p10 - p9) % MOD + MOD) % MOD; // tất cả - không có số 7
return 0;
}MOD = 10**9 + 7
n = int(input())
p10 = pow(10, n, MOD) # hàm pow có sẵn: 10^n mod MOD
p9 = pow(9, n, MOD)
print((p10 - p9) % MOD) # tất cả - không có số 7 (Python tự cho số dư không âm)Cho dãy $n$ số nguyên $a_1, \ldots, a_n$ ($1 \le n \le 2 \cdot 10^5$, $|a_i| \le 1000$). Với mỗi đoạn con liên tiếp $[l, r]$ tính tổng các phần tử trong đoạn, rồi in tổng của tất cả các tổng đó.
3
1 2 320📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long cho mọi phép nhân.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
long long total = 0;
for(long long i = 1; i <= n; i++){
long long x;
cin >> x;
total += x * i * (n - i + 1); // a[i] nằm trong i * (n - i + 1) đoạn
}
cout << total;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
total = 0
for i in range(1, n + 1):
total += int(data[i]) * i * (n - i + 1) # a[i] nằm trong i * (n - i + 1) đoạn
print(total)Có $T$ câu hỏi ($T \le 10^5$), mỗi câu cho hai số nguyên $a, n$ ($1 \le a \le 10^{18}$, $0 \le n \le 10^{18}$). In chữ số tận cùng của $a^n$, mỗi đáp án một dòng.
4
2 10
7 3
12 0
1000000000000000000 10000000000000000004
3
1
0📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int T;
cin >> T;
while(T--){
long long a, n;
cin >> a >> n;
if(n == 0){ cout << 1 << "\n"; continue; }
int d = a % 10, e = (n - 1) % 4 + 1; // chu kỳ chia hết 4
int r = 1;
for(int i = 0; i < e; i++) r = r * d % 10;
cout << r << "\n";
}
return 0;
}import sys
data = sys.stdin.buffer.read().split()
T = int(data[0])
out = []
for k in range(T):
a, n = int(data[1 + 2 * k]), int(data[2 + 2 * k])
if n == 0:
out.append(1)
continue
e = (n - 1) % 4 + 1 # chu kỳ chia hết 4
out.append(pow(a % 10, e) % 10)
print('\n'.join(map(str, out)))Cho $n$ điểm trên mặt phẳng ($2 \le n \le 2 \cdot 10^5$, toạ độ nguyên, $|x_i|, |y_i| \le 10^8$). Khoảng cách Manhattan giữa hai điểm là $|x_i - x_j| + |y_i - y_j|$. Tính tổng khoảng cách của mọi cặp điểm.
3
0 0
1 2
3 110📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long pairSum(vector<long long> a){ // tổng |a_i - a_j| mọi cặp
sort(a.begin(), a.end());
long long n = a.size(), s = 0;
for(long long i = 0; i < n; i++) s += a[i] * (2 * i - n + 1);
return s;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<long long> x(n), y(n);
for(int i = 0; i < n; i++) cin >> x[i] >> y[i];
cout << pairSum(x) + pairSum(y); // hai trục độc lập
return 0;
}import sys
def pair_sum(a): # tổng |a_i - a_j| mọi cặp
a.sort()
n = len(a)
return sum(v * (2 * i - n + 1) for i, v in enumerate(a))
data = sys.stdin.buffer.read().split()
n = int(data[0])
x = [int(data[1 + 2 * i]) for i in range(n)]
y = [int(data[2 + 2 * i]) for i in range(n)]
print(pair_sum(x) + pair_sum(y)) # hai trục độc lậpMột tấm lưới gồm $n$ hàng, $m$ cột ô vuông đơn vị ($1 \le n, m \le 5 \cdot 10^4$). Đếm số hình chữ nhật (mọi kích thước, kể cả hình vuông) có cạnh nằm trên đường kẻ, và số hình vuông. In hai số trên một dòng.
2 318 8📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n, m;
cin >> n >> m;
long long rect = (n * (n + 1) / 2) * (m * (m + 1) / 2); // chọn 2 đường ngang, 2 đường dọc
long long sq = 0;
for(long long k = 1; k <= min(n, m); k++) sq += (n - k + 1) * (m - k + 1);
cout << rect << " " << sq;
return 0;
}n, m = map(int, input().split())
rect = (n * (n + 1) // 2) * (m * (m + 1) // 2) # chọn 2 đường ngang, 2 đường dọc
sq = sum((n - k + 1) * (m - k + 1) for k in range(1, min(n, m) + 1))
print(rect, sq)Dãy Fibonacci: $F_0 = 0$, $F_1 = 1$, $F_k = F_{k-1} + F_{k-2}$. Cho $n$ và $m$ ($0 \le n \le 10^{18}$, $2 \le m \le 1000$), in $F_n \bmod m$.
100 105📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n, m;
cin >> n >> m;
long long a = 0, b = 1, p = 0; // cặp (F_k, F_k+1) mod m
do {
long long c = (a + b) % m;
a = b; b = c; p++;
} while(!(a == 0 && b == 1)); // quay lại cặp đầu tiên -> chu kỳ p
long long r = n % p;
a = 0; b = 1;
for(long long i = 0; i < r; i++){ long long c = (a + b) % m; a = b; b = c; }
cout << a;
return 0;
}n, m = map(int, input().split())
a, b, p = 0, 1, 0 # cặp (F_k, F_k+1) mod m
while True:
a, b = b, (a + b) % m
p += 1
if a == 0 and b == 1: # quay lại cặp đầu tiên -> chu kỳ p
break
a, b = 0, 1
for _ in range(n % p):
a, b = b, (a + b) % m
print(a)Cho số nguyên $r$ ($0 \le r \le 10^6$). Đếm số điểm $(x, y)$ có toạ độ nguyên nằm trong hoặc trên đường tròn tâm $O$ bán kính $r$, tức là $x^2 + y^2 \le r^2$.
213📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
math.isqrt cho nhanh). Nhờ đối xứng, cột $x$ và cột $-x$ giống nhau. Mẫu: cột $x = 0$ có 5 điểm, $x = \pm 1$ mỗi cột 3 điểm, $x = \pm 2$ mỗi cột 1 điểm, tổng 13. Dùng long long cho $r^2 = 10^{12}$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long r;
cin >> r;
long long h = r, total = 0;
for(long long x = 0; x <= r; x++){
while(x * x + h * h > r * r) h--; // h chỉ giảm khi x tăng
long long col = 2 * h + 1; // số điểm trên cột x
total += (x == 0) ? col : 2 * col; // cột x và cột -x
}
cout << total;
return 0;
}from math import isqrt
r = int(input())
rr = r * r
# cột x có 2h + 1 điểm với h = isqrt(r² - x²); cột x và cột -x giống nhau
total = (2 * r + 1) + 2 * sum(2 * isqrt(rr - x * x) + 1 for x in range(1, r + 1))
print(total)Cho dãy $x_0$ cho trước, $x_{k+1} = (x_k^2 + c) \bmod m$ ($2 \le m \le 10^6$, $0 \le x_0 < m$, $0 \le c \le 10^9$). Tính $S = x_0 + x_1 + \cdots + x_{N-1}$ với $1 \le N \le 10^{12}$.
3 1 10 1027📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
first như phần 4, đồng thời lưu tổng tiền tố $P_k = x_0 + \cdots + x_{k-1}$ của các số hạng đã sinh (gọi $t$ là số số hạng đã sinh). Nếu $N \le t$ thì đáp án là $P_N$. Ngược lại, lấy hết đuôi $P_\mu$, còn lại $N - \mu$ số hạng gồm $q = (N - \mu) / \lambda$ vòng trọn, mỗi vòng có tổng $P_t - P_\mu$, cộng phần lẻ $r = (N - \mu) \bmod \lambda$ số hạng đầu chu kỳ là $P_{\mu + r} - P_\mu$. Mẫu: dãy 3, 0, 1, 2, 5, 6, 7, 0, …: $\mu = 1$, $\lambda = 6$, tổng một vòng 21, $q = 1$, $r = 3$: $S = 3 + 21 + (0 + 1 + 2) = 27$. Chú ý $x^2$ tới $10^{12}$ và $c$ tới $10^9$: dùng long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long x, c, m, N;
cin >> x >> c >> m >> N;
vector<int> first(m, -1);
vector<long long> P(1, 0); // P[k] = x0 + ... + x(k-1)
long long t = 0;
while(first[x] == -1){
first[x] = t;
P.push_back(P.back() + x);
x = (x * x + c) % m;
t++;
}
long long mu = first[x], lam = t - mu;
if(N <= t){ cout << P[N]; return 0; }
long long q = (N - mu) / lam, r = (N - mu) % lam;
cout << P[mu] + q * (P[t] - P[mu]) + (P[mu + r] - P[mu]); // đuôi + q vòng + phần lẻ
return 0;
}x, c, m, N = map(int, input().split())
first = [-1] * m
P = [0] # P[k] = x0 + ... + x(k-1)
t = 0
while first[x] == -1:
first[x] = t
P.append(P[-1] + x)
x = (x * x + c) % m
t += 1
mu = first[x]
lam = t - mu
if N <= t:
print(P[N])
else:
q, r = divmod(N - mu, lam)
print(P[mu] + q * (P[t] - P[mu]) + (P[mu + r] - P[mu])) # đuôi + q vòng + phần lẻ
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét