Editorial for Bedao Regular Contest 13 - EVAL


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.

Author: bedao

Nhận xét: giá trị kì vọng của hàm call(a, b)call(c, d) sẽ bằng nhau nếu ~b - a = d - c~.

Gọi ~f[i]~ là giá trị kì vọng của hàm call(l, r) với ~r - l + 1 = i~. Ta có công thức quy hoạch động sau:

~f[i] = (1 + f[i]) + \sum \limits_{j = 1}^{i - 2} (1 + f[j] + f[i - j - 1]) + (1 + f[i])~

~\Rightarrow f[i] = i + 2 \cdot f[i] + \sum \limits_{j = 1}^{i - 2} (f[j] + f[i - j - 1])~

~\Rightarrow (i - 2) \cdot f[i] = i + \sum \limits_{j = 1}^{i - 2} (f[j] + f[i - j - 1])~

~\Rightarrow f[i] = \dfrac{i + \sum \limits_{j = 1}^{i - 2} (f[j] + f[i - j - 1])}{i - 2}~

Để tính nhanh ~\sum \limits_{j = 1}^{i - 2} (f[j] + f[i - j - 1])~, ta có thể sử dụng prefix sum (tổng tiền tố).

Độ phức tạp: ~O(n)~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.