鉴于考试情况乐观,就简单讲讲吧

考虑$s_i$为买$i$的价格

$$ a_i=\sum_j s_j\begin{Bmatrix}i\\j\end{Bmatrix}\\ s_i=\sum_j a_j(-1)^{i-j}\begin{bmatrix}i\\j\end{bmatrix} $$

算出斯特林数后暴力算$O(n(r-l))$

由于我们只要知道一行的斯特林数就可以递推算

于是复杂度$O(n(\log n+r-l))$