DP M - NISHIO Hirokazu's Scrapbox (Auto-translated from Japanese)

DP M

M - Candies

https://gyazo.com/7f00d3569b97262049eab2547f73d1ad

Distribution Counting Issues

Heavy addition at DP confluence.

cumulative sum is obtained in advance.

Rustic solution, this will pass all samples except the last.

code:python

def solve(N, K, XS):

table = 0 * (K + 1)

for i in range(XS0 + 1):

tablei = 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(XSi + 1):

if j - k < 0:

break

v += tablej - k

v %= MOD

newtablej = v

table = newtable

return tableK

What's wrong with simple is the addition loop, so find the cumulative sum in advance.

code:python

def solve(N, K, XS):

table = 0 * (K + 1)

for i in range(XS0 + 1):

tablei = 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 += tablej

accumj = acc

for j in range(K + 1):

v = accumj

k = j - XSi - 1

if k >= 0:

v -= accumk

newtablej = v % MOD

table = newtable

return tableK

---

This page is auto-translated from /nishio/DP M. 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.