동전 교환과 쿼리

시간 제한3초메모리 제한512 MB

요약

각 질의마다 액면 c_i짜리 동전을 d_i개 이하로 사용해 합이 정확히 v가 되는 조합의 수를 센다. 답은 64비트 정수 범위다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 조합론, 수학, 구현
정답자: 아직 제출이 없습니다

문제

어느 나라에서 쓰는 동전은 $c_1$ 원, $c_2$ 원, $c_3$ 원, $c_4$ 원 네 종류다. 지갑에는 $c_1$ 원 동전 $d_1$ 개, $c_2$ 원 동전 $d_2$ 개, $c_3$ 원 동전 $d_3$ 개, $c_4$ 원 동전 $d_4$ 개가 들어 있다. 이 동전으로 정확히 $v$ 원을 만드는 방법이 몇 가지인지 세는 프로그램을 작성하시오.

같은 종류의 동전은 서로 구별하지 않는다. 종류별로 사용한 개수가 모두 같으면 같은 방법이다.

예를 들어 1원 동전 3개, 2원 동전 2개, 5원 동전 3개, 10원 동전 1개를 가지고 10원을 만드는 방법은 네 가지다.

$10 = 1 + 1 + 1 + 2 + 5$
$10 = 1 + 2 + 2 + 5$
$10 = 5 + 5$
$10 = 10$

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. ( $1 \le T \le 100$ )

각 테스트 케이스의 첫째 줄에는 정수 $c_1$ , $c_2$ , $c_3$ , $c_4$ , $q$ 가 공백으로 구분되어 주어진다. ( $1 \le c_1 < c_2 < c_3 < c_4 \le 1000$ , $1 \le q \le 100$ )

이어지는 $q$ 개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. 각 쿼리는 정수 $d_1$ , $d_2$ , $d_3$ , $d_4$ , $v$ 로 이루어진다. ( $1 \le d_1, d_2, d_3, d_4, v \le 10^5$ )

출력

각 쿼리마다 $c_1$ 원 동전을 $d_1$ 개 이하, $c_2$ 원 동전을 $d_2$ 개 이하, $c_3$ 원 동전을 $d_3$ 개 이하, $c_4$ 원 동전을 $d_4$ 개 이하로 써서 정확히 $v$ 원을 만드는 방법의 수를 한 줄에 하나씩 출력한다. 만드는 방법이 없으면 0을 출력한다. 답은 32비트 정수 범위를 넘을 수 있다.

예제2

예제 1

입력

2
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900
10 20 30 40 1
100 100 100 100 101

예상 출력

4
27
0

예제 2

입력

3
1 2 3 4 3
1 1 1 1 10
1 1 1 1 5
1 1 1 1 1
2 4 6 8 2
5 5 5 5 7
5 5 5 5 8
5 10 20 50 2
3 3 3 3 100
1 1 1 1 4

예상 출력