$ dp[i][j] を求める i番目までを右端にした時に和がjになる区間の数 最初に自身が左端になる区間の数を設定する時に、$ dp[i][a[i]] = 1 ではなく$ dp[i][a[i]] = i + 1 とすることで左端の選び方の数を織り込むことができる 直前を右端とした区間は自身を右端とした区間でも成り立つので$ dp[i][j] += dp[i-1][j が必要 $…