LOJ#3730. 「SNOI2022」数位

非常不错的一道容斥 + 斯特林数 + 数位 DP。

考虑对于每个 $S = \sum_{i} a_{i}$ 求方案数。因为有 $L \leq a_{i} \leq R$ 的限制，我们考虑经典容斥。设若只存在限制 $a_{i} \geq L$ ，那么方案数通过隔板法容易得到为 $(\binom{S - k (L - 1) - 1}{k - 1})$ 。于是容斥，设至少有 $x$ 个 $a_{i}$ 满足 $a_{i} > R$ ，再利用二项式反演得到：

\sum_{i = 0}^{k} (- 1)^{i} (\binom{k}{i}) (\binom{S - k (L - 1) - i (R - L + 1) - 1}{k - 1})

设 $x = S - k (L - 1) - i (R - L + 1) - 1$ ，那么要求 $(\binom{x}{k - 1})$ 。 $x$ 很大，在组合数上不好处理，我们尝试将限制转为 $k$ 。通过第一类斯特林数，我们可以将下降幂转为普通幂 $x^{\underset{―}{n}} = \sum_{i = 0}^{n} (- 1)^{n - i} [\binom{n}{i}] x^{i}$ ，也就是有 $(\binom{x}{n}) = \frac{x^{\underset{―}{n}}}{n!} = \frac{1}{n!} \sum_{i = 0}^{n} (- 1)^{n - i} [\binom{n}{i}] x^{i}$ 。于是我们对于每个 $i \in [0, k - 1]$ 求出 $\sum_{x} x_{i}$ 即可。

接下来