AtCoder ABC #159 : F - Knapsack for All Segments

Eより実装がラク。
https://atcoder.jp/contests/abc159/tasks/abc159_f

問題

整数列Aが与えられる。
Aの部分列のうち、区間[L,R]を制限したとき、A[L...R]の部分列で和がSとできるような組み合わせを考える。
[L,R]全通りにおける前述の和を求めよ。

解法

f(i,k) := i番目までのprefixで部分列で総和がkとなるものの組み合わせ。ただし最初に取った要素がj番目ならj+1倍カウントする
とする。あとはf(i,S)を各iについて求めていけばよい。
また、f(i-1,0)→f(i,A[i])のように初めて0から遷移する場合、i+1通りと考える(この要素を含む区間の先頭は(i+1)通りあるので)。

int N,S;
int A[3030];
const ll mo=998244353;
ll dp[3030];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	dp[0]=0;
	ll ret=0;
	FOR(i,N) {
		cin>>x;
		for(j=S-x;j>=0;j--) {
			if(j==0) (dp[x]+=i+1)%=mo;
			else (dp[x+j]+=dp[j])%=mo;
		}
		ret+=dp[S];
	}
	cout<<ret%mo<<endl;
}

まとめ

参加が遅かったので、終わったら解こうと思ったけど間に合ってしまった。