Hướng dẫn cho LQDOJ CUP 2022 - Round 4 - UGPALIND
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Subtask \(1\) (\(20\%\) số điểm): \(|s_1| = |s_2| = \ldots = |s_n| = 1\).
Tutorial
Hai xâu palindrome độ dài \(S\) khác nhau khi và chỉ khi tiền tố độ dài \(\lceil S / 2\rceil\) khác nhau.
Ví dụ aba khác với aca vì ab khác ac.
Để tính số lượng xâu palindrome phân biệt độ dài \(K\) thỏa đề, ta chỉ cần tính số lượng xâu độ dài \(\lceil K / 2\rceil\) (nửa xâu) phân biệt và chứa ít nhất \(1\) trong \(n\) xâu cho trước.
Thay vì tính số lượng xâu \(S\) chứa ít nhất một trong các xâu cho trước, ta sẽ tính số lượng xâu không chứa bất kỳ xâu nào trong \(n\) xâu và trừ \(26^{|S|}\) đi con số này sẽ được kết quả cần tìm.
Ở subtask 1, các xâu chỉ có dạng là các ký tự, gọi \(d\) là số lượng ký tự riêng biệt trong \(n\) ký tự, ta dễ dàng thấy số xâu \(S\) không chứa xâu nào trong \(n\) xâu ban đầu sẽ là \((26 - d)^{|S|}\).
Độ phức tạp: \(\mathcal{O}(\log_2(n))\)
Solution
#include <bits/stdc++.h>
using namespace std;
const int ALPHABET_SIZE = 26;
const long long MOD = 1e9 + 7;
int n, k;
bool yes[ALPHABET_SIZE + 1];
long long binPow(long long a, long long b) {
long long result = 1;
while (b) {
if (b & 1) {
result = result * a % MOD;
}
b >>= 1;
a = a * a % MOD;
}
return result;
}
long long solve(int n) {
return (binPow(26, n) + MOD - binPow(26 - count(yes + 1, yes + ALPHABET_SIZE + 1, true), n)) % MOD;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("UGPALIND.inp", "r", stdin);
freopen("UGPALIND.out", "w", stdout);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
char x;
cin >> x;
yes[x - 'a' + 1] = true;
}
if (k % 2 == 0) {
cout << solve(k / 2);
} else {
cout << solve(k / 2 + 1);
}
return 0;
}
Subtask \(2\) (\(20\%\) số điểm): \(n = 1\) và \(|s_1| = 2\).
Tutorial
Ở subtask 2, ý tưởng cũng đưa về như subtask 1, cố gắng tính số "nửa xâu" không chứa xâu con nào. Gọi xâu đề cho là xy, ta nhận thấy nếu ta tạo một nửa xâu mà có x hoặc y liền kề nhau thì palindrome của chúng ta chắc chắn sẽ chứa xy là xâu con, do đó ta sẽ sử dụng quy hoạch động để tính số lượng xâu mà x và y không nằm liền kề.
Lưu ý trường hợp đặc biệt khi x = y và \(k\) là chẵn. Khi đó ta không được phép điền ký tự đầu tiên là x bởi khi đó palindrome sẽ có xx là xâu con.
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1005;
const int MOD = 1e9 + 7;
const int BASE = 26;
int n, k;
int dp[MAX_N][BASE + 1];
int x, y;
string str;
int solve(int n) {
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
for (int pre = 0; pre <= BASE; pre++) {
if (dp[i][pre]) {
for (int c = 1; c <= BASE; c++) {
if (pre == x && c == y) {
continue;
}
if (pre == y && c == x) {
continue;
}
if (x == y && i == 0 && c == x && k % 2 == 0) {
continue;
}
dp[i + 1][c] = (dp[i + 1][c] + dp[i][pre]) % MOD;
}
}
}
}
int result = 1;
for (int i = 1; i <= n; i++) {
result = 1LL * result * BASE % MOD;
}
for (int pre = 0; pre <= BASE; pre++) {
result = (result + MOD - dp[n][pre]) % MOD;
}
return result;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("UGPALIND.inp", "r", stdin);
freopen("UGPALIND.out", "w", stdout);
cin >> n >> k;
assert(n == 1);
cin >> str;
x = str[0] - 'a' + 1;
y = str[1] - 'a' + 1;
cout << solve((k + 1) / 2);
return 0;
}
Subtask \(3\) (\(20\%\) số điểm): \(n=1\).
Tutorial
Gọi xâu duy nhất đề cho là \(S\). Ta nhận thấy nếu nửa xâu chứa \(S\) hoặc \(\text{rev}(S)\) thì xâu palindrome chắc chắn sẽ chứa \(S\). Do vậy, ta cũng sẽ cần tính số lượng nửa xâu không chứa \(S\) và \(\text{rev}(S)\).
Gọi \(\text{dp}[i][la][lb]\) là số lượng xâu có độ dài \(i\), có hậu tố trùng với tiền tố độ dài \(la\) của \(S\) và trùng với tiền tố độ dài \(lb\) của \(\text{rev}(S)\). Ban đầu \(\text{dp}[0][0[0]=1\). Để chuyển trạng thái, ta sẽ thử điền các ký tự từ a tới z ở vị trí \(i + 1\) và cần tính thử \(la\) và \(lb\) mới sẽ thay đổi như nào. Thao tác tìm \(la\) và \(lb\) mới có thể áp dụng thuật toán KMP để tìm.
Sau khi tính xong mảng \(\text{dp}\), ta sẽ cần trừ \(26^{\lceil K / 2\rceil}\) đi các \(\text{dp}[\lceil K / 2\rceil][la][lb]\). Lưu ý rằng ngoài trường hợp xâu con nằm hoàn toàn trên 1 trong 2 nửa của palindrome thì còn có thể nằm ở cả hai bên. Do đó, ta sẽ chỉ trừ đi những \(\text{dp}[\lceil K / 2\rceil][la][lb]\) nào thỏa mãn nếu nửa xâu này sau khi nhân đôi lên sẽ không xuất hiện xâu \(S\) hay \(\text{rev}(S)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int n, m, k;
vector<vector<vector<int>>> dp;
vector<int> kmpA, kmpB;
vector<vector<int>> nextA, nextB;
vector<bool> okPrefixA, okPrefixB;
string a, b;
void initializeKMP(string s, int n, vector<int> &kmp) {
kmp.resize(n + 1);
kmp[1] = 0;
for (int i = 2; i <= n; i++) {
int j = kmp[i - 1];
while (j > 0 && s[j + 1] != s[i]) {
j = kmp[j];
}
if (s[j + 1] == s[i]) {
j++;
}
kmp[i] = j;
}
}
void findNext(string &s, int n, vector<int> &kmp, vector<vector<int>> &nxt) {
nxt.resize(n + 1, vector<int>(27, 0));
for (int i = 1; i < n; i++) {
for (int c = 1; c <= 26; c++) {
char letter_c = char(c + 96);
int j = kmp[i];
while (j > 0 && s[j + 1] != letter_c) {
j = kmp[j];
}
if (s[j + 1] == letter_c) {
j++;
}
nxt[i][c] = j;
}
}
}
bool checkPrefix(string &s, int n, int a) {
int j = (k % 2 == 0 ? a : a - 1);
for (int i = a + 1; i <= n; i++) {
if (j == 0) {
return false;
}
if (s[i] != s[j]) {
return false;
}
j--;
}
return true;
}
void findOkPrefix(string &s, int n, vector<bool> &ok) {
ok.resize(n + 1);
for (int i = 1; i <= n; i++) {
ok[i] = checkPrefix(s, n, i);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("UGPALIND.inp", "r", stdin);
freopen("UGPALIND.out", "w", stdout);
cin >> n >> k;
int half = (k + 1) / 2;
cin >> a;
m = (int)a.size();
b = a;
reverse(b.begin(), b.end());
a = " " + a;
b = " " + b;
dp.resize(half + 2, vector<vector<int>>(m + 10, vector<int>(m + 10)));
initializeKMP(a, m, kmpA);
initializeKMP(b, m, kmpB);
findNext(a, m, kmpA, nextA);
findNext(b, m, kmpB, nextB);
findOkPrefix(a, m, okPrefixA);
findOkPrefix(b, m, okPrefixB);
dp[0][0][0] = 1;
for (int i = 0; i < half; i++) {
for (int la = 0; la < m; la++) {
for (int lb = 0; lb < m; lb++) {
if (dp[i][la][lb]) {
for (int c = 1; c <= 26; c++) {
char letter_c = char(c + 96);
int next_la = ((a[la + 1] == letter_c) ? la + 1 : nextA[la][c]);
int next_lb = ((b[lb + 1] == letter_c) ? lb + 1 : nextB[lb][c]);
if (next_la < m && next_lb < m) {
dp[i + 1][next_la][next_lb] = (dp[i + 1][next_la][next_lb] + dp[i][la][lb]) % MOD;
}
}
}
}
}
}
int result = 1;
for (int i = 1; i <= half; i++) {
result = 1LL * result * 26 % MOD;
}
for (int la = 0; la < m; la++) {
for (int lb = 0; lb < m; lb++) {
if (!okPrefixA[la] && !okPrefixB[lb]) {
result = (result + MOD - dp[half][la][lb]) % MOD;
}
}
}
cout << result;
return 0;
}
Thuật toán trên sẽ cho độ phức tạp là \(\mathcal{O}(K \times |S|^2 \times 26)\), nhưng như vậy là chưa đủ với \(K, |S| \leq 1000\).
Ta sẽ cần có nhận xét rằng, giữa \(la\) và \(lb\) thì ta chỉ cần quan tâm cái lớn hơn mà thôi, vì chỉ cần có thông tin của đoạn dài nhất thì ta cũng sẽ có thông tin của đoạn còn lại. Do đó ta sẽ gọi \(\text{dp}[i][l][type]\) là số lượng xâu độ dài \(i\) có hậu tố trùng với tiền tố độ dài \(l\) của \(S\) nếu \(type= 0\) và \(\text{rev}(S)\) nếu \(type = 1\). Để chuyển trạng thái, ta sẽ cần tiền xử lý một mảng \(\text{next}[i][j][l][c]\) là độ dài tiền tố mới của xâu có \(type = j\) nếu thêm ký tự \(c\) ngay sau tiền tố độ dài \(l\) của xâu có \(type = i\) bằng cách sử dụng KMP tương tự như đã nêu ở trên.
Độ phức tạp: \(\mathcal{O}((K + S) \times |S| \times 26)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int n, m, k;
string str[2];
vector<vector<vector<int>>> dp;
vector<vector<int>> nxt[2][2];
vector<vector<bool>> isPalindrome[2];
void checkPalindrome(string s, int n, vector<vector<bool>> &isPalindrome) {
isPalindrome.resize(n + 1, vector<bool>(n + 1));
for (int i = 1; i <= n; i++) {
isPalindrome[i][i] = true;
}
for (int i = 1; i < n; i++) {
if (s[i] == s[i + 1]) isPalindrome[i][i + 1] = true;
}
for (int length = 3; length <= n; length++) {
for (int i = 1; i <= n - length + 1; i++) {
int j = i + length - 1;
isPalindrome[i][j] = (s[i] == s[j] && isPalindrome[i + 1][j - 1]);
}
}
}
void findNext(string a, string b, int m, vector<vector<int>> &nxt) {
string s = b + a;
n = m * 2 + 1;
nxt.resize(m + 10, vector<int>(27, 0));
vector<int> kmp(n + 1);
kmp[1] = 0;
for (int i = 2; i <= n; i++) {
int j = kmp[i - 1];
while (j > 0 && s[j + 1] != s[i]) {
j = kmp[j];
}
if (s[j + 1] == s[i]) {
j++;
}
kmp[i] = j;
}
for (int i = m + 1; i <= n; i++) {
for (int c = 1; c <= 26; c++) {
char letter_c = char(c + 96);
int j = kmp[i];
while (j > 0 && s[j + 1] != letter_c) {
j = kmp[j];
}
if (s[j + 1] == letter_c) {
j++;
}
nxt[i - m - 1][c] = j;
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("UGPALIND.inp", "r", stdin);
freopen("UGPALIND.out", "w", stdout);
cin >> n >> k;
int half = (k + 1) / 2;
cin >> str[0];
m = (int)str[0].size();
str[1] = str[0];
reverse(str[1].begin(), str[1].end());
for (int i = 0; i <= 1; i++) {
str[i] = " " + str[i];
}
dp.resize(half + 2, vector<vector<int>>(m + 10, vector<int>(2)));
for (int start = 0; start <= 1; start++) {
checkPalindrome(str[start], m, isPalindrome[start]);
}
for (int start = 0; start <= 1; start++) {
for (int finish = 0; finish <= 1; finish++) {
findNext(str[start], str[finish], m, nxt[start][finish]);
}
}
dp[0][0][0] = 1;
for (int i = 0; i < half; i++) {
for (int l = 0; l < m; l++) {
for (int start = 0; start <= 1; start++) {
if (dp[i][l][start]) {
for (int c = 1; c <= 26; c++) {
int nextL = -1, nextStart = -1;
bool flag = true;
for (int finish = 0; finish <= 1; finish++) {
int hereL = nxt[start][finish][l][c];
if (nextL < hereL) {
nextL = hereL;
nextStart = finish;
}
if (hereL == m) {
flag = false;
break;
}
if (i == half - 1) {
int remain = m - hereL;
int trai = (k % 2 == 1) ? hereL - remain : hereL - remain + 1;
if (trai < 1) continue;
if (isPalindrome[finish][trai][m]) {
flag = false;
break;
}
}
}
if (flag) {
dp[i + 1][nextL][nextStart] = (dp[i + 1][nextL][nextStart] + dp[i][l][start]) % MOD;
}
}
}
}
}
}
int result = 1;
for (int i = 1; i <= half; i++) {
result = 1LL * result * 26 % MOD;
}
for (int l = 0; l < m; l++) {
for (int start = 0; start <= 1; start++) {
result = (result + MOD - dp[half][l][start]) % MOD;
}
}
cout << result;
return 0;
}
Subtask \(4\) (\(20\%\) số điểm): \(|s_i| \leq 20 \ \forall i \in [1, n]\).
Tutorial
Ở subtask 4, ta sẽ cần tính số lượng xâu độ dài \(\lceil K / 2\rceil\) không chứa xâu \(S_i\) và \(\text{rev}(S_i)\) nào. Như vậy ta sẽ có \(2K\) xâu tổng cộng.
Áp dụng ý tưởng chỉ quan tâm xâu nào có tiền tố dài nhất trùng với hậu tố của xâu đang xây dựng, ta có thể có mảng \(\text{dp}[i][l][k]\) số lượng xâu độ dài \(i\) có hậu tố trùng với tiền tố độ dài \(l\) của xâu thứ \(k\) và mảng \(\text{next}[i][j][l][c]\) có định nghĩa tương tự như subtask 3. Để tiết kiệm bộ nhớ, ta sẽ thay thế mảng \(\text{next}[i][j][l][c]\) bên trên thành mảng pair \(\text{next}[i][l][c]\) lưu \(j\) và độ dài tiền tố mới tương ứng.
Độ phức tạp: \(\mathcal{O}(K^2 \times |S|^2 \times 26)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2005;
const int MOD = 1e9 + 7;
int n, k;
int dp[MAX_N][MAX_N][21];
pair<int, int> nxt[MAX_N][21][27];
bool isPalindrome[MAX_N][21][21], ok_l[MAX_N][MAX_N][27], ok_palin[MAX_N][MAX_N][27];
string a[MAX_N];
void checkPalindrome(int x) {
string &s = a[x];
int n = (int)s.size() - 1;
for (int i = 1; i <= n; i++) {
isPalindrome[x][i][i] = true;
}
for (int i = 1; i < n; i++) {
if (s[i] == s[i + 1]) {
isPalindrome[x][i][i + 1] = true;
}
}
for (int length = 3; length <= n; length++) {
for (int i = 1; i <= n - length + 1; i++) {
int j = i + length - 1;
isPalindrome[x][i][j] = (s[i] == s[j] && isPalindrome[x][i + 1][j - 1]);
}
}
}
void findNext(int x, int y) {
string &sa = a[x], &sb = a[y];
int ma = (int)sa.size() - 1, mb = (int)sb.size() - 1;
string s = sb + sa;
int n = ma + mb + 1;
vector<int> kmp(n + 1);
kmp[1] = 0;
for (int i = 2; i <= n; i++) {
int j = kmp[i - 1];
while (j > 0 && s[j + 1] != s[i]) {
j = kmp[j];
}
if (s[j + 1] == s[i]) {
j++;
}
kmp[i] = j;
}
for (int i = mb + 1; i <= n; i++) {
for (int c = 1; c <= 26; c++) {
char letter_c = char(c + 96);
int j = kmp[i];
while (j > 0 && s[j + 1] != letter_c) {
j = kmp[j];
}
if (s[j + 1] == letter_c) {
j++;
}
nxt[x][i - mb - 1][c] = max(nxt[x][i - mb - 1][c], pair<int, int>(j, y));
int remain = mb - j;
int trai = (k % 2 == 1) ? j - remain : j - remain + 1;
if (trai < 1) continue;
if (isPalindrome[y][trai][mb]) {
ok_palin[x][i - mb - 1][c] = false;
}
if (j == mb) {
ok_l[x][i - mb - 1][c] = false;
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("UGPALIND.inp", "r", stdin);
freopen("UGPALIND.out", "w", stdout);
cin >> n >> k;
int half = (k + 1) / 2;
for (int i = 0; i < n; i++) {
cin >> a[i * 2];
assert((int)a[i * 2].size() <= 20);
a[i * 2 + 1] = a[i * 2];
reverse(a[i * 2 + 1].begin(), a[i * 2 + 1].end());
}
for (int i = 0; i < 2 * n; i++) {
a[i] = " " + a[i];
}
for (int start = 0; start < 2 * n; start++) {
for (int l = 0; l < (int)a[start].size(); l++) {
for (int c = 1; c <= 26; c++) {
ok_palin[start][l][c] = true;
ok_l[start][l][c] = true;
}
}
}
for (int start = 0; start < 2 * n; start++) {
checkPalindrome(start);
}
for (int start = 0; start < 2 * n; start++) {
for (int finish = 0; finish < 2 * n; finish++) {
findNext(start, finish);
}
}
dp[0][0][0] = 1;
for (int i = 0; i < half; i++) {
for (int start = 0; start < 2 * n; start++) {
for (int l = 0; l < (int)a[start].size() - 1; l++) {
if (dp[i][start][l]) {
for (int c = 1; c <= 26; c++) {
int nxt_l = nxt[start][l][c].first, nxt_start = nxt[start][l][c].second;
if (!ok_l[start][l][c] || (!ok_palin[start][l][c] && i == half - 1)) {
continue;
}
dp[i + 1][nxt_start][nxt_l] = (dp[i + 1][nxt_start][nxt_l] + dp[i][start][l]) % MOD;
}
}
}
}
}
int result = 1;
for (int i = 1; i <= half; i++) {
result = 1LL * result * 26 % MOD;
}
for (int start = 0; start < 2 * n; start++) {
for (int l = 0; l < (int)a[start].size() - 1; l++) {
result = (result + MOD - dp[half][start][l]) % MOD;
}
}
cout << result;
return 0;
}
Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.
Tutorial
Đầu tiên, ta sẽ build Aho Corasick với việc gọi \(\text{go}[node][c]\) là trả về \(node\) sâu nhất trùng với hậu tố của node hiện tại + kí tự \(c\). Gọi \(\text{dp}[i][node]\) là xây dựng xâu độ dài \(i\) và hậu tố trùng với \(node\) trên cây Trie Aho Corasick. Ta có công thức quy hoạch động tương tự là \(\text{dp}[i+1][go[node,c]] += \text{dp}[i][node]\). Chi tiết cài đặt có thể tham khảo code sau.
Độ phức tạp: \(\mathcal{O}(K \times |S| \times 26)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 2005;
const int MAXC = 26;
int trie[MAXN][MAXC], link[MAXN], go[MAXN][MAXC];
int cur, n, m, dp[2][MAXN];
bool terminal[MAXN];
pair<int, int> par[MAXN];
void push(string s) {
int p = 0;
for (char c : s) {
int tmp = c - 'a';
if (trie[p][tmp] == 0) trie[p][tmp] = ++cur;
par[trie[p][tmp]] = pair<int, int>(p, tmp);
p = trie[p][tmp];
}
terminal[p] = 1;
}
void build_aho() {
queue<int> bfs;
bfs.push(0);
link[0] = 0;
while (bfs.size()) {
int u = bfs.front();
bfs.pop();
if (terminal[link[u]]) terminal[u] = 1;
for (int c = 0; c < MAXC; ++c) {
go[u][c] = go[link[u]][c];
if (trie[u][c]) {
link[trie[u][c]] = go[u][c];
go[u][c] = trie[u][c];
bfs.push(trie[u][c]);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("UGPALIND.inp", "r", stdin);
freopen("UGPALIND.out", "w", stdout);
cin >> n >> m;
cur = 0;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
push(s);
reverse(s.begin(), s.end());
push(s);
}
build_aho();
dp[0][0] = 1;
for (int i = 0; i < (m + 1) / 2; i++) {
bool type = i & 1;
for (int j = 0; j <= cur; ++j) {
dp[type ^ 1][j] = 0;
}
for (int j = 0; j <= cur; ++j) {
for (int c = 0; c < MAXC; ++c) {
int k = go[j][c];
if (terminal[k]) {
continue;
}
dp[type ^ 1][k] = (dp[type ^ 1][k] + dp[type][j]) % MOD;
}
}
}
int answer = 1;
for (int i = 1; i <= (m + 1) / 2; i++) {
answer = 1ll * answer * MAXC % MOD;
}
for (int i = 0; i <= cur; i++) {
if (!terminal[i]) {
int p = i;
deque<int> path;
while (p > 0) {
path.emplace_back(par[p].second);
p = par[p].first;
}
if (m & 1) {
if (path.size()) {
path.pop_front();
}
}
while ((int)path.size() > m / 2) {
path.pop_back();
}
bool isPalindrome = 0;
p = i;
for (int c : path) {
p = go[p][c];
if (terminal[p]) {
isPalindrome = 1;
break;
}
}
if (!isPalindrome) {
answer = (answer + MOD - dp[((m + 1) >> 1) & 1][i]) % MOD;
}
}
}
cout << (answer + MOD) % MOD << '\n';
return 0;
}
Bình luận