- Distribution Counting Issues
- Heavy addition at DP confluence. - cumulative sum is obtained in advance.
Rustic solution, this will pass all samples except the last. python
def solve(N, K, XS):
table = [0] * (K + 1)
for i in range(XS[0] + 1):
table[i] = 1
for i in range(1, N):
v = 0
newtable = [0] * (K + 1)
for j in range(K + 1):
v = 0
for k in range(XS[i] + 1):
if j - k < 0:
break
v += table[j - k]
v %= MOD
newtable[j] = v
table = newtable
return table[K]
What’s wrong with simple is the addition loop, so find the cumulative sum in advance. python
def solve(N, K, XS):
table = [0] * (K + 1)
for i in range(XS[0] + 1):
table[i] = 1
for i in range(1, N):
v = 0
newtable = [0] * (K + 1)
accum = [0] * (K + 1)
acc = 0
for j in range(K + 1):
acc += table[j]
accum[j] = acc
for j in range(K + 1):
v = accum[j]
k = j - XS[i] - 1
if k >= 0:
v -= accum[k]
newtable[j] = v % MOD
table = newtable
return table[K]
This page is auto-translated from [/nishio/DP M](https://scrapbox.io/nishio/DP M) using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.