문제 설명

4가지 종류의 동전이 있으며 각각의 액면가는 \(c_1, c_2, c_3, c_4\)입니다.

어떤 사람이 가게에서 물건을 \(n\)번 구매합니다. 각 구매마다 \(i\)번째 동전을 \(d_i\)개씩 가지고 있으며, 총 \(s\) 가치의 물건을 사려고 합니다. 각 구매에 대해 지불 방법의 수를 구하세요.

입력 형식

첫 번째 줄에는 다섯 개의 정수 \(c_1, c_2, c_3, c_4, n\)이 주어집니다.

다음 \(n\)개의 줄에는 각각 다섯 개의 정수 \(d_1, d_2, d_3, d_4, s\)가 주어집니다.

출력 형식

각 구매에 대해 답을 한 줄에 하나씩 출력합니다.

예제 #1

예제 입력 #1

1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900

예제 출력 #1

4
27

제약 조건

• \(1 \leq c_i, d_i, s \leq 10^5\)
• \(1 \leq n \leq 1000\)

분석

이 문제는 여러 동전으로 특정 금액을 만드는 방법의 수를 구하는 전형적인 다중 배낭 문제로 보이지만, 각 동전의 사용 개수에 제한이 있고 쿼리 횟수가 많습니다. 단순 다중 배낭으로 풀면 시간 복잡도가 \(O(4 \cdot n \cdot s)\)로 매우 커져 비효율적입니다. 따라서 완전 배낭과 포함-배제 원리를 사용하는 다른 접근 방식이 필요합니다.

완전 배낭 + 포함-배제 원리

먼저 각 동전의 개수 제한을 무시하고, 모든 동전을 무한히 사용할 수 있다고 가정합니다. 이때 금액 \(j\)를 만드는 방법의 수를 \(f[j]\)라고 정의합니다. 완전 배낭 점화식은 다음과 같습니다.

f[0] = 1
for i in 1..4:
    for j in c[i] to MAX_SUM:
        f[j] += f[j - c[i]]

이제 개수 제한을 고려합니다. 예를 들어 첫 번째 동전을 \(d_1\)개까지만 사용해야 한다면, \(d_1+1\)개 이상 사용하는 경우는 불가능합니다. \(f[s]\)는 무제한 경우이므로, 첫 번째 동전을 \(d_1+1\)개 이상 사용한 경우를 빼야 합니다. 이는 \(s - (d_1+1) \cdot c_1\) 금액을 남은 동전(무제한)으로 만드는 방법의 수와 같습니다.

하지만 여러 동전의 제한을 동시에 고려할 때는 각 제한을 위반한 경우가 겹칠 수 있습니다. 따라서 포함-배제 원리를 적용해야 합니다. 각 동전 \(i\)에 대해 개수 제한을 위반한 사건을 \(A_i\)라고 하면, 전체 경우의 수는 \(f[s]\)이고 우리가 원하는 경우의 수는 \(f[s]\)에서 모든 \(A_i\)의 합집합을 뺀 값입니다.

포함-배제 원리에 따라, 4개의 동전에 대한 최종 답은 다음과 같습니다.

ans = f[s]
    - (A1 + A2 + A3 + A4)
    + (A1∩A2 + A1∩A3 + A1∩A4 + A2∩A3 + A2∩A4 + A3∩A4)
    - (A1∩A2∩A3 + A1∩A2∩A4 + A1∩A3∩A4 + A2∩A3∩A4)
    + (A1∩A2∩A3∩A4)

여기서 각 교집합의 크기는 해당 동전들을 모두 \(d_i+1\)개 이상 사용한 경우의 수를 의미합니다. 예를 들어 \(A_1 \cap A_2\)의 크기는 \(f[s - (d_1+1)\cdot c_1 - (d_2+1)\cdot c_2]\)입니다.

비트마스킹을 사용하여 0부터 15까지의 모든 부분집합을 순회하며, 각 부분집합에 포함된 동전의 수가 짝수이면 더하고 홀수이면 빼는 방식으로 포함-배제를 구현할 수 있습니다.

코드 (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAX_VAL = 100005;
ll f[MAX_VAL];
int coin[5], limit[5];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 1; i <= 4; i++) cin >> coin[i];
    
    // 완전 배낭: 무제한 동전으로 금액 만드는 경우의 수
    f[0] = 1;
    for (int i = 1; i <= 4; i++) {
        for (int j = coin[i]; j < MAX_VAL; j++) {
            f[j] += f[j - coin[i]];
        }
    }

    int q;
    cin >> q;
    while (q--) {
        for (int i = 1; i <= 4; i++) cin >> limit[i];
        int target;
        cin >> target;
        ll ans = 0;

        // 0부터 15까지 모든 부분집합 순회
        for (int mask = 0; mask < (1 << 4); mask++) {
            int cnt = 0;
            ll deduction = 0;
            for (int i = 1; i <= 4; i++) {
                if (mask & (1 << (i - 1))) {
                    cnt++;
                    deduction += (ll)(limit[i] + 1) * coin[i];
                }
            }
            if (target >= deduction) {
                if (cnt & 1)
                    ans -= f[target - deduction];
                else
                    ans += f[target - deduction];
            }
        }
        cout << ans << '\n';
    }
    return 0;
}