Project: Portfolio Selection · Score Generating Functions

Lesson 6

Nikolai Chukhin · Alexander S. Kulikov

Programming problem.

Implement a program for the following task. There are \(n\) stocks, and stock \(i\) has price \(p_{i}\). Each stock may be bought at most once. Count the number of portfolios whose total price is exactly \(B\).

  • Input format.  The first line contains two integers \(1 \le n \le 200\) and \(0 \le B \le 5000\). The second line contains integers \(1 \le p_{1},\dotsc,p_{n} \le 5000\).

  • Output format.  Output the number of portfolios of price exactly \(B\) modulo \(10^{9}+7\).

Hint:
Let \(D_{b}\) denote the number of ways to obtain a total price \(b\) using the stocks processed thus far. Initially, \(D_{0}=1\) and \(D_{b}=0\) for any \(b \neq 0\). When processing a stock with price \(p_{i}\), update the entries of \(D\).

5 points
Public samples
Public sample 1
Input
4 10
2 3 5 7
Expected output
2
Public sample 2
Input
4 12
2 3 5 7
Expected output
2
Public sample 3
Input
4 10
5 5 5 5
Expected output
6