标签: 容斥

1 篇文章

洛谷 – P1450 – [HAOI2008]硬币购物
共有 $4$ 种硬币。面值分别为 $c_1,c_2,c_3,c_4$。
某人去商店买东西,去了 $n$ 次,对于每次购买,他带了 $d_i$ 枚第 $i$ 种硬币,想购买价值恰好为 $s$ 的东西。
多次询问,每次询问形如 $(d_1,d_2,d_3,d_4,s)$,求付款方法数。
$1\leq c_i,d_i,s\leq 10^5$,$1\leq n\leq 1000$.