题目描述

硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。

数据规模

di,s<=100000

tot<=1000

题解：

首先，我们不考虑硬币的限制，用动态规划求解背包方案数。然后考虑容斥原理，进行解题。编程上有技巧：使用dfs来减少代码量。

#include
    
     typedef long long ll;const int maxn = 1e5+10;int c[4],d[4];int tot;int S;ll f[maxn],ans;inline void prelude(void) {    f[0]=1;    for(int i = 0;i<4;++i) {        for(int V=c[i];V