Exact change
The till has no change, and you count out exactly N tenge in coins from your wallet. It has coins of eight denominations, 1, 2, 5, 10, 20, 50, 100 and 200 tenge, and a limited number of each: k1 coins of 1 tenge, k2 of 2 tenge, and so on. In how many ways can exactly N tenge be counted out?
Ways differ only in how many coins of each denomination you give: coins of one denomination are indistinguishable, and order does not matter. Giving nothing is also a way if N = 0. There can be very many ways; print their number modulo 109 + 7.
Input
The first line holds N (0 ≤ N ≤ 105). The second holds eight numbers k1, …, k8 (0 ≤ ki ≤ 105): how many coins of 1, 2, 5, 10, 20, 50, 100 and 200 tenge are in the wallet.
Output
The number of ways modulo 109 + 7.
Examples
Example 1
7 3 2 1 0 0 0 0 0
3
Example 2
3 0 1 1 0 0 0 0 0
0
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Start with a wallet that has as many coins of each denomination as you like. Coins are allowed one denomination at a time: ways[s] is how many sets of the coins allowed so far give s. What changes when there are at most k coins of denomination c?
2Hint 2
With the limit, the new answer is a sum of k + 1 old ones: new[s] = ways[s] + ways[s − c] + … + ways[s − k·c]. Adding honestly, for a full wallet that is about N²/2 additions for the 1-tenge coins alone. Compare the sum for s with the sum for s − c: how do they differ?
3The idea
The sums for s and for s − c are windows of k + 1 cells with step c, shifted by one cell. They share k terms, so
$$new[s] = new[s - c] + ways[s] - ways[s - (k + 1)c],$$where the last term is subtracted only if the index is non-negative. This is a sliding window, or prefix sums along each remainder modulo c. Each sum takes one addition and one subtraction, however many coins there are.
4Walkthrough
The DP state is the pair “how much is left to make, which denominations have been dealt with”, as in the ordinary problem about sets of coins from the article. Denominations are processed in turn, each in one pass over the amounts from c to N. The new array is computed from the old one, so both are kept: if you write into the same array, already updated cells get into the window, and coins of denomination c start being counted beyond the limit.
The third test is 1000 tenge with a wallet holding a thousand of each coin: the limits do not interfere, and the answer coincides with the number of sets from the article, 321,335,886.
4+Solution
5Complexity
Eight passes over N + 1 amounts: O(8·N) time, O(N) memory.
6Common mistakes
- An honest sum over the window. Correct, but the fourth test is a full wallet and N = 105: billions of additions.
- Limits ignored. If the coins are treated as unlimited, the first sample and the tests with small k fail.
- A negative remainder. After a subtraction the number can become negative. In Python the
%operator returns a non-negative remainder, while in Go and C++ the remainder of a negative number is negative: add the modulus. - One array instead of two. The window mixes old and new values: see the solution.