**LỜI GIẢI**
Phát biểu lại bài toán: Đếm trong xâu $S$ số cặp xâu con $S\[i\dots j\]$ và $S\[k\dots t\]$ rời nhau và $S\[i\dots j\]$ trước $S\[k\dots t\]$ sao cho $S\[i\dots j\]+S\[k\dots t\]$ là palindrome.
Để ý tính chất sau (không mất tính tổng quát, giả sử $j-i \le t-k$): $S\[i\dots j\]+S\[k\dots t\]$ là palindrome $\iff S\[i\dots i+t-k\]$ khớp với $S\[k\dots t\]$ nghịch đảo $(1)$ và $S\[i+t-k+1\dots j\]$ là palindrome $(2)$ (tương tự với trường hợp còn lại).
Tính chất trên cho ta ý tưởng sau: Giả sử đếm được một nghiệm mà $S\[i\dots j\]$ khớp hoàn toàn với $S\[k\dots t\]$ nghịch đảo (điều kiện $(1)$), ta có thể tiếp tục "mở rộng" nghiệm này ra bằng cách đếm trong đoạn $\[j+1\dots k-1\]$ số palindrome bắt đầu từ $j+1$ hoặc kết thúc tại $k-1$ (điều kiện $(2)$) và ghép vào một trong hai xâu con của nghiệm đã có.
Ta hoàn toàn có thể tiền xử lí số palindrome như trên trong $O(n^2)$ bằng cách quy hoạch động song song với [truy vấn palindrome](https://www.marisaoj.com/problem/153):
> Gọi $dp\[L\]\[R\]\[0/1\]$ là số palindrome trong đoạn $\[L\dots R\]$ bắt đầu tại $L (0)$ hoặc kết thúc tại $R (1)$.
> Trường hợp cơ sở: Nếu $L > R$ thì đoạn rỗng và $dp\[L\]\[R\] = 0$.
> Nếu $S\[L\dots R\]$ là palindrome thì $dp\[L\]\[R\]\[0\] = dp\[L\]\[R-1\]\[0\] + 1$ và $dp\[L\]\[R\]\[1\] = dp\[L+1\]\[R\]\[1\] + 1$.
> Ngược lại, $dp\[L\]\[R\]\[0\] = dp\[L\]\[R-1\]\[0\]$ và $dp\[L\]\[R\]\[1\] = dp\[L+1\]\[R\]\[1\]$.
Do đó ta chỉ còn cần đếm số nghiệm "khớp hoàn toàn" như trên trong một độ phức tạp phù hợp với $n \le 5000$. Điều này cũng có thể được giải quyết bằng cách quy hoạch động:
> Nếu $S\[i\dots j\]$ và $S\[k\dots t\]$ là một nghiệm "khớp hoàn toàn" thì $S\[i+1\dots j\]$ và $S\[k\dots t-1\]$ cũng là một nghiệm như vậy. Nói cách khác, các nghiệm này "mở rộng" ra dần từ hai vị trí $j$ và $k$.
> Gọi $len\[j\]\[k\]$ là độ dài của nghiệm "khớp hoàn toàn" dài nhất "mở rộng" ra từ hai vị trí $j$ và $k$.
> Trường hợp cơ sở: Nếu $j < 1$ hoặc $k > n$ thì vị trí nằm ngoài mảng và $len\[j\]\[k\] = 0$.
> Nếu $S\[j\] = S\[k\]$ thì $len\[j\]\[k\] = len\[j-1\]\[k+1\] + 1$.
> Ngược lại $len\[j\]\[k\] = 0$.
> Song song với việc gán $len\[j\]\[k\]$, ta có thể đóng góp luôn $len\[j\]\[k\] \cdot (1 + dp\[j+1\]\[k-1\]\[0\] + dp\[j+1\]\[k-1\]\[1\])$ vào tổng kết quả.
Độ phức tạp của thuật toán là $O(n^2)$ tiền xử lí $dp$ và $O(n^2)$ xử lí $len$ cũng như góp vào kết quả, tổng cộng là $O(n^2)$, phù hợp với $n \le 5000$.
sasaki2c
Created at
0 likes