Palindrome Kép
Đề bài
Palindrome là một chuỗi kí tự mà khi đọc từ trái qua phải hoặc đọc từ phải qua trái đều nhận được kết quả như nhau.
Một chuỗi Palindrome kép là một chuỗi được gộp bởi hai chuỗi Palindrome có cùng độ dài.
Ví dụ: chuỗi $\{aabb\}$, $\{aaaa\}$ là các chuỗi palindrome kép, trong khi các chuỗi $\{abba\}$ và $\{aaaabb\}$ thì không.
Có bao nhiêu cách cắt ra từ xâu $S$ để có được một chuỗi palindrome kép? Nói cách khác: có bao nhiêu cặp $(l, r)$ mà chuỗi con $S_l S_{l+1} \ldots S_r$ là một chuỗi palindrome kép?
Dữ liệu
- Dòng 1: ghi số nguyên $n$ ($1 \le n \le 500\,000$);
- Dòng 2: chứa chuỗi $S$ có $n$ ký tự. Các kí tự trong chuỗi $S$ là các chữ cái tiếng Anh in thường.
Kết quả: một dòng duy nhất là một số nguyên: số xâu con là chuỗi palindrome kép tìm được.
Subtasks
- 19% số điểm với $n \le 500$;
- 33% số điểm với $n \le 5000$;
- 48% số điểm không có ràng buộc bổ sung.
6
abacac65
aaaaa6Liệt kê cụ thể 6 xâu con của ví dụ 1 (màu xanh là palin thứ nhất, màu cam là palin thứ hai):
| (l, r) | Xâu con | Hai nửa palindrome |
|---|---|---|
| (1, 2) | ab | a | b |
| (1, 6) | abacac | aba | cac |
| (2, 3) | ba | b | a |
| (3, 4) | ac | a | c |
| (4, 5) | ca | c | a |
| (5, 6) | ac | a | c |
Nộp bài
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
19%Subtask 1: duyệt và kiểm tra trực tiếp – O(n³)
Tư tưởng cơ bản:
- Đối với mỗi vị trí $i$, ta sẽ đếm xem có bao nhiêu vị trí $j$ thoả mãn sao cho $j \ge i$ và xâu con liên tiếp từ $i$ đến $j$ là một xâu palin kép.
- Để kiểm tra xem một xâu liên tiếp có phải là palin kép hay không: ta thấy rằng xâu palin kép là xâu được ghép lại bởi hai xâu palin có độ dài bằng nhau. Do đó chúng ta sẽ có các điều kiện kiểm tra sau:
- Độ dài của xâu con liên tiếp bắt buộc phải là chẵn (được ghép từ hai xâu có độ dài bằng $x$ nên độ dài hiện tại sẽ là $2x$, chia hết cho 2).
- Xâu palin đầu tiên sẽ là từ vị trí $i$ đến $i + \frac{j - i + 1}{2} - 1$. Xâu palin thứ hai sẽ là xâu còn lại. Lúc đó việc đơn giản là check riêng mỗi xâu có phải là palin hay không. Nếu cả hai đều là palin thì cộng kết quả lên một lượng là 1.
Độ phức tạp thuật toán: $O(n^3)$. Với $n \le 500$ thì chỉ khoảng vài chục triệu phép tính nên vẫn chạy kịp.
Em nhập 1 xâu rồi bấm Tiếp để xem cách duyệt mọi xâu con độ dài chẵn, cắt đôi và kiểm tra 2 nửa:
Xem code subtask 1
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
string s;
namespace subtask_1 {
int solve(){
int ans = 0;
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j += 2){
int ps = i + (j - i + 1) / 2 - 1;
bool ok = 1;
for(int l = i, r = ps; l <= r; l++, r--){
if(s[l] != s[r])
ok = 0;
}
for(int l = ps + 1, r = j; l <= r; l++, r--){
if(s[l] != s[r])
ok = 0;
}
ans += ok;
}
}
return ans;
}
}; // namespace subtask_1
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
cin >> s;
s = "#" + s;
cout << subtask_1::solve() << endl;
return 0;
}def solve(n, s):
ans = 0
s = "#" + s
for i in range(1, n + 1):
for j in range(i + 1, n + 1, 2):
ps = i + (j - i + 1) // 2 - 1
ok = True
l, r = i, ps
while l <= r:
if s[l] != s[r]:
ok = False
break
l += 1
r -= 1
l, r = ps + 1, j
while l <= r:
if s[l] != s[r]:
ok = False
break
l += 1
r -= 1
if ok:
ans += 1
return ans
n = int(input().strip())
s = input().strip()
print(solve(n, s))+33%Subtask 2: tính trước bảng check bằng cách mở rộng từ trọng tâm – O(n²)
Ở đây $n \le 5000$ nên ta nhận thấy cách ở subtask 1 không còn hiệu quả nữa. Ta sẽ tìm cách tối ưu việc kiểm tra một xâu có phải palin hay không. Ta gọi check[i][j] nhận giá trị là 0 hoặc 1 với:
check[i][j] = 1: xâu liên tiếp từ $i$ đến $j$ là xâu đối xứng;check[i][j] = 0: xâu liên tiếp từ $i$ đến $j$ không phải là xâu đối xứng.
Nhận xét rằng mỗi palin đều có 1 hoặc 2 điểm là trọng tâm:
- Nếu xâu palin có độ dài là lẻ, thì chỉ có kí tự ở giữa là trọng tâm. Ví dụ:
aabcbaa, ở xâu này thì trọng tâm sẽ rơi vào vị trí thứ 4, tức là ký tực. - Nếu xâu palin có độ dài là chẵn, thì có hai kí tự là trọng tâm. Ví dụ:
aaddaa, ở xâu này thì trọng tâm rơi vào vị trí 3 và 4, tức là 2 ký tựd.
Có thể thấy được rằng một xâu palin luôn được "mở rộng" từ trọng tâm. Ví dụ với aabcbaa, chúng ta có thể xây dựng xâu này bằng quy trình sau:
Điều này đồng nghĩa với việc mỗi lần "mở rộng" ta thêm hai ký tự giống nhau vào ở hai đầu của xâu. Từ nhận xét trên, ta có thể:
Trường hợp xâu palin lẻ: duyệt qua từng vị trí $x$ trong mảng. Lúc đó ta sẽ xem xét những xâu nhận $x$ là trọng tâm, ta sẽ thêm dần các kí tự ở hai bên $x$. Điều kiện để thêm là hai ký tự đó phải bằng nhau. Ví dụ ta có xâu abbcbbaa, giả sử giờ ta đang duyệt đến $x = 4$. Ta gọi xâu $s$ sẽ là xâu palin hiện tại, ban đầu ta đặt $s$ = c. Tiếp đến sau đó ta lần lượt thêm như sau:
Đến đây ta không thể thêm được nữa vì không còn ký tự nào đằng trước ký tự thứ nhất. Mỗi xâu thoả mãn ta đánh dấu check[l][r] = 1.
Trường hợp xâu palin chẵn: tương tự xâu palin lẻ nhưng ta sẽ coi trọng tâm của ta là $x$ và $x + 1$.
Đến đây ta đã có được kết quả của mảng check. Việc còn lại là làm tương tự như subtask 1, nhưng mà sẽ gọi thẳng kết quả xác định có phải palin hay không từ mảng check mà không cần chạy for để kiểm tra.
Độ phức tạp thuật toán: $O(n^2)$, với $n \le 5000$ là khoảng $2.5 \times 10^7$ phép tính.
Xem code subtask 2
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
string s;
bool check[5005][5005];
namespace subtask_2 {
int solve(){
int ans = 0;
for(int i = 1; i <= n; i++){
int l = i, r = i;
while(l >= 1 && r <= n){
if(s[l] != s[r])
break;
check[l][r] = 1;
l--;
r++;
}
}
for(int i = 2; i <= n; i++){
int l = i - 1, r = i;
while(l >= 1 && r <= n){
if(s[l] != s[r])
break;
check[l][r] = 1;
l--;
r++;
}
}
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j += 2){
int ps = i + (j - i + 1) / 2 - 1;
if(check[i][ps] && check[ps + 1][j])
ans++;
}
}
return ans;
}
}; // namespace subtask_2
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
cin >> s;
s = "#" + s;
cout << subtask_2::solve() << endl;
return 0;
}def solve(n, s):
s = "#" + s # để dùng chỉ số 1-based
check = [[False] * (n + 2) for _ in range(n + 2)]
ans = 0
# Các palindrome có độ dài lẻ
for i in range(1, n + 1):
l, r = i, i
while l >= 1 and r <= n:
if s[l] != s[r]:
break
check[l][r] = True
l -= 1
r += 1
# Các palindrome có độ dài chẵn
for i in range(2, n + 1):
l, r = i - 1, i
while l >= 1 and r <= n:
if s[l] != s[r]:
break
check[l][r] = True
l -= 1
r += 1
# Đếm các cặp (i, j)
for i in range(1, n + 1):
for j in range(i + 1, n + 1, 2):
ps = i + (j - i + 1) // 2 - 1
if check[i][ps] and check[ps + 1][j]:
ans += 1
return ans
n = int(input().strip())
s = input().strip()
print(solve(n, s))check kích thước $5000 \times 5000$ trong Python là list lồng list nên tốn khá nhiều bộ nhớ (cỡ vài trăm MB) và chạy mất khoảng 1 giây, nên có thể bị quá giới hạn bộ nhớ/thời gian tuỳ hệ thống chấm. Bản C++ dùng mảng bool chỉ tốn khoảng 25 MB.+48%Subtask 3: hash + chặt nhị phân + cây Fenwick – O(n log n)
Bước 1: độ dài palin lớn nhất nhận mỗi vị trí làm trọng tâm
Xét trường hợp những xâu palin kép có độ dài các palin cấu thành là lẻ. Đầu tiên, đối với mỗi vị trí $i$, chúng ta sẽ tìm độ dài của xâu palin có độ dài lớn nhất mà nhận $i$ làm trọng tâm. Điều này có thể thực hiện bằng hash và chặt nhị phân (so sánh hash xuôi của nửa bên phải với hash ngược của nửa bên trái).
Gọi len[x] là số ký tự ở nửa bên phải (tính cả trọng tâm) trong xâu palin dài nhất nếu nhận trọng tâm là $x$. Ví dụ với aaabb: ở vị trí 2, palin dài nhất nhận trọng tâm này sẽ là aaa, số ký tự nửa bên phải của nó sẽ là 2.
Bước 2: điều kiện để ghép được palin kép từ 2 trọng tâm x, y
Tiếp đến, trong một palin kép, hãy gọi $x$ là trọng tâm của palin thứ nhất, $y$ là trọng tâm của palin thứ hai ($x < y$). Hai palin có cùng độ dài lẻ nên khoảng cách $y - x$ chính bằng độ dài mỗi palin, là số lẻ; vì vậy ta nhận thấy rằng $x$, $y$ phải khác tính chẵn lẻ (đồng dư khác nhau khi chia cho 2).
Để có thể tạo ra một palin kép với hai trọng tâm là $x$, $y$, ta nhận xét rằng phải tồn tại một cách nào đó để cho rìa phải của palin trọng tâm $x$ chạm rìa trái của palin trọng tâm $y$. Suy ra độ dài lớn nhất mà palin ở trọng tâm $x$ và $y$ có thể tạo được phải lớn hơn hoặc bằng một nửa khoảng cách của hai vị trí $x$, $y$: $\frac{y - x + 1}{2}$. Khi đấy:
⇔ len[x] * 2 ≥ y − x + 1
⇔ y ≤ len[x] * 2 + x − 1
⇔ len[y] * 2 ≥ y − x + 1
⇔ y − len[y] * 2 + 1 ≤ x ≤ y
Bước 3: đếm bằng cây Fenwick, duyệt ngược x từ n về 1
Duyệt ngược $x$ từ $n$ về 1. Khi đó với mỗi $x$, ta cần đếm số lượng $y$ nằm trong khoảng $(x, \; len[x] \times 2 + x - 1]$ mà đồng thời thoả điều kiện thứ hai. Để làm được việc này, ta nhận xét rằng điều kiện thứ hai chỉ xảy ra nếu $x$ nằm trong khoảng từ $y - len[y] \times 2 + 1$ đến $y$. Tức là mỗi vị trí $y$ chỉ "còn hiệu lực" khi $x$ đi trong đoạn đó.
Ta sẽ sử dụng một cây segment tree / Fenwick tree, quản lý số lượng các vị trí trong phân đoạn bất kì đang phù hợp để làm trọng tâm $y$ hay không. Dựa vào điều này, ta có thể làm cách sau: khi $x$ chạy ngược từ $n$ về 1, những vị trí có điểm kết thúc bằng $x$ (tức chính $y = x$) sẽ update cây vị trí đó thành 1 (có thể là trọng tâm $y$). Những vị trí nếu có điểm bắt đầu ($y - len[y] \times 2 + 1$) bằng $x$ thì sau khi xử lý xong $x$, ta sẽ cập nhật lại chúng thành 0 (không thể là trọng tâm $y$ nữa vì $x$ đã vượt ngoài khoảng mà vị trí đó có thể chấp nhận).
Điều đặc biệt ở đây là vì $x$, $y$ phải khác tính chẵn lẻ nên chúng ta sẽ chia thành hai đợt xử lý: một đợt là xử lý trường hợp $x$ lẻ $y$ chẵn và một đợt là xử lý $x$ chẵn $y$ lẻ.
Xét trường hợp những xâu palin kép có độ dài các palin cấu thành là chẵn: vẫn tương tự trường hợp lẻ nhưng ta sẽ thay đổi một chút về trọng tâm. len[x] thay vì là độ dài lớn nhất nếu nhận $x$ làm trọng tâm thì sẽ là độ dài lớn nhất nếu nhận cặp $x - 1$ và $x$ làm trọng tâm.
Độ phức tạp: $O(n \log n)$ (chặt nhị phân trên hash cho mỗi vị trí và các thao tác trên cây Fenwick).
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
string s;
namespace subtask_3 {
int MOD = 1e9 + 7;
int base = 23;
int len[500005];
int hashS[500005];
int hashT[500005];
int fen[500005];
int g[500005];
vector<vector<int>> ps(500005);
void reset(int x){
for(int i = 1; i <= x; i++)
fen[i] = 0;
}
void up(int u, int chg){
int idx = u;
while(idx <= n){
fen[idx] += chg;
idx += idx & (-idx);
}
return;
}
int query(int l, int r){
if(l > r)
return 0;
l--;
r = min(r, n);
int idx = r;
int ans = 0;
while(idx > 0){
ans += fen[idx];
idx -= idx & (-idx);
}
idx = l;
while(idx > 0){
ans -= fen[idx];
idx -= idx & (-idx);
}
return ans;
}
int getHashS(int i, int j){
return (hashS[j] - ((hashS[i - 1] * g[j - i + 1]) % MOD) + MOD) % MOD;
}
int getHashT(int i, int j){
return (hashT[i] - ((hashT[j + 1] * g[j - i + 1]) % MOD) + MOD) % MOD;
}
void pre(int x){
int ans = 0;
for(int i = 1; i <= n; i++){
if(i - x < 1)
continue;
int ps1 = i - x, ps2 = i, res = 0;
if(s[ps1] != s[ps2]){
len[i] = 0;
continue;
}
int l = 0, r = min(ps1 - 1, n - ps2), mid;
while(l <= r){
mid = (l + r) / 2;
if(getHashT(ps1 - mid, ps1) == getHashS(ps2, ps2 + mid)){
l = mid + 1;
res = max(res, mid);
}
else
r = mid - 1;
}
len[i] = res + 1;
}
}
int xuly(int x, int y, int hic){
reset(n);
for(int i = 1; i <= n; i++){
ps[i].clear();
}
for(int i = 1; i <= n; i++){
if(i + hic > n)
continue;
if(i - len[i + hic] * 2 >= 1){
ps[i - len[i + hic] * 2].push_back(i);
}
}
int ans = 0;
for(int i = n; i >= 1; i--){
if(i % 2 == x && i - hic >= 1){
ans += query(i, len[i] * 2 + i - 1);
}
if(i % 2 == y && i + hic <= n){
up(i, 1);
}
for(auto j : ps[i]){
if(j % 2 == y && j + hic <= n){
up(j, -1);
}
}
}
return ans;
}
int cal(int x){
int ans = 0;
ans += xuly(0, 1, 1 ^ x);
ans += xuly(1, 0, 1 ^ x);
return ans;
}
int solve(){
g[0] = 1;
for(int i = 1; i <= n; i++){
g[i] = g[i - 1] * base;
g[i] %= MOD;
}
int ans = 0;
for(int i = 1; i <= n; i++){
hashS[i] = hashS[i - 1] * base + (s[i] - 96);
hashS[i] %= MOD;
}
for(int i = n; i >= 1; i--){
hashT[i] = hashT[i + 1] * base + (s[i] - 96);
hashT[i] %= MOD;
}
pre(0);
ans += cal(1);
pre(1);
ans += cal(0);
return ans;
}
} // namespace subtask_3
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
cin >> s;
s = "#" + s;
cout << subtask_3::solve() << endl;
return 0;
}def solve_subtask3(n, s):
MOD = 10**9 + 7
base = 23
s = "#" + s # 1-based indexing
len_arr = [0] * (n + 5)
hashS = [0] * (n + 5)
hashT = [0] * (n + 5)
fen = [0] * (n + 5)
g = [0] * (n + 5)
ps = [[] for _ in range(n + 5)]
def reset(x):
for i in range(1, x + 1):
fen[i] = 0
def up(u, chg):
idx = u
while idx <= n:
fen[idx] += chg
idx += idx & -idx
def query(l, r):
if l > r:
return 0
l -= 1
r = min(r, n)
idx = r
ans = 0
while idx > 0:
ans += fen[idx]
idx -= idx & -idx
idx = l
while idx > 0:
ans -= fen[idx]
idx -= idx & -idx
return ans
def getHashS(i, j):
return (hashS[j] - (hashS[i - 1] * g[j - i + 1]) % MOD + MOD) % MOD
def getHashT(i, j):
return (hashT[i] - (hashT[j + 1] * g[j - i + 1]) % MOD + MOD) % MOD
def pre(x):
for i in range(1, n + 1):
if i - x < 1:
continue
ps1 = i - x
ps2 = i
res = 0
if s[ps1] != s[ps2]:
len_arr[i] = 0
continue
l, r = 0, min(ps1 - 1, n - ps2)
while l <= r:
mid = (l + r) // 2
if getHashT(ps1 - mid, ps1) == getHashS(ps2, ps2 + mid):
res = max(res, mid)
l = mid + 1
else:
r = mid - 1
len_arr[i] = res + 1
def xuly(x, y, hic):
reset(n)
for i in range(1, n + 1):
ps[i].clear()
for i in range(1, n + 1):
if i + hic > n:
continue
if i - len_arr[i + hic] * 2 >= 1:
ps[i - len_arr[i + hic] * 2].append(i)
ans = 0
for i in range(n, 0, -1):
if i % 2 == x and i - hic >= 1:
ans += query(i, len_arr[i] * 2 + i - 1)
if i % 2 == y and i + hic <= n:
up(i, 1)
for j in ps[i]:
if j % 2 == y and j + hic <= n:
up(j, -1)
return ans
def cal(x):
ans = 0
ans += xuly(0, 1, 1 ^ x)
ans += xuly(1, 0, 1 ^ x)
return ans
# precompute powers
g[0] = 1
for i in range(1, n + 1):
g[i] = (g[i - 1] * base) % MOD
# forward hash
for i in range(1, n + 1):
hashS[i] = (hashS[i - 1] * base + (ord(s[i]) - 96)) % MOD
# backward hash
for i in range(n, 0, -1):
hashT[i] = (hashT[i + 1] * base + (ord(s[i]) - 96)) % MOD
pre(0)
ans = cal(1)
pre(1)
ans += cal(0)
return ans
n = int(input().strip())
s = input().strip()
print(solve_subtask3(n, s))Mình chạy thử: với $n = 500\,000$ bản C++ chạy khoảng 0.3 giây (kể cả chuỗi toàn chữ a với đáp án lên tới 62 500 000 000, nên biến đếm phải dùng long long như code đã #define int long long). Bản Python cùng thuật toán mất khoảng 12 giây với $n = 500\,000$ nên chỉ nên dùng để tham khảo ý tưởng; muốn ăn trọn subtask cuối thì nên nộp bản C++. Ngoài ra, bước 1 cũng có thể thay hash + chặt nhị phân bằng thuật toán Manacher để tìm palin dài nhất tại mọi trọng tâm trong $O(n)$, bạn nào thích có thể tìm hiểu thêm.