Thought Process

Very similar to the previous problem (Problem 249), a bit more technical in my opinion

I used dynamic programming again.

We have an array[x] = number of subsets who remainder modulo 250 is x

The difference between this problem and the previous one, is that the previous has an ordering to it, the smallest sets never get touched once they are surpassed, here a modulo can bring you right back to the start.

If we were in the previous problem, we could simply do this

array = [1] + [0]*249
for x in {1^1, 2^2, ...}:
for y in range(250):
array[(x + y) % 250] += array[y] <- Make some test cases to come up with this yourself!
array[(x + y) % 250] %= mod

However, because of the looping I just talked about, array[y] may be updated as we move along for higher numbers, and it would be the same should we work backwards.

Instead what we do is initialise a second array, which is equal to the previous array, and we update it after every turn, it would look like so:

array = [1] + [0]*249
array2 = [1] + [0]*249
for x in {1^1, 2^2, ...}:
for y in range(250):
array[(x + y) % 250] += array2[y] <- this is the difference
array[(x + y) % 250] %= mod
array2 = [x for x in array] (Note: we cannot do array2 = array, otherwise these 2 become one object!)

We could also replace the entire array for slightly more concise code:

array = [1] + [0]*249
for x in values:
array = [(array[y] + array[(x + y) % 250]) % mod for y in range(len(array))]