非常不错的一道容斥 + 斯特林数 + 数位 DP。
考虑对于每个 $S=\sum_i a_i$ 求方案数。 因为有 $L\le a_i\le R$ 的限制,我们考虑经典容斥。设若只存在限制 $a_i\ge L$,那么方案数通过隔板法容易得到为 $\binom{S-k(L-1)-1}{k-1}$。于是容斥,设至少有 $x$ 个 $a_i$ 满足 $a_i>R$,再利用二项式反演得到:
设 $x=S-k(L-1)-i(R-L+1)-1$,那么要求 $\binom{x}{k-1}$。$x$ 很大,在组合数上不好处理,我们尝试将限制转为 $k$。通过第一类斯特林数,我们可以将下降幂转为普通幂 $\displaystyle x^{\underline n}=\sum_{i=0}^n (-1)^{n-i} {n\brack i} x^i$,也就是有 $\displaystyle \binom{x}{n}=\frac{x^{\underline {n}}}{n!}=\frac{1}{n!}\sum_{i=0}^n (-1)^{n-i} {n\brack i} x^i$。于是我们对于每个 $i\in[0,k-1]$ 求出 $\sum_x x_i$ 即可。
接下来