yukicoder : No.1353 Limited Sequence

問題の理解にちょっと手間取った。
https://yukicoder.me/problems/no/1353

問題

N要素の整数列Aと、区間[L,R]が与えられる。
以下を満たす数列Bは何通りか。

• 各要素は1以上N以下の整数
• 総和はL以上R以下
• 同じ値vが連続するとき、連続する回数はA[v]以下

解法

以下を考えよう。
dp(s,e) := 総和がSで末尾がeであるようなBの構成法の組み合わせ

dp(s,e)からは、e以外の値vをA[v]個まで後ろにつなげることができるので、これを総当たりしよう。
その際、末尾にvを加えるケースは、v以外のeに対するdp(s,e)から遷移できるので、累積和を使い計算量を落とす。

int N,L,R;
int A[2020];
ll dp[2020][2020];
const ll mo=998244353;

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

まとめ

こちらも実装軽めの★3。