【2023GGXS】货币 做题记录

有 $m$ 种货币，第 $i$ 种面值为 $2^{i-1}$，求凑出 $n$ 元钱有多少种方案数，对 $998244353$ 取模。

Ex：求 $n$ 有多少种 $m$ 位 $k$ 进制表示（每一位的数字无上限）。

$1\le m\le 30$，$0\le n\le 10^{18}$，$2\le k\le 16$。

考虑把面值为 $2^i$ 的货币拆成面值 $2^{i}$、$2^{i+1}$、$2^{i+2}$……的货币各一个，即把 $2^i$ 的选择个数 $a_i$“摊平”。这样就可以转化为 01 背包。

那么数位 dp，设 $dp_{i,j}$ 表示考虑完 $2^0\sim 2^i$，向后进了 $j$ 的方案数。

转移考虑枚举有 $k$ 种面值当前位都为 $1$，枚举上一位的进位 $l$，则：

$dp_{i,\lfloor\frac{k+l}{2}\rfloor}=[k+l\equiv n_{2^i}\text{ (mod }2\text{)}]\binom{\min(m,i+1)}{k}dp_{i-1,l}$

Ex 做法类似，不过拆出来的每种货币可以选 $k-1$ 个。