题解：AT_abc399_f [ABC399F] Range Power Sum

· · 题解

考虑一种 dp 的思路，令：

s_{i, j} = \sum _ {l = i} ^ {n} \left(\sum _ {o = i} ^ {l} a_o \right) ^ j

显然 \sum _ {i = 1} ^ n s_{i, k} 即为答案。

考虑转移，手搓多个实例我们注意到：

s_{i, j} = s_{i + 1, j} + (n - i + 1)a _ i ^ j + \sum _ {l = 1} ^ {j - 1} \binom{j}{l} a _ i ^ {j - l} s _ {i + 1, l}

上式通过定义略微变形即可证明，读者可以自行尝试。

于是就有了代码。

这种思路是从后往前转移，从前往后是同理的。