Description

硬币购物一共有 \(4\) 种硬币. 面值分别为 \(c_1, c_2, c_3, c_4\). 某人去商店买东西, 去了 \(tot\) 次. 每次带 \(d_i\) 枚 \(c_i\) 硬币, 买 \(s\) 的价值的东西. 请问每次有多少种付款方法.

Input

第 \(1\) 行五个整数 \(c_1, c_2, c_3, c_4, tot\);

接下来 \(tot\) 行, 每行包括五个整数 \(d_1, d_2, d_3, d_4, s\).

Output

每次的方法数

Sample Input

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

Sample Output

4
27

Data Range

对于所有的数据, 满足:\(d_i, s \leq 10^5, tot \leq 1000\).

Explanation

容斥原理, 考虑此处选还是不选用 \(3\) 个参数的 dfs 实现.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 100100;

int T, s, c[5], d[5];
lli dp[maxn];

lli dfs(int x, int k, int sum)
{
    if (sum < 0)
        return 0;
    lli res = 0;
    if (x >= 5) {
        if (k & 1)
            res -= dp[sum];
        else
            res += dp[sum];
        return res;
    }
    res += dfs(x + 1, k + 1, sum - (d[x] + 1) * c[x]);
    res += dfs(x + 1, k, sum);
    return res;
}

int main(int argc, char** argv)
{
    scanf("%d%d%d%d%d", &c[1], &c[2], &c[3], &c[4], &T);
    // Preprocessing types
    dp[0] = 1;
    for (int i = 1; i <= 4; i++)
        for (int j = c[i]; j < maxn; j++)
            dp[j] += dp[j - c[i]];
    for (int idx = 1; idx <= T; idx++) {
        scanf("%d%d%d%d%d", &d[1], &d[2], &d[3], &d[4], &s);
        lli res = dfs(1, 0, s);
        printf("%lld\n", res);
    }
    return 0;
}