Lucas 写炸了彻底怒了

这个题 $a,b$ 没啥用，他能取的数字个数为 $b-a+1$ ，我们们设函数 $f_{x,y}$ 的值为能取到的数字个数为 $x$ 个，这个 $S$ 的长度为 $y$ 的情况数，我们就有式子：

然后我们想怎么求单个的 $f_{x,y}$。

列一下情况 $f_{1,1}=1$ 情况为 1， $f_{1,2}=1$ 情况为 11 ， $f_{2,1}=2$ 情况为 1,2 ， $f_{2,2}=1$ 情况为 11,12,22 ， $f_{3,1}=3$ 情况为 1,2,3 ， $f_{3,2}=6$ 情况为 11,12,13,22,23,33

我们可以把每一个 $f_{x,y}$ 的所有情况看成 $f_{x-1,y}$ 的所有情况和 $f_{x,y-1}$ 的所有情况后面加上一个数字 $y$ ，然后就有 $f_{x,y}=f_{x-1,y}+f_{x,y-1}$ 我们就可把它抽象成一个杨辉三角，那么 $f_{x,y}=C_{x+y-1}^{y}$

所以

然后 Lucas就可以了

Lucas定理

Lucas 定理是一种求组合数是取模数 $p$ 为质数情况下的快速求法，Lucas 定理内容：

$$\left( \begin{array}{c} n \\ m \end{array} \right)\equiv \left( \begin{array}{c} n \mod p \\m \mod p\end{array} \right)\left( \begin{array}{c} \lfloor\frac{n}{p}\rfloor \\ \lfloor\frac{m}{p}\rfloor \end{array} \right)\mod p $$

当 $n<k$ 时，$\left( \begin{array}{c} n \\ m \end{array} \right)$ 规定为 $0$