Trọng Số Của Xâu
Đề bài
Trọng số của một xâu $s$ chỉ gồm các chữ cái trong bảng chữ cái tiếng Anh được tính bằng tổng các giá trị $i^2 \times v_{s_i}$ với $1 \le i \le |s|$, trong đó $|s|$ là độ dài xâu $s$, $s_i$ là ký tự thứ $i$ của xâu $s$, $v_{s_i}$ là vị trí của ký tự $s_i$ trong bảng chữ cái.
Ví dụ, trọng số của xâu $s =$ abca sẽ được tính như sau: Với $i = 1$, ta có $1^2 \times v_{s_1} = 1^2 \times 1 = 1$. Với $i = 2$, ta có $2^2 \times v_{s_2} = 2^2 \times 2 = 8$. Với $i = 3$, ta có $3^2 \times v_{s_3} = 3^2 \times 3 = 27$. Với $i = 4$, ta có $4^2 \times v_{s_4} = 4^2 \times 1 = 16$. Vậy trọng số của xâu $s$ bằng $1 + 8 + 27 + 16 = 52$.
Một xâu con liên tiếp của xâu $t$ là xâu $t$ khi xóa đi một số ký tự đầu và cuối (có thể không xóa ký tự nào), và giữ nguyên thứ tự của các ký tự còn lại. Ví dụ ab, bdc, abdc hay b là xâu con liên tiếp của abdc nhưng acd hay abc thì không.
Tính tổng trọng số của tất cả các xâu con liên tiếp của xâu $t$.
Input: Một dòng duy nhất gồm xâu $t$ có độ dài không quá $2 \times 10^5$.
Output: Một dòng duy nhất là trọng số của xâu $t$. Vì kết quả có thể rất lớn nên bạn chỉ cần in ra trọng số sau khi đã chia lấy dư cho $10^9 + 7$.
Subtasks:
- Subtask 1 ($30\%$): Độ dài xâu $t$ không vượt quá $200$.
- Subtask 2 ($35\%$): Độ dài xâu $t$ không vượt quá $2000$.
- Subtask 3 ($35\%$): Độ dài xâu $t$ không vượt quá $2 \times 10^5$.
abc65Note:
- Các xâu
a,b,ccó trọng số lần lượt là $1, 2, 3$. - Các xâu
ab,bccó trọng số lần lượt là $9, 14$. - Xâu
abccó trọng số là $36$.
Vậy tổng trọng số của các xâu con của xâu abc là $65$.
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 😇. Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé, các bạn nào 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:
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 CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Tóm tắtHiểu đề cho thật đơn giản
Trướ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: cho 1 xâu $s$ gồm các chữ cái in thường có độ dài $1 \le |s| \le 2 \cdot 10^5$ ($|s|$ chính là độ dài của xâu $s$ nha anh em). Có 2 điều mà bạn cần nắm:
- 1 xâu con liên tiếp của $s$ là 1 đoạn liên tiếp nằm trong $s$ ($s$ cũng là xâu con liên tiếp của chính nó). Ví dụ $s =$
abcdthìabc,a,cd,abcdlà xâu con của $s$, cònacd,bdthì không. - Trọng số của 1 xâu được tính bằng tổng các giá trị $i^2 \times V_{s[i]}$, trong đó $1 \le i \le |s|$, $V_{s[i]}$ là vị trí của ký tự $s[i]$ trong bảng chữ cái. Ví dụ xâu
abdcó trọng số $= 1^2 \cdot 1 + 2^2 \cdot 2 + 3^2 \cdot 4 = 45$.
Hãy tính tổng trọng số của tất cả các xâu con liên tiếp của xâu $s$ (vì kết quả sẽ rất lớn nên hãy chia dư cho $10^9 + 7$). Ví dụ $s =$ abc:
| Xâu con | Cách tính | Trọng số |
|---|---|---|
a | 1²·1 | 1 |
ab | 1²·1 + 2²·2 | 9 |
abc | 1²·1 + 2²·2 + 3²·3 | 36 |
b | 1²·2 | 2 |
bc | 1²·2 + 2²·3 | 14 |
c | 1²·3 | 3 |
| Tổng trọng số | 65 | |
Bài này có 3 subtask nha anh em. Mình sẽ hướng dẫn anh em làm từng cái 1.
Subtask 1|s| ≤ 200: làm y như đề bảo – O(|s|³)
Với subtask đầu thì ta sẽ code theo y như cách đề bài bảo thôi. Ta sẽ xét mọi xâu con của $s$ (bắt đầu tại $i$, kết thúc tại $j$), tính trọng số của xâu con đó bằng 1 vòng lặp $k$ rồi cộng vào biến kết quả là được.
Source code cho cách làm trên mình để đây cho anh em cần thì tham khảo nhé:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll mod = (int)1e9 + 7;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
ll n = (ll)s.length(), res = 0;
for(ll i = 0; i < n; ++i) {
for(int j = i; j < n; ++j) {
ll sum = 0;
for(int k = i; k <= j; ++k) {
ll stt = k - i + 1;
sum += stt * stt * ((int)s[k] - (int)'a' + 1);
sum %= mod;
}
res += sum;
res %= mod;
}
}
cout << res;
return 0;
}mod = 10**9 + 7
s = input().strip()
n = len(s)
res = 0
for i in range(n):
for j in range(i, n):
summ = 0
for k in range(i, j + 1):
stt = k - i + 1
summ += stt * stt * (ord(s[k]) - ord('a') + 1)
summ %= mod
res += summ
res %= mod
print(res)Giải thích 1 số chỗ trong cách làm ở 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 cần nhập xuất nhiều dữ liệu thì ta hãy nên để 2 dòng này vào để chạy nhanh hơn. 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é.ll stt = k - i + 1: ở đây ta đang lấy các phần tử xâu con bắt đầu từ $i$ tới $j$, $k - i + 1$ chính là số thứ tự của chữ cái ta đang xét trong xâu con chạy từ $i$ tới $j$ (sttlà viết tắt của số thứ tự đó).((int)s[k] - (int)'a' + 1)chính bằng số thứ tự của chữ cái in thường trong bảng chữ cái.- Các phần như
sum %= modhayres %= modchính là ta đang áp dụng đồng dư thức. Dành cho bạn nào chưa biết thì $(a + b) \bmod m$ $= ((a \bmod m) + (b \bmod m)) \bmod m$ và $(a \cdot b) \bmod m$ $= ((a \bmod m) \cdot (b \bmod m)) \bmod m$. Chính vì vậy, thay vì đợi cộng xong hết mới chia dư (chắc chắn sẽ bị tràn số), ta chia dư mỗi khi cập nhật các biến nhưsumvàres.
Dễ dàng thấy là cách trên không thể chạy được full bài này. Tuy nhiên hãy vẫn nên cài đặt nó để sau này ta lấy nó làm công cụ kiểm tra tính chính xác cho cách làm tối ưu.
Subtask 2|s| ≤ 2000: tận dụng trọng số xâu con trước – O(|s|²)
Ta tiến tiếp tới subtask tiếp theo nào. Khi ta làm cách vét cạn ta sẽ thấy được cái không tối ưu của nó, từ đó ta sẽ tối ưu lên. Ở cách trên chỗ chưa tối ưu chính là vòng lặp thứ 3.
Ví dụ $s =$ abcd, ta xét xâu con ab và tính trọng số của nó bằng $1^2 \cdot 1 + 2^2 \cdot 2 = 9$. Rồi ta xét xâu con abc, lại tính $1^2 \cdot 1 + 2^2 \cdot 2 + 3^2 \cdot 3 = 36$, tiếp tới xâu con abcd: $1^2 \cdot 1 + 2^2 \cdot 2 + 3^2 \cdot 3 + 4^2 \cdot 4$ $= 100$. Ta sẽ thấy rằng khi từ ab sang abc ta đều đi tính lại trọng số từ đầu, khiến mất thời gian.
Xâu con abc chính là xâu con ab thêm chữ cái c vào cuối, nên trọng số của nó = trọng số của ab + (số thứ tự mà c được thêm vào)$^2 \times$ (số thứ tự của c trong bảng chữ cái) $= 9 + 3^2 \cdot 3 = 36$. Tương tự trọng số của abcd $= 36 + 4^2 \cdot 4 = 100$. Từ đó ta sẽ lưu kết quả trọng số của xâu con trước đó để tính nhanh hơn.
Bây giờ dưới vòng lặp $i$ ta sẽ sử dụng một biến tmp có tác dụng lưu trọng số của xâu con bắt đầu từ $i$ tới $j - 1$, thì khi xét xâu con bắt đầu từ $i$ tới $j$ ta chỉ việc lấy tmp + (số thứ tự mà chữ cái $s[j]$ được thêm vào)$^2 \times$ (số thứ tự của chữ cái $s[j]$ trong bảng chữ cái).
Source code cho cách làm trên mình để đây cho anh em cần thì tham khảo nhé:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll mod = (int)1e9 + 7;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
ll n = (ll)s.length(), res = 0;
for(ll i = 0; i < n; ++i) {
ll tmp = 0;
for(int j = i; j < n; ++j) {
ll stt = j - i + 1;
tmp += stt * stt * ((int)s[j] - (int)'a' + 1);
tmp %= mod;
res += tmp;
res %= mod;
}
}
cout << res;
return 0;
}mod = 10**9 + 7
s = input().strip()
n = len(s)
res = 0
for i in range(n):
tmp = 0
for j in range(i, n):
stt = j - i + 1
tmp += stt * stt * (ord(s[j]) - ord('a') + 1)
tmp %= mod
res += tmp
res %= mod
print(res)Giải thích 1 số chỗ trong cách làm ở trên:
tmp = 0, vì lúc đó chưa có xâu con nào bắt đầu tại vị trí thứ $i$ cả nên ta sẽ gántmp = 0đầu tiên.stt = j - i + 1chính là số thứ tự mà chữ cái $s[j]$ được thêm vào.
Với cách này khi bạn submit thì đã ăn được 65% bài này đổ lên rồi. Giờ chúng ta sẽ sang cách để AC full bài này.
Subtask 3|s| ≤ 2·10⁵: rút ra công thức
Vì cách này sẽ dùng toán và sẽ khá dài dòng nên để có thể hiểu và nghĩ ra được dễ dàng hơn thì các bạn nên lấy nháp ra và nháp, chỉ 1 lúc thôi các bạn sẽ nhìn ra được quy luật và sẽ AC được bài này thôi. Nếu vẫn không được thì giờ mình sẽ lấy ví dụ cho bạn xem và ta sẽ rút ra được cách AC bài này.
Ví dụ $s =$ abcd. Ta gọi số thứ tự của a trong bảng chữ cái là $V_a$, của b là $V_b$ và cứ thế trong bảng chữ cái.
- Các xâu con bắt đầu từ vị trí đầu tiên là
a,ab,abc,abcd, trọng số lần lượt là $1^2 V_a$; $1^2 V_a + 2^2 V_b$; $1^2 V_a + 2^2 V_b + 3^2 V_c$; $1^2 V_a + 2^2 V_b + 3^2 V_c + 4^2 V_d$. Tổng của chúng $= 4 \cdot 1^2 V_a + 3 \cdot 2^2 V_b$ $+ 2 \cdot 3^2 V_c + 1 \cdot 4^2 V_d$ — ta đánh dấu là kết quả (1). - Các xâu con bắt đầu từ vị trí thứ 2 là
b,bc,bcd, trọng số $1^2 V_b$; $1^2 V_b + 2^2 V_c$; $1^2 V_b + 2^2 V_c + 3^2 V_d$. Tổng $= 3 \cdot 1^2 V_b + 2 \cdot 2^2 V_c + 1 \cdot 3^2 V_d$ — kết quả (2). - Tương tự tổng trọng số các xâu con bắt đầu từ vị trí thứ 3 $= 2 \cdot 1^2 V_c + 1 \cdot 2^2 V_d$ — kết quả (3).
- Và bắt đầu từ vị trí thứ 4 $= 1 \cdot 1^2 V_d$ — kết quả (4).
Tổng trọng số của tất cả xâu con của $s$ đương nhiên bằng (1) + (2) + (3) + (4). Ta nhóm theo từng chữ cái và đảo chỗ ta sẽ được:
+ 3·Vb·(1² + 2²)
+ 2·Vc·(1² + 2² + 3²)
+ 1·Vd·(1² + 2² + 3² + 4²)
Bảng dưới đây gom đúng các số hạng đó lại: mỗi hàng là 1 kết quả (1), (2), (3), (4), mỗi cột là 1 chữ cái; cộng theo cột là ra từng dòng của công thức trên:
| bắt đầu tại | a (Va) | b (Vb) | c (Vc) | d (Vd) |
|---|---|---|---|---|
| vị trí 1 (a…) | 4·1² | 3·2² | 2·3² | 1·4² |
| vị trí 2 (b…) | – | 3·1² | 2·2² | 1·3² |
| vị trí 3 (c…) | – | – | 2·1² | 1·2² |
| vị trí 4 (d…) | – | – | – | 1·1² |
| Cộng cột | 4·(1²) | 3·(1² + 2²) | 2·(1² + 2² + 3²) | 1·(1² + 2² + 3² + 4²) |
Lúc này nếu anh em vẫn chưa nhìn ra quy luật thì có thể thử làm như cách trên với xâu abc, nó sẽ ra: $3 V_a (1^2) + 2 V_b (1^2 + 2^2)$ $+ 1 \cdot V_c (1^2 + 2^2 + 3^2)$. Thay $V_a = 1, V_b = 2, V_c = 3$ thì kết quả là $3 + 20 + 42 = 65$ ✔.
Vậy anh em nhìn ra quy luật rồi chứ. Lúc này ta có thể rút ra công thức tính tổng trọng số của tất cả các xâu con của xâu $s$:
Anh em thấy sự kì diệu của toán học rồi chứ 😘. Nếu để ý nhìn kĩ lại xâu thì thấy công thức trên là hoàn toàn hợp lý. Xét xâu abcd, nhìn vào vị trí thứ 2 tức là chữ b: các xâu con ab, abc, abcd đều chứa b ở vị trí thứ 2 — có 3 xâu như vậy vì từ chữ b đến cuối tính cả bản thân nó là có 3 chữ. Cứ vậy, khi xét các xâu con bắt đầu từ vị trí thứ 2 thì b đứng ở vị trí thứ 1 và vẫn chỉ có 3 xâu con chứa nó. Tổng lại, b đóng góp $3 \cdot V_b \cdot (2^2 + 1^2)$.
Em nhập 1 xâu rồi bấm Tiếp để xem từng chữ cái đóng góp bao nhiêu vào kết quả:
Code ACTổng bình phương bằng quy hoạch động – O(|s|)
Giờ bắt tay vào code thì anh em lưu ý nhé, mà code 1 vòng for bên trong để tính $1^2 + 2^2 + \cdots + i^2$ thì độ phức tạp thời gian vẫn là $O(|s|^2)$, chưa AC được đâu. Đến đoạn này thì anh em nào biết công thức $1^2 + 2^2 + \cdots + n^2$ $= \dfrac{n(n + 1)(2n + 1)}{6}$ thì có thể áp dụng, nhưng mình sẽ chỉ anh em một cách dễ hơn, đó chính là dùng quy hoạch động như số Fibonacci đó: gọi $F[i]$ là tổng $1^2 + 2^2 + \cdots + i^2$ thì ta dễ dàng có công thức truy hồi
Vậy là trong quá trình tính ta luôn luôn cập nhật $F[i]$, độ phức tạp đã về $O(|s|)$ rồi. Đây là source code của mình về cách làm trên cho bạn nào muố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;
const ll nMax = 2 * (int)1e5 + 5;
ll f[nMax];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
ll n = (ll)s.length(), res = 0;
f[0] = 0;
for(ll i = 1; i <= n; ++i) {
f[i] = (f[i - 1] + i * i) % mod;
res += (n - i + 1) * ((int)s[i - 1] - (int)'a' + 1) * f[i];
res %= mod;
}
cout << res;
return 0;
}mod = 10**9 + 7
nMax = 2 * 10**5 + 5
f = [0] * (nMax)
s = input().strip()
n = len(s)
res = 0
f[0] = 0
for i in range(1, n + 1):
f[i] = (f[i - 1] + i * i) % mod
res += (n - i + 1) * (ord(s[i - 1]) - ord('a') + 1) * f[i]
res %= mod
print(res)Giải thích 1 số chỗ trong cách làm ở trên:
f[i] = (f[i - 1] + i * i) % mod: anh em nhớ phải% modvì nếu không tí nhân vào sẽ gây ra tràn số.(n - i + 1) * ((int)s[i - 1] - (int)'a' + 1) * f[i]: ở đây $(n - i + 1) = (|s| - i + 1)$,((int)s[i - 1] - (int)'a' + 1)chính là thứ tự của chữ thứ $i$ trong bảng chữ cái (xâu C++ đánh số từ 0 nên làs[i - 1]),f[i]chính là tổng $1^2 + 2^2 + \cdots + i^2$. Đó chính là công thức nha anh em. Tích này lớn nhất cỡ $2 \cdot 10^5 \cdot 26 \cdot 10^9 \approx 5 \cdot 10^{15}$, vẫn nằm gọn tronglong long.
Vậy nếu ta rút xuống độ phức tạp này thì chắc chắn ta sẽ AC bài này rồi. Ta đã đi qua 3 subtask và rút gọn độ phức tạp xuống rất nhiều. Để anh em dễ tưởng tượng thì với cách làm ban đầu, khi vào trường hợp to nhất là $|s| = 2 \cdot 10^5$ thì sẽ mất tận $(2 \cdot 10^5)^3 / 10^8$ giây, xấp xỉ 2 năm rưỡi để ra được kết quả đó 😂. Còn với cách cuối cùng thì ta chỉ mất tầm 0.002 giây thôi nha hehe.
z) so với cách tính trực tiếp theo định nghĩa: tất cả các bản đều khớp 100%. Thời gian trên máy mình: Cách 3 với $|s| = 2 \cdot 10^5$ chạy khoảng 0.004 giây (C++) và 0.1 giây (Python); Cách 2 với $|s| = 2000$ khoảng 0.01 giây, nhưng với $|s| = 2 \cdot 10^5$ thì chạy hơn 2 phút vẫn chưa xong, đúng như dự đoán.
Nhận xét
Đăng nhận xét