AtCoder Beginner Contest 159 F.napsack for All Segments

题目链接

Problem Statement

Given are a sequence of $N$ integers $A_1,A_2,\dots ,A_N$ and a positive integer S.
For a pair of integers $(L,R)$ such that $1\le L\le R\le N$, let us define f(L,R) as follows:$f(L,R)$ is the number of sequences of integers $(x_1,x_2,\dots ,x_k)$ such that $L\le x_1<x_2<\cdots <x_k\le R$ and $A_{x_1}+A_{x_2}+\cdots +A{x}_k=S$.
Find the sum of $f(L,R)$ over all pairs of integers $(L,R)$ such that $1\le L\le R\le N$. Since this sum can be enormous, print it modulo 998244353.

Sample Input 1

3 4
2 2 4

Sample Output 1

5

Sample Input 2

5 8
9 9 9 9 9

Sample Output 2

0

Sample Input 3

10 10
3 1 4 1 5 9 2 6 5 3

Sample Output 3

152

DP必死/(ㄒoㄒ)/~~
动态规划是ACM算法里最难的也是最简单的~
这就是一道类似01背包的动态规划，挂上代码就都明白了：

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
const int mod=998244353;
int f[N],n,s,x,ans=0;
int main(){
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        cin>>x;
        for(int j=s-x;j>0;j--) f[j+x]=(f[j+x]+f[j])%mod;
        f[x]=(f[x]+i)%mod;
        ans=(ans+f[s])%mod;
    }
    cout<<ans;
    return 0;
}