Biến đổi xâu đối xứng
Đề bài
Một xâu được gọi là đối xứng khi viết từ phải qua trái hay từ trái qua phải thì xâu đó không thay đổi. Nguyên là một người rất yêu thích xâu đối xứng và các bài toán liên quan về nó. Vào một ngày, anh ấy gặp bài toán như sau: Cho trước một xâu $S$ gồm ký tự in hoa $A$–$Z$. Hãy đếm số lượng xâu đối xứng có thể thu được bằng cách sắp xếp lại các ký tự trong xâu $S$.
Tuy rất giỏi về các bài toán về xâu đối xứng, nhưng hiện tại anh ấy vẫn chưa thể nghĩ ra ý tưởng cho bài toán này. Vì thế anh ấy rất muốn bạn giải quyết bài toán này.
Input
- Có một dòng duy nhất chứa xâu $s$.
Output
- Một số nguyên là số lượng xâu đối xứng có thể thu được (lấy phần dư của kết quả khi chia cho $M = 10^9 + 7$).
Scoring
- $50\%$ test: Độ dài của xâu $S$ không quá $10$ ký tự.
- $50\%$ test: Độ dài của xâu $S$ không quá $10^6$ ký tự.
ABBAA2Note: Có 2 xâu đối xứng thu được là: ABABA và BAAAB.
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
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 CodeforcesTrước tiên mình sẽ tóm tắt lại đề bài một cách đơn giản nhất để bạn nào chưa hiểu như sau: một xâu đối xứng là khi viết từ phải qua trái hay từ trái qua phải thì xâu đó đều không đổi. Cho bạn một xâu $S$ (có số ký tự $\le 10^6$) gồm các kí tự in hoa từ A tới Z. Từ xâu $S$ hãy đếm số lượng xâu đối xứng có thể được tạo ra bằng cách sắp xếp lại các kí tự trong xâu $S$.
Ví dụ $S$ = "ABBAA" ta có thể tạo ra 2 xâu đối xứng là "ABABA" và "BAAAB". Vậy kết quả ta cần in ra là $2$.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Sinh mọi hoán vị bằng next_permutation – 50% test
Cách làm đơn giản nhất của bài này chính là thực hiện theo y như đề bài thôi. Đề bài bảo sắp xếp lại các ký tự trong xâu $s$ thì ta sẽ sắp xếp lại tất cả các ký tự trong xâu $s$. Sau đó kiểm tra xem xâu ta tạo ra có bị trùng hay không (tức là ta đã từng tạo ra một xâu như vậy chưa), tại vì nhỡ trong xâu một ký tự có thể xuất hiện nhiều lần; từ đó sẽ có những trường hợp tráo đổi bị trùng nên ta cần check xâu đã từng tạo hay chưa. Nếu xâu là lần đầu được tạo ra thì ta sẽ check xem có phải xâu đối xứng không. Nếu có thì ta tăng biến đếm số xâu đối xứng tạo được lên 1. Còn không thì thôi.
Hàm next_permutation – sinh hoán vị không trùng
Mặc dù đây là cách làm đơn giản nhất nhưng khi vào code thì sẽ khá chi là phức tạp nha; việc tạo ra mọi cách sắp xếp trong xâu $S$ sao cho các cách sắp xếp là không trùng nhau được gọi là sinh hoán vị của xâu. Nếu các bạn tự xây dựng hàm thì sẽ khá là phức tạp, và việc lý giải ở đây cũng vô cùng khó, nên mình sẽ giới thiệu cho anh em nào chưa biết một hàm rất hay trong C++ đó chính là hàm next_permutation (dịch ra là hoán vị tiếp theo đó, các bạn có thể search để hiểu sâu hơn về hàm nha).
- Hàm này sẽ sinh ra tất cả các hoán vị cho bạn khi và chỉ khi đầu vào bạn truyền cho nó là 1 xâu, 1 mảng hay 1 vector đã sắp xếp tăng dần nha. Nếu không sắp xếp tăng dần thì nó sẽ không sinh ra hết đâu.
- Nó nhận tham số đầu vào là
(tên_xâu.begin(), tên_xâu.end()), mỗi lần gọi nó sẽ thay đổi các vị trí trong xâu để tạo ra hoán vị kế tiếp; nếu còn có thể tạo hoán vị thì nó trả vềtrue, không tạo được nữa thì nó trả vềfalse. - Các hoán vị trùng nhau (do ký tự lặp) được nó tự bỏ qua, nên ta không cần check trùng nữa.
Sau đây là một đoạn code nhỏ để các bạn nhìn cách ta dùng hàm đó:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string s = "ABBAA";
sort(s.begin(), s.end());
do {
cout << s << endl;
}while(next_permutation(s.begin(), s.end()));
return 0;
}Khi chạy đoạn code trên ta sẽ sinh ra được 10 hoán vị của xâu $s$:
| # | Hoán vị | check(s) |
|---|---|---|
| 1 | AAABB | ✘ |
| 2 | AABAB | ✘ |
| 3 | AABBA | ✘ |
| 4 | ABAAB | ✘ |
| 5 | ABABA | ✔ cnt++ |
| 6 | ABBAA | ✘ |
| 7 | BAAAB | ✔ cnt++ |
| 8 | BAABA | ✘ |
| 9 | BABAA | ✘ |
| 10 | BBAAA | ✘ |
Việc đầu tiên ta làm chính là sắp xếp lại xâu $s$ sao cho các kí tự tăng dần bằng hàm sort(). Sau đó các bạn sẽ thấy sao ta không while{} như bình thường mà phải là do{} while()? Bởi vì việc ta sắp xếp các kí tự trong xâu $s$ tăng dần cũng chính là sinh ra được 1 hoán vị rồi; nếu ta viết while(next_permutation(s.begin(), s.end())) {xử lý} thì ta sẽ bỏ lỡ mất hoán vị đầu tiên (chính là xâu đã được sắp xếp đó), vì ta chỉ cần gọi hàm next_permutation() là nếu nó sinh được hoán vị thì nó sẽ tráo đổi trong xâu để ra hoán vị mới luôn.
Chính vì vậy nên ta mới do (tức là làm trước, xử lý chạy trước) sau đó mới sinh hoán vị tiếp theo để lần tới chạy. Và khi đã sinh hết hoán vị (xâu bây giờ sắp xếp giảm dần) thì tự động hàm next_permutation sẽ thấy nó không thể sinh thêm hoán vị được nữa và dừng vòng lặp (trả về false đó).
Với hàm sort, next_permutation và một vòng lặp do{} while(); ta có thể dễ dàng sinh ra hoán vị của xâu mà không cần phải check trùng hay là code đệ quy dài + phức tạp nữa rồi. Việc của ta bây giờ là trong phần xử lý của do{} ta cần check xem xâu hoán vị đó có phải là xâu đối xứng hay không nữa thôi.
Kiểm tra xâu đối xứng trong O(n / 2)
Cách dễ nhất để check một xâu có phải xâu đối xứng hay không chính là tạo một xâu bản sao của xâu cần check, lật ngược xâu bản sao lại và so sánh 2 xâu; nếu xâu gốc và xâu bản sao bằng nhau thì chứng tỏ là xâu đối xứng, không thì không phải là xâu đối xứng. Việc check như trên sẽ làm ta tốn thời gian là $O(2 \cdot \text{độ dài xâu})$ vì ta phải copy ngược xâu sang xâu bản sao và làm thêm một bước so sánh.
Cách nhanh hơn và tối ưu hơn thì ta chỉ cần mất $O(\text{độ dài xâu} / 2)$ mà thôi, tức nhanh hơn gấp 4 lần. Vì xâu viết từ trái qua phải hay phải qua trái cũng đều như nhau nên chứng tỏ kí tự ở đầu xâu phải bằng kí tự ở cuối xâu; kí tự thứ hai của xâu phải bằng kí tự ở cuối xâu − 1; và cứ tương tự cho đến kí tự ở giữa xâu. Xâu lưu từ vị trí $0$ nên kí tự cuối là vị trí $n - 1$; tổng quát là kí tự số $i$ so với kí tự số $n - 1 - i$.
Và $i$ sẽ phải $< n / 2$: vì nếu xâu lẻ thì kí tự ở vị trí $n / 2$ là kí tự ở giữa xâu nên kí tự đó ta không phải check; còn nếu xâu chẵn thì không tồn tại kí tự ở giữa xâu, nhưng vị trí $n / 2$ sẽ lệch về phía bên phải xâu (anh em mà có xâu độ dài $6$ thì $6 / 2 = 3$, các kí tự được đánh số từ $0$ tới $5$ nên vị trí $3$ đã thuộc nửa phải) nên ta cũng chỉ cần đi tới $< n / 2$ là được rồi. Nếu ta check 2 kí tự đối xứng đó mà khác nhau thì return false luôn; còn nếu đi được hết vòng for mà không có cặp nào khác thì xâu đó là xâu đối xứng rồi, return true thôi. Sau đây là hàm check xâu đối xứng của mình nha:
bool check(string &s) {
int n = (int)s.length();
for(int i = 0; i < n / 2; ++i) {
if(s[i] != s[n - 1 - i]) {
return false;
}
}
return true;
}Vì độ dài xâu $s$ có thể sẽ rất lớn nên việc thêm tham chiếu (&s) sẽ giúp anh em cải thiện tốc độ chạy hơn nha; anh em đỡ phải copy xâu $s$ sang một xâu bản sao để truyền vào hàm.
Source code Cách 1
Vậy giờ mỗi lần sinh được hoán vị xâu ta chỉ việc check đối xứng, rồi nếu đúng thì tăng biến đếm thôi. Sau đây là Source Code của mình về ý tưởng trên cho anh em nào cần tham khảo nha:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll mod = (int)1e9 + 7;
bool check(string &s) {
int n = (int)s.length();
for(int i = 0; i < n / 2; ++i) {
if(s[i] != s[n - 1 - i]) {
return false;
}
}
return true;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
ll cnt = 0;
sort(s.begin(), s.end());
do {
if(check(s)) {
cnt++;
cnt %= mod;
}
}while(next_permutation(s.begin(), s.end()));
cout << cnt;
return 0;
}mod = 10**9 + 7
def check(s):
n = len(s)
for i in range(n // 2):
if s[i] != s[n - 1 - i]:
return False
return True
def next_permutation(s):
# giống std::next_permutation: đổi s thành hoán vị kế tiếp, hết thì trả về False
i = len(s) - 2
while i >= 0 and s[i] >= s[i + 1]:
i -= 1
if i < 0:
s.reverse()
return False
j = len(s) - 1
while s[j] <= s[i]:
j -= 1
s[i], s[j] = s[j], s[i]
s[i + 1:] = reversed(s[i + 1:])
return True
s = sorted(input().strip())
cnt = 0
while True:
if check(s):
cnt = (cnt + 1) % mod
if not next_permutation(s):
break
print(cnt)Giải thích 1 số chỗ trong code ở trên:
ios::sync_with_stdio(0); cin.tie(0);2 dòng đầu tiên của hàm main sẽ giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn đang code theo ngôn ngữ C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là sẽ ra rất nhiều bài viết giải thích nhé), nên kinh nghiệm trong các bài mà cần nhập xuất nhiều thì ta nên sử dụng 2 dòng trên. Trong bài này thì đầu vào là một xâu có thể lên tới $10^6$ kí tự nên các bạn nên thêm vào nha. Tất nhiên nếu các bạn code theo cú pháp của C thì chẳng cần mấy dòng đó làm gì, tuy nhiên thường khi code các bài lập trình thi đấu thế này ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó, vậy nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé.cnt %= mod;Đoạn này thì ta đang áp dụng đồng dư thức: thay vì cộng tất cả vào rồi mới chia dư thì ta sẽ chia dư mỗi khi cộng vào luôn. Kết quả thì vẫn như nhau nha.
Đánh giá độ phức tạp của cách làm trên: gọi độ dài xâu $s$ là $n$. Thực chất độ phức tạp sẽ là $n \log n$ (ở bước sort đó anh em) $+\ n \cdot n! \cdot \dfrac{n}{2}$ (độ phức tạp của việc sinh hết hoán vị bằng next_permutation là $n \cdot n!$, sau đó nhân với độ phức tạp hàm check); nhưng theo quy tắc Big O thì $n \log n$ là quá nhỏ so với cái kia nên:
Với cách trên thì chắc chắn ta sẽ bị TLE (Time Limit Exceeded – quá thời gian cho phép) rồi, vì với $n = 10^6$ thì số phép tính ta phải tính là rất rất lớn; với cách trên thì ta sẽ ăn được khoảng 6/10 test (subtask $n \le 10$: $10! \approx 3{,}6$ triệu hoán vị vẫn chạy kịp). Giờ ta sẽ cùng đi tới cách tối ưu hơn để AC (Accepted – được chấp nhận) bài này nha.
Nhận xétKhi nào tạo được xâu đối xứng?
Nếu các bạn hiểu được rõ về hàm check thì cũng sẽ hiểu được rằng để một xâu có thể đối xứng thì bắt buộc các kí tự xuất hiện trong nó phải xuất hiện chẵn lần; nếu có thì chỉ có duy nhất một kí tự được quyền xuất hiện lẻ lần mà thôi (ký tự đó đứng ở giữa). Nếu có nhiều hơn 1 kí tự xuất hiện lẻ lần thì chắc chắn ta không thể tạo ra xâu đối xứng từ xâu đó.
- Lấy xâu
abcabc: ta chỉ cần sắp xếp nửa đầu xâu làabc, acb, bac, bca, cab, cba. Sau đó ở nửa sau ta hoàn toàn có thể ghép vào tạo ra được xâu đối xứng, vì số kí tự là chẵn nên nửa trước như nào thì nửa sau ta hoàn toàn có thể ghép ứng vào được. Ví dụabcthì nửa sau sẽ làcba;acbthì nửa sau làbca; … vân vân. - Nếu xâu có một kí tự xuất hiện lẻ lần, ví dụ
abcabca: ta chỉ việc để một kí tựaở giữa, sau đó ta có…a…thì ở nửa trước ta lại điền được như trên làabc, acb, bac, bca, cab, cba. Tuyalẻ nhưng vì ta để một kí tự ở giữa rồi nên số kí tựacòn lại để ghép là chẵn, nên ta hoàn toàn có thể chia đối xứng ra 2 bên. - Nếu có từ 2 kí tự xuất hiện lẻ lần đổ lên, ví dụ
abcađi. Giờ mình đố anh em tạo ra được xâu đối xứng đó 😜. Lúc này vì tồn tại 2 thành phần lẻ nên ta sẽ không thể để thành phần nào ra giữa cả; thậm chí 3 thành phần lẻ thì càng không. Từ đó nếu có 2 kí tự xuất hiện lẻ lần đổ lên thì chắc chắn ta không thể tạo ra được xâu đối xứng.
Vậy ta hãy tạo một mảng đếm cnt[26] giúp ta đếm các kí tự trong xâu xuất hiện bao nhiêu lần. Sau khi đếm xong thì ta duyệt từ đầu mảng cnt đến cuối mảng cnt; nếu có từ 2 số lẻ trở lên (tức là có 2 kí tự có số lần xuất hiện lẻ) thì ta sẽ in ra kết quả là $0$ và kết thúc chương trình thôi; còn nếu thoả mãn điều kiện số kí tự xuất hiện lẻ lần $\le 1$ thì ta sẽ đến với bước tiếp theo.
Nghe hơi khó hiểu nhưng nếu giả sử a xuất hiện 10 lần, b 8 lần, c 12 lần, d 3 lần thì ta chỉ cần đếm hoán vị của xâu có 5 kí tự a, 4 kí tự b, 6 kí tự c và 1 kí tự d thôi. Số hoán vị đó sẽ chính là đáp án của bài toán luôn: xâu đó bản chất chính là nửa đầu xâu; ta xếp ra được cái gì thì ở nửa sau vì các kí tự chẵn nên sẽ luôn có các kí tự để ứng vào tạo ra xâu đối xứng; còn kí tự d xuất hiện lẻ lần thì cho 1 kí tự đó ra ở giữa "…. d ….", rồi ta còn 2 kí tự d thì nó lại chẵn rồi, bẻ đôi ra là còn 1 kí tự d cho vào nửa đầu.
Và khi vào code thì anh em không cần lấy số lần lẻ (ví dụ ở trên là 3) trừ đi 1 xong rồi mới chia 2 đâu, mà chỉ cần chia 2 luôn thôi. Vì ở C++ phép / giữa 2 số nguyên sẽ tự động làm tròn xuống: 3 / 2 = 1; 5 / 2 = 2.
Cách 2Hoán vị lặp + nghịch đảo modulo – O(N) – AC
Đến đây rồi không lẽ ta lại vẫn dùng hàm next_permutation để sinh hoán vị tiếp? Thế thì ta vẫn sẽ bị TLE thôi; mặc dù giảm đi được một nửa xâu nhưng một nửa của $10^6$ vẫn là quá lớn. Giờ ta thấy là ta chỉ cần biết số cách sắp xếp của xâu nửa đầu đó thôi là ta đã có kết quả của bài toán rồi. Bạn nào đến đây mà nghĩ là gọi xâu nửa đầu có $n$ kí tự, vậy số cách sắp xếp sẽ là $n!$ ($n$ giai thừa) là sai đó nha. Vì các kí tự trong xâu có thể trùng lặp mà; nhỡ đâu xâu đó là "AAAAAA" thì tính ra chỉ có 1 hoán vị thôi.
Công thức hoán vị lặp
Đến đây rồi thì các bạn phải biết về hoán vị lặp nha. Dành cho anh em nào chưa biết thì mình sẽ tiến cử cho anh em link này: Phương pháp giải bài toán hoán vị lặp (VietJack).
Với $n$ phần tử trong đó có $n_1$ phần tử loại 1, $n_2$ phần tử loại 2, $n_3$ phần tử loại 3, …, $n_k$ phần tử loại $k$ sao cho $n_1 + n_2 + \ldots + n_k = n$, thì số cách sắp xếp $n$ phần tử này là:
Bạn nào mà có trí tưởng tượng tốt thì hình dung ra rất dễ nha: ta có $n$ phần tử thì ta có $n!$ cách sắp xếp. Tại có $n_1$ phần tử loại 1 trùng nhau nên trong $n!$ cách đó, mỗi xâu bị đếm lặp $n_1!$ lần do tự các phần tử loại 1 đổi chỗ cho nhau; nếu có thêm $n_2$ phần tử loại 2 trùng nữa thì lại có thêm $n_2!$ trường hợp tự những phần tử loại 2 đổi chỗ cho nhau, và vân vân. Từ đó việc loại đi các trường hợp trùng thì ta sẽ chia cho $(n_1! \cdot n_2! \cdots n_k!)$ mà thôi.
Và các bạn xem: gọi nửa đầu xâu có $n$ kí tự, kí tự A xuất hiện $n_1$ lần, kí tự B xuất hiện $n_2$ lần, …, kí tự Z xuất hiện $n_{26}$ lần. Số cách sắp xếp nửa đầu của ta chính là $\dfrac{n!}{n_1! \cdot n_2! \cdots n_{26}!}$ mà thôi. Nếu kí tự nào không xuất hiện thì số lần của nó là $0$, và $0! = 1$ nên ở dưới mẫu nhân với 1 là không sao nha. Ví dụ đề ABBAA: nửa đầu có $n_A = 3/2 = 1$, $n_B = 2/2 = 1$, $n = 2$ → $\dfrac{2!}{1! \cdot 1!} = 2$. Khớp!
Chia trong modulo: dùng nghịch đảo modulo
Nhờ công thức trên ta có thể tính số cách sắp xếp nửa đầu rất nhanh rồi. Nhưng mà ta đâu thể lưu trữ tầm $(5 \cdot 10^5)!$ đâu vì đó là một số quá lớn. Nên trong quá trình tính giai thừa ta phải chia dư, trong quá trình tính mẫu số ta cũng sẽ phải chia dư liên tục để tránh bị tràn. Nhưng khó ở chỗ là trong đồng dư thức ta không có phép chia, nên anh em phải dùng nghịch đảo modulo.
Vì $M = 10^9 + 7$ là số nguyên tố, theo định lý Fermat nhỏ, nghịch đảo modulo của down chính là $\text{down}^{M-2} \bmod M$. Lũy thừa này tính trong $O(\log_2 M)$ bằng chia để trị: $a^b = (a^{b/2})^2$, nếu $b$ lẻ thì nhân thêm $a$ (đây là hàm powMod trong code bên dưới). Nếu anh em nào chưa biết về nghịch đảo modulo và cách tính $a^b \bmod m$ trong $\log_2(b)$ thì nên tìm hiểu kỹ trước nhé, đây là kiến thức rất hay gặp.
Mô phỏng ý tưởng
Em nhập một xâu chữ in hoa rồi bấm Tiếp để xem từng bước: đếm ký tự, kiểm tra số ký tự lẻ, dựng nửa đầu, tính công thức hoán vị lặp và (nếu ít) liệt kê luôn các xâu đối xứng:
Source code Cách 2
Sau đây là Source Code của mình về ý tưởng trên cho anh em nào cần tham khảo nha:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll mod = (ll)1e9 + 7;
ll factorials(int n) {
ll res = 1;
for(ll i = 2; i <= n; ++i) {
res = (res * i) % mod;
}
return res;
}
ll powMod(ll a, ll b, ll m) {
if(b == 0) {
return 1;
}
ll half = powMod(a, b / 2, m);
half = (half * half) % m;
if(b % 2) {
return (half * (a % m)) % m;
}
return half;
}
int cnt[26];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
for(int i = 0; i < (int)s.length(); ++i) {
cnt[(int)s[i] - (int)'A']++;
}
int cntOdd = 0, n = 0;
for(int i = 0; i < 26; ++i) {
n += cnt[i] / 2;
if(cnt[i] % 2) {
cntOdd++;
}
}
if(cntOdd > 1) {
cout << 0;
return 0;
}
ll up = factorials(n);
ll down = 1;
for(int i = 0; i < 26; ++i) {
down = (down * factorials(cnt[i] / 2)) % mod;
}
ll res = (up * powMod(down, mod - 2, mod)) % mod;
cout << res;
return 0;
}import sys
mod = 10**9 + 7
def factorials(n):
res = 1
for i in range(2, n + 1):
res = res * i % mod
return res
s = sys.stdin.readline().strip()
cnt = [0] * 26
for ch in s:
cnt[ord(ch) - ord('A')] += 1
cntOdd = 0
n = 0
for i in range(26):
n += cnt[i] // 2
if cnt[i] % 2:
cntOdd += 1
if cntOdd > 1:
print(0)
else:
up = factorials(n)
down = 1
for i in range(26):
down = down * factorials(cnt[i] // 2) % mod
# pow(down, mod - 2, mod) chính là nghịch đảo modulo của down
print(up * pow(down, mod - 2, mod) % mod)Giải thích 1 số chỗ trong code ở trên:
ll factorials(int n): hàm tính $n!$ nhưng có chia dư chomodnha; bạn sẽ thấy trong quá trình tính mình sẽ chia dư luôn để tránh tràn số, và hãy nhớ khai báolong longđể nhân vào không bị tràn.ll powMod(ll a, ll b, ll m): hàm tính $a^b \bmod m$ để giúp ta tính được nghịch đảo modulo của mẫu nha.int cnt[26];: đây chính là mảng đếm; vì trong tiếng Anh có 26 chữ cái nên mình tạo mảng có độ lớn là 26, và mình khai báo toàn cục thì mặc định lúc đầu các phần tử sẽ bằng 0 nha.cnt[(int)s[i] - (int)'A']++;: ở đây ta trừ đi'A'chính là đang đổi ký tự sang số nguyên:'A' - 'A' = 0, và cứ vậy đến'Z' - 'A' = 25nha. Vì các kí tự trong xâu là chữ cái in hoa nên mình mới trừ đi'A'.int cntOdd = 0, n = 0;: đoạn này và vòngforở dưới chính là ta đang tính $n$ (độ dài của nửa xâu đó anh em) vàcntOddgiúp ta đếm xem có bao nhiêu kí tự xuất hiện lẻ lần. NếucntOdd > 1thì chứng tỏ có từ 2 kí tự xuất hiện lẻ lần đổ lên và kết quả dĩ nhiên là $0$ rồi, sau đó ta thoát chương trình thôi.ll up = factorials(n); ll down = 1;:upchính là tử số $n!$,downtương đương với mẫu số.down = (down * factorials(cnt[i] / 2)) % mod;: ở đây ta đang áp công thức mẫu $= n_1! \cdot n_2! \cdots n_{26}!$ đó anh em; phần tử nào không xuất hiện thì $0! = 1$ nên nhân vào không sao. Vàcnt[i] / 2là vì ta đã quy ước ở nửa đầu thì số lần mỗi kí tự xuất hiện bằng một nửa số lần xuất hiện ở toàn xâu: $n_1 = \text{cnt}[0] / 2$, …, $n_{26} = \text{cnt}[25] / 2$. Trong quá trình tính mẫu ta liên tục chia dư để tránh tràn số.ll res = (up * powMod(down, mod - 2, mod)) % mod;: lúc này kết quả sẽ bằng tửupnhân với nghịch đảo modulo của mẫu làpowMod(down, mod - 2, mod), sau đó tất cả chia dư chomodlà ra.
Đánh giá độ phức tạp: $n$ (độ dài nửa đầu) bằng một nửa độ dài xâu $s$. Hàm tính giai thừa có độ phức tạp $O(n)$; ta dùng nó để tính tử số một lần là $O(n)$, sau đó tính mẫu thì là $O(n_1 + n_2 + \ldots + n_{26}) = O(n)$ lần nữa, thêm $O(\log M)$ cho powMod. Vậy tổng cộng là $O(|s|)$. Mà độ dài của xâu $s$ tối đa là $10^6$ thì code ta hoàn toàn dưới 1 giây một cách dễ dàng nha.
next_permutation cho giống C++, bản Cách 2 dùng hàm có sẵn pow(down, mod - 2, mod) để tính nghịch đảo modulo). Cả 4 bản đã được kiểm tra với 250 bộ test ngẫu nhiên (độ dài 1–10, có cả xâu toàn 1 ký tự, xâu nhiều ký tự lẻ, xâu đủ 26 chữ cái) so với cách đếm trực tiếp bằng định nghĩa (liệt kê mọi hoán vị khác nhau rồi đếm xâu đối xứng): khớp 100%. Với xâu dài $10^6$, bản C++ Cách 2 chạy khoảng 0.02 giây, bản Python khoảng 0.4 giây; Cách 1 với xâu 10 ký tự khác nhau chạy khoảng 0.03 giây (C++) và 4.5 giây (Python – nên bản Python Cách 1 chỉ để tham khảo ý tưởng).
Nhận xét
Đăng nhận xét