Editorial for Pink Green Peacock và tiết học Toán thú vị
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Gọi ~S_k~ là ~ \displaystyle\sum_{i = 1}^n i^k~.
Ta có: ~(n+1)^{k+1} = \displaystyle\sum_{i = 0}^{k+1} C_{k+1}^i * n ^ i~. (Nhị thức Newton)
~ \iff (n+1)^{k+1} - n^{k+1} = \displaystyle\sum_{i = 0}^k C_{k+1}^i * n ^ i~.
Ta lại có: ~\displaystyle\sum_{i = 1}^n [(i+1)^{k+1} - i^{k+1}] = (n+1)^{k+1} - 1 = \displaystyle\sum_{i = 0}^k C_{k+1}^i * S_i~.
~\iff (k+1) * S_k = (n+1)^{k+1} - 1 - (\displaystyle\sum_{i = 0}^{k-1} C_k^i * S_i)~.
Sử dụng công thức trên, ta có thể dễ dàng tính được kết quả trong độ phức tạp ~k^2~ với mỗi truy vấn. Vì phải sử dụng Bignum nên dộ phức tạp là ~k^3 * log n~ với mỗi truy vấn.
Comments