Atcoder ABC 159

作者: ffacs 分类: Atcoder 发布时间: 2020-04-23 06:51

F

题意

求长度为$n \leq 3000$的序列的每一个子串中和为$s$的子序列个数和.

解法

我们反过来求,对于一个 第一个元素在$j$,最后一个元素在$i$的子序列,那么它做出的贡献就是$j*(n-i+1)$,那么对于所有最后一个元素在$i$的子序列,它们的贡献就是$(n-i+1)\sum\limits_{x=1}\limits^{y}j_x$,那么我们只要维护前缀和即可.

发表评论

电子邮件地址不会被公开。 必填项已用*标注