乍一看限制条件很多，难做。
试试把子问题拆解成小问题：
共有 1 种硬币。面值为 c_1。不限制使用次数，请问每次有多少种付款方法？
这样变成了裸的完全背包，直接 O(n) 解决。但是原问题怎么写啊？我也不知道啊 qwq。
满足条件的方案总数 不好求，但是 不满足条件的方案总数 可以求，那么只要 方案总数 - 不满足条件的方案总数 = 满足条件的方案总数！
怎样是非法的呢？那就是取的硬币数量 sum>d_i，即一旦 sum=d_i+1，那么接下来不论怎么取硬币都是非法方案。
那强制令体积为 s-c_i \cdot (d_i+1) 时所有方案都是非法的，此时状态转移方程好推，
ans=dp_s-dp_{s-c_i \cdot (d_i+1)}
即我们把不合法方案看做 4 个集合，要求的就是集合们的并集。设第 i 个集合为 A_i，即求 |A_1 \cup A_2 \cup A_3 \cup A_4|。
由容斥原理
\left| \bigcup_{i=1}^n A_i \right| = \sum_{k=1}^n (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} \left| A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k} \right|
即集合的并等于集合的交的交错和（奇正偶负）可得到：
|A_1 \cup A_2 \cup A_3 \cup A_4| \\
= (|A_1| + |A_2| + |A_3| + A_4|) - (|A_1 \cap A_2| + |A_1 \cap A_3| + |A_1 \cap A_4| + |A_2 \cap A_3| + |A_2 \cap A_4| + |A_3 \cap A_4|)
+ (|A_1 \cap A_2 \cup A_3| + |A_1 \cap A_3 \cap A_4| + |A_2 \cap A_3 \cap A_4|) \\ - |A_1 \cap A_2 \cap A_3 \cap A_4|
两个集合的并集怎么求呢？
还是类似刚才的做法，如果要让这种方案成立，我们就强制把两个硬币全部扣去，即 s-c_i \cdot (d_i+1)-c_j \cdot (d_j+1) 同样可以拓展到 n 个的情况。
用二进制设计状态更加简洁。