Số 0 cuối cùng
Đề bài
Cho xâu $S$ gồm $n$ kí tự các chữ cái in thường (a đến z). Xét các hoán vị không lặp lại của xâu này. Ví dụ với xâu cbbb ta sẽ có 4 hoán vị: cbbb, bcbb, bbcb, bbbc.
Yêu cầu: tìm số lượng chữ số 0 tận cùng của số lượng các hoán vị không lặp của xâu đã cho.
Input:
- Dòng 1: chứa số nguyên $n$ $(1 \le n \le 10^4)$.
- Dòng 2: chứa xâu $S$.
Output: ghi một số nguyên là số lượng chữ số 0 tận cùng tìm được.
Scoring:
- Subtask #1 (50% số điểm): $n \le 15$.
- Subtask #2 (50% số điểm): $n \le 10^4$.
4
bcbb0Lời mở đầu
Với ví dụ bcbb: xâu có 3 chữ b và 1 chữ c, số hoán vị khác nhau là 4 (chữ c đứng ở 1 trong 4 vị trí). Số 4 không có chữ số 0 tận cùng nên đáp án là 0.
Bài này là sự kết hợp của 2 kiến thức rất hay gặp: đếm hoán vị lặp (cần đếm số lần xuất hiện mỗi chữ – dùng map) và đếm chữ số 0 tận cùng của một số khổng lồ mà không cần tính ra số đó. Mình đi từ cách tính thẳng (ăn subtask 1) tới cách dùng công thức Legendre (full điểm).
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
| Test | Thuộc | n | Đáp án | Cách 1 C++ | Cách 2 C++ | Python số lớn |
|---|---|---|---|---|---|---|
| 1–50 | Subtask 1 | 1 – 15 | 0 – 3 | 50/50 | 50/50 | 50/50 |
| 51–60 | Subtask 2 | 100 | 15 – 17 | 0/10 | 10/10 | 10/10 |
| 61–80 | Subtask 2 | 1.000 | 29 – 37 | 0/20 | 20/20 | 20/20 |
| 81–100 | Subtask 2 | 10.000 | 43 – 60 | 0/20 | 20/20 | 20/20 |
Bộ test có 100 test, chia đúng 50% – 50% như đề: test 1–50 có $n \le 15$ (subtask 1), test 51–100 có $n$ = 100, 1000 hoặc $10^4$ (subtask 2). Ba cột cuối là số test chạy đúng trong 1 giây (thời gian CPU). Ở subtask 1 có 14 test đáp án bằng 0 (ví dụ $n \le 4$ thì $n! \le 24$ không thể tận cùng bằng 0). Ở subtask 2 thì xâu chứa đủ 26 chữ cái, mỗi chữ lặp lại rất nhiều lần (tới khoảng 450 lần khi $n = 10^4$), đáp án lên tới 60.
Công thứcSố hoán vị không lặp
Nếu xâu có $n$ kí tự, trong đó chữ $c$ xuất hiện $\text{cnt}[c]$ lần, thì số hoán vị khác nhau là
bcbb: $P = \frac{4!}{3! \cdot 1!} = 4$.Để đếm $\text{cnt}[c]$ mình dùng map<char, int> (dùng mảng 26 phần tử cũng được). Câu hỏi còn lại: $P$ tận cùng bằng bao nhiêu chữ số 0?
50%Cách 1: tính thẳng P bằng số nguyên 64 bit
Với $n \le 15$ thì $n! \le 15! \approx 1.3 \cdot 10^{12}$, vừa kiểu unsigned long long. Ta tính $f = n!$, chia lần lượt cho $\text{cnt}[c]!$ (chia dần cho $2, 3, \ldots, \text{cnt}[c]$ – mỗi bước chia đều ra số nguyên), rồi đếm số 0 tận cùng bằng cách chia 10 tới khi không chia hết nữa.
Kết quả chạy thật: bản C++ đúng 50/50 test của subtask 1 (mỗi test gần như 0 giây), nhưng quá thời gian toàn bộ 50 test của subtask 2 – tổng cộng 50/100 test, đúng 50% điểm. Tab "Python (số lớn)" thì khác hẳn: Python có số nguyên không giới hạn nên tính chính xác được cả $10000!$, bản này đúng 100/100 test, chậm nhất 0.04 giây (CPU). Một cái bẫy nhỏ: lúc đầu mình đếm số 0 bằng str(f) và bị lỗi ở 20 test $n = 10^4$, vì từ Python 3.11 việc đổi số nguyên hơn 4300 chữ số sang xâu bị chặn (ValueError) – nên mình chuyển sang chia 10 dần như bản C++.
f *= i bị tràn số: unsigned long long tự động lấy dư cho $2^{64}$. Mà $100!$ chứa thừa số $2^{97}$, nên ngay khi tích có đủ 64 thừa số 2 thì $f$ trở thành đúng bằng 0! Sau đó chia mấy cũng vẫn là 0, và vòng while (f % 10 == 0) chạy mãi không dừng. Bài học: tràn số không chỉ cho kết quả sai, nó còn có thể làm chương trình treo.Ý tưởngChỉ cần đếm thừa số 2 và 5
Mỗi chữ số 0 tận cùng ứng với một thừa số $10 = 2 \cdot 5$. Nếu $P$ chứa $2^{a}$ và $5^{b}$ (trong phân tích ra thừa số nguyên tố) thì số chữ số 0 tận cùng là $\min(a, b)$. Và số mũ của một số nguyên tố trong thương bằng hiệu các số mũ:
Trong đó số mũ của $p$ trong $m!$ tính bằng công thức Legendre: $v_p(m!)$ $= \left\lfloor \frac{m}{p} \right\rfloor$ $+ \left\lfloor \frac{m}{p^2} \right\rfloor$ $+ \left\lfloor \frac{m}{p^3} \right\rfloor$ $+ \cdots$
Công thức Legendre dễ hiểu: trong các số $1, 2, \ldots, m$ có $\lfloor m/p \rfloor$ số chia hết cho $p$ (mỗi số góp 1 thừa số $p$), $\lfloor m/p^2 \rfloor$ số chia hết cho $p^2$ (góp thêm 1 thừa số nữa), ... Ví dụ $v_5(100!) = 20 + 4 = 24$, $v_2(10!) = 5 + 2 + 1 = 8$.
Lưu ý không được chỉ đếm thừa số 5 như bài "số 0 tận cùng của $n!$" quen thuộc: sau khi chia, số thừa số 2 có thể ít hơn số thừa số 5. Ví dụ xâu gồm 24 chữ a và 1 chữ b: $P = \frac{25!}{24! \cdot 1!} = 25$, có $b = 2$ nhưng $a = 0$, đáp án là 0.
Em nhập xâu rồi bấm Tiếp để xem từng bước tính $a$ và $b$:
100%Cách 2: công thức Legendre
- Hàm
legendre(m, p)chỉ lặp $\log_p m$ lần, biếnqđể kiểulong longcho chắc chắnq *= pkhông tràn. - Duyệt
mapbằngfor (auto it : cnt):it.firstlà chữ cái,it.secondlà số lần xuất hiện. - Bản Python của mình dùng đúng công thức này. Ngoài ra Python có số nguyên lớn nên có thể tính thẳng $P$ bằng
math.factorialrồi đếm số 0 ở cuối xâu – mình để ở tab "Python (số lớn)" của cách 1.
Kết quả chạy thật: C++ đúng 100/100 test, thời gian CPU lớn nhất 0.004 giây – mỗi test chỉ tốn $O(n)$ để đếm chữ cái. Bản Python cũng 100/100 test, chậm nhất 0.03 giây.
unsigned long long): 50/100 (đủ subtask 1, TLE cả subtask 2). Cách 2 (Legendre): C++ 100/100, Python 100/100. Bản Python số lớn (tính thẳng $P$): 100/100, CPU tối đa 0.04 s.
Nhận xét
Đăng nhận xét