Hướng dẫn giải của Giá trị của xâu
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Tong gia tri cac xau con; gia tri cua xau tinh theo chi so i^2 nhan v (vi tri trong bang chu cai).
Sub 1: Vet can, ~N \le 500~ ~O(N^2)~
Voi moi doan con cong dan gia tri theo dinh nghia. Chay rieng: dung 15/20 test.
Sub 2: Cong thuc, ~N \le 2 \cdot 10^5~ ~O(N)~
Ky tu o vi tri p xuat hien trong (n-p+1) doan con voi chi so 1..p, dong gop v * (n-p+1) * (1^2 + ... + p^2). Chay rieng: dung 20/20 test.
Chương trình hoàn chỉnh
Neu N <= 500 dung sub 1, nguoc lai dung sub 2. Ket qua lay theo modulo 10^9+7.
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;
string t;
// Sub 1: vet can O(N^2), dung khi N <= 500: voi moi doan con, cong dan gia tri theo dinh nghia
void sub1() {
int n = t.size();
long long ans = 0;
for (int l = 0; l < n; l++) {
long long val = 0;
for (int r = l; r < n; r++) {
long long len = r - l + 1; // chi so i cua ky tu t[r] trong doan con
long long v = t[r] - 'a' + 1;
val = (val + len * len % MOD * v) % MOD;
ans = (ans + val) % MOD;
}
}
cout << ans << "\n";
}
// Sub 2: cong thuc O(N): ky tu o vi tri p (1-based) co chi so i = p-l+1 voi l = 1..p, va xuat hien
// trong (n-p+1) doan con. Dong gop: v * (n-p+1) * (1^2 + 2^2 + ... + p^2)
void sub2() {
int n = t.size();
long long ans = 0, S2 = 0;
for (int p = 1; p <= n; p++) {
S2 = (S2 + (long long)p * p) % MOD;
long long v = t[p - 1] - 'a' + 1;
ans = (ans + v * ((n - p + 1) % MOD) % MOD * S2) % MOD;
}
cout << ans << "\n";
}
int main() {
freopen("GIAXAU.INP", "r", stdin);
freopen("GIAXAU.OUT", "w", stdout);
cin >> t;
if (t.size() <= 500) sub1();
else sub2();
return 0;
}
Bình luận