Overview

This is a “subset sum counting” problem where you select some items from \(N\) products such that the total price is exactly \(K\) yen, and count the number of ways to do so.

Analysis

Essence of the Problem

This problem asks us to count combinations where we repeatedly make a binary choice of “select” or “don’t select” for each product, and the total price of selected products is exactly \(K\).

Naive Approach and Its Issues

If we try “select/don’t select” for all products, we need to examine \(2^N\) combinations. When \(N = 100\), \(2^{100}\) is an astronomically large number, making this approach far too slow (TLE).

Solution: Dynamic Programming (DP)

We use dynamic programming to efficiently calculate “the number of ways to achieve a total of \(j\) yen.”

Let’s consider a concrete example. If the product prices are \([2, 3, 5]\) and \(K = 5\):

1. Initial state: When buying nothing, there is \(1\) way to have a total of \(0\) yen
2. After considering product 1 (price 2 yen): \(1\) way for total \(0\) yen, \(1\) way for total \(2\) yen
3. After considering product 2 (price 3 yen): \(1\) way each for totals \(0, 2, 3, 5\) yen
4. After considering product 3 (price 5 yen): \(2\) ways for total \(5\) yen (\(\{3, 2\}\) and \(\{5\}\))

In this way, we add products one by one while updating the number of ways to reach each amount.

Algorithm

We use 0-1 knapsack-style subset sum DP.

1. Prepare an array \(dp[j]\) where \(dp[j]\) = “number of ways to have a total of exactly \(j\) yen”
2. Set initial value \(dp[0] = 1\) (there is 1 way to buy nothing)
3. For each product \(i\) (with price \(H_i\)):
   • Loop from \(j = K\) down to \(j = H_i\) in reverse order
   • \(dp[j] \leftarrow dp[j] + dp[j - H_i]\) (add the case of buying product \(i\))
4. Finally, \(dp[K]\) is the answer

Why Update in Reverse Order?

Since each product can be bought at most once, we need to ensure we don’t use the same product multiple times.

• Forward direction (from smaller \(j\) to larger \(j\)): We would reference already-updated \(dp[j - H_i]\), which would count cases where the same product is used multiple times.
• Reverse direction (from larger \(j\) to smaller \(j\)): We reference values that haven’t been updated with the current product yet, guaranteeing each product is used at most once.

Complexity

• Time complexity: \(O(NK)\)
  • For each of the \(N\) products, we perform at most \(K\) updates
• Space complexity: \(O(K)\)
  • Only a 1-dimensional array \(dp\) is used

Implementation Notes

• Don’t forget MOD operations: The number of ways can become very large, so take the remainder when divided by \(10^9 + 7\) at each addition
• Range of reverse loop: Using range(K, price - 1, -1) updates only the range where \(j \geq H_i\) (since we cannot buy the product when \(j < H_i\))
• Setting initial value: Forgetting \(dp[0] = 1\) will leave all values as \(0\)

Source Code

def solve():
    MOD = 10**9 + 7
    
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    
    # dp[j] = number of ways to purchase items totaling exactly j yen
    dp = [0] * (K + 1)
    dp[0] = 1  # There is 1 way to buy nothing
    
    # For each product, consider whether to select it or not (subset sum problem)
    for i in range(N):
        price = H[i]
        # Update in reverse order to guarantee each product is used at most once
        for j in range(K, price - 1, -1):
            dp[j] = (dp[j] + dp[j - price]) % MOD
    
    print(dp[K])

solve()

---

This editorial was generated by claude4.5opus.