## Tóm tắt đề
Cho hai xâu *S*, *T* có cùng độ dài *n*. Với mỗi cặp chỉ số \$1 \le i < j \le n-1\$, đặt
* \$T\_a = T\_1T\_2\dots T\_i\$ (độ dài *a* = *i*),
* \$T\_b = T\_{i+1}\dots T\_j\$ (độ dài *b* = *j* − *i*),
* \$T\_c = T\_{j+1}\dots T\_n\$ (độ dài *c* = *n* − *j*),
và yêu cầu: cặp \$(i,j)\$ là **tốt** nếu có thể **hoán vị** ba đoạn \$T\_a, T\_b, T\_c\$ rồi **nối lại** để được đúng xâu *S*. Đếm số cặp tốt. Ràng buộc: \$1 \le n \le 5000\$. ([MarisaOJ - Marisa Online Judge][1])
## Ý tưởng chính
Với một cặp \$(i,j)\$ cố định, độ dài ba khối là *a*, *b*, *c* đã xác định. Khi đó, *S* cũng bị chia tự nhiên thành ba đoạn theo **cùng bộ độ dài**:
* \$S\_A = S\[1..a]\$,
* \$S\_B = S\[a+1..a+b]\$,
* \$S\_C = S\[a+b+1..n]\$.
Điều kiện “hoán vị \$T\_a,T\_b,T\_c\$ rồi ghép lại bằng *S*” tương đương với việc **một trong 6 hoán vị** sau đúng đắn:
$$
S = T_a T_b T_c \ \text{hoặc}\ T_a T_c T_b \ \text{hoặc}\ T_b T_a T_c \ \text{hoặc}\ T_b T_c T_a \ \text{hoặc}\ T_c T_a T_b \ \text{hoặc}\ T_c T_b T_a.
$$
Như vậy, lời giải tự nhiên là **duyệt mọi** \$(i,j)\$ và **so khớp 6 cấu hình** trên.
## Thuật toán chi tiết
1. **Tiền xử lý băm**
* Tính mảng lũy thừa *p* và tiền tố băm `hashS`, `hashT` cho *S*, *T*.
* Hàm \$\text{getHash}(\cdot)\$ trả về băm của đoạn con bất kỳ trong \$O(1)\$.
2. **Duyệt cặp chia**
* Với mọi \$i=1..n-2\$ và \$j=i+1..n-1\$:
* Đặt *a* = *i*, *b* = *j* − *i*, *c* = *n* − *j*.
* Xác định chỉ số các đoạn:
* Trên *S*: \$S\_A = S\[1..a]\$, \$S\_B = S\[a+1..a+b]\$, \$S\_C = S\[a+b+1..n]\$.
* Trên *T*: \$T\_a = T\[1..i]\$, \$T\_b = T\[i+1..j]\$, \$T\_c = T\[j+1..n]\$.
* **Kiểm tra 6 hoán vị**, mỗi hoán vị gồm **3 so sánh đoạn** (khớp chiều dài):
* \$S\_A = T\_a\$, \$S\_B = T\_b\$, \$S\_C = T\_c\$;
* \$S\_A = T\_a\$, \$S\_B = T\_c\$, \$S\_C = T\_b\$;
* \$S\_A = T\_b\$, \$S\_B = T\_a\$, \$S\_C = T\_c\$;
* \$S\_A = T\_b\$, \$S\_B = T\_c\$, \$S\_C = T\_a\$;
* \$S\_A = T\_c\$, \$S\_B = T\_a\$, \$S\_C = T\_b\$;
* \$S\_A = T\_c\$, \$S\_B = T\_b\$, \$S\_C = T\_a\$.
* Nếu bất kỳ hoán vị nào khớp hoàn toàn, tăng kết quả thêm 1.
## Mã giả (Pseudocode)
```text
precompute_hash(S, T):
// p[k] = base^k mod MOD
// hashS[i], hashT[i] = băm tiền tố (1-index)
...
getHashS(l, r), getHashT(l, r):
// trả về băm đoạn con S[l..r] và T[l..r] trong O(1)
solve(S, T):
n = |S|
precompute_hash(S, T)
ans = 0
for i in 1..n-2:
for j in i+1..n-1:
a = i; b = j - i; c = n - j
SA = (1, a)
SB = (a+1, a+b)
SC = (a+b+1, n)
TA = (1, i)
TB = (i+1, j)
TC = (j+1, n)
ok = false
ok |= eq(SA, TA) and eq(SB, TB) and eq(SC, TC)
ok |= eq(SA, TA) and eq(SB, TC) and eq(SC, TB)
ok |= eq(SA, TB) and eq(SB, TA) and eq(SC, TC)
ok |= eq(SA, TB) and eq(SB, TC) and eq(SC, TA)
ok |= eq(SA, TC) and eq(SB, TA) and eq(SC, TB)
ok |= eq(SA, TC) and eq(SB, TB) and eq(SC, TA)
if ok: ans += 1
print(ans)
where eq((x1, x2), (y1, y2)) := getHashS(x1, x2) == getHashT(y1, y2)
```
> Lưu ý định dạng chỉ số: ở phần mã giả trên, tất cả **1-index** và đoạn là **đóng** $\[l, r]\$.
## Chứng minh tính đúng đắn
* Với cặp \$(i,j)\$, ba khối \$T\_a, T\_b, T\_c\$ là **ba đoạn con liên tiếp** của *T* với độ dài *a*, *b*, *c*. Nếu có thể hoán vị để tạo *S*, thì *S* chính là phép nối của **một hoán vị** trong \$6\$ hoán vị của \$(T\_a, T\_b, T\_c)\$. Do *S* cũng được chia thành ba đoạn \$S\_A,S\_B,S\_C\$ theo **cùng bộ độ dài**, điều kiện này tương đương với việc **một trong 6 cách ghép**: \$S\_A=S\_{\pi(1)}\$, \$S\_B=S\_{\pi(2)}\$, \$S\_C=S\_{\pi(3)}\$ với \$S\_{\pi(k)} \in {T\_a,T\_b,T\_c}\$ ứng với hoán vị \$\pi\$.
* Chiều ngược lại hiển nhiên: nếu một trong 6 cấu hình so khớp, thì nối ba đoạn tương ứng của *T* (theo hoán vị đó) sẽ đúng bằng *S*, nên \$(i,j)\$ là tốt.
## Độ phức tạp
* Tiền xử lý băm: \$O(n)\$ thời gian, \$O(n)\$ bộ nhớ.
* Duyệt \$(i,j)\$: có \$\binom{n-1}{2} = O(n^2)\$ cặp. Mỗi cặp kiểm tra **6 cấu hình**, mỗi cấu hình **3 so sánh đoạn** (mỗi so sánh \$O(1)\$).
Tổng thời gian \$O(n^2)\$, đủ nhanh với \$n \le 5000\$. (Có thể dùng **double-hash** nếu muốn hạn chế hơn rủi ro va chạm.)
tutithuybi123
Created at
1 likes