专栏文章

题解：AT_abc399_f [ABC399F] Range Power Sum

yyszkddzyh
AT_abc399_f题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miprlzgr
此快照首次捕获于
2025/12/03 16:48
3 个月前
此快照最后确认于
2025/12/03 16:48
3 个月前
查看原文
考虑一种 dp 的思路，令：
si,j=∑l=in(∑o=ilao)js_{i, j} = \sum _ {l = i} ^ {n} \left(\sum _ {o = i} ^ {l} a_o \right) ^ j
显然 ∑i=1nsi,k\sum _ {i = 1} ^ n s_{i, k} 即为答案。
考虑转移，手搓多个实例我们注意到：
si,j=si+1,j+(n−i+1)aij+∑l=1j−1(jl)aij−lsi+1,ls_{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}
上式通过定义略微变形即可证明，读者可以自行尝试。
于是就有了代码。
这种思路是从后往前转移，从前往后是同理的。

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...