Editorial for Bedao Grand Contest 10 - FGSTRING


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: FireGhost130104 , bedao

Gọi ~f[i]~ là giá trị kì vọng của xâu tạo ra từ ~s[i..n]~.

Dễ thấy, ~f[i] = \frac{1}{n-i+1} \cdot \sum_{j=i}^{n} f[j+1]~ ~+~ (số vị trí ~k~ thỏa mãn ~i \leq k \leq j~ và ~s[i] = s[k]~). Tuy nhiên độ phức tạp của cách làm này là ~O(n^2)~.

Nhận xét: ~\sum_{j=i}^{n}~ (số vị trí ~k~ thỏa mãn ~i \leq k \leq j~ và ~s[i] = s[k]~) = ~\sum_{s_j = s_i}{}(n - j + 1)~. Với nhận xét này, ta có thể cải tiến lời giải lên ~O(n)~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.