[AtCoder ABC159F] Knapsack for All Segments

题目链接

Solution

这种题首先肯定是转换视角：假设 $A_i\cdots A_j\cdots A_k$ 是和为 $S$ 的序列，则它对答案的贡献为 $i\cdot(n-k+1)$.

于是对于所有在 $A_k$ 结束的和为 $S$ 的序列：

$$A_{i_1}\cdots A_{j_1}\cdots A_k\\A_{i_2}\cdots A_{j_2}\cdots A_k\\\cdots\\A_{i_r}\cdots A_{j_r}\cdots A_k$$

它们对答案的贡献为 $(i_1+i_2+\cdots+i_r)\cdot(n-k+1)$.

所以我们想枚举结束点 $k$，计算和为 $S$ 且在 $A_k$ 结束的序列的第一个元素的位置之和，即上式第一个括号的值。考虑 $dp$：

• dp 状态：$dp[k][s]$ 表示在 $A_k$ 结束的序列的第一个元素的位置之和。
• 转移方程：$dp[k][s] = \sum\limits_{i=1}^{k-1}dp[i][s-a[k]]$，特别地，$dp[k][a[k]] = k$.
• 转移顺序：由转移方程可知，顺序枚举即可
• 边界条件：无

复杂度：$O(NS)$

Code

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 3005;
const LL MOD = 998244353;

int n;
LL S, a[N], dp[N][N], ans, sum[N][N];

int main(){
    read(n, S);
    for(int i = 1; i <= n; i++) read(a[i]);
    for(int k = 1; k <= n; k++){
        (dp[k][a[k]] += k) %= MOD;
        for(int s = a[k] + 1; s <= S; s++)
            (dp[k][s] += sum[k-1][s-a[k]]) %= MOD;
        for(int s = 0; s <= S; s++)
            sum[k][s] = (sum[k-1][s] + dp[k][s]) % MOD;
    }
    for(int i = 1; i <= n; i++)
        (ans += dp[i][S] * (n - i + 1) % MOD) %= MOD;
    printf("%lld\n", ans);
    return 0;
}