题目地址
QAQ我把这题出出来之后，发现以前有一道几乎一样的题，而且我还A过！感觉自己记性真的有点好......
算法一
对于$10\%$的数据，$n, l, r \le 1000$。因此我们直接暴力枚举$x$，然后暴力求组合数即可。
如果你不会模意义下的除法，可以用杨辉三角打出前$1001$行，然后直接查询。
如果你既不会除法也不会杨辉三角(居然能看懂题目？)，存在$5\%$的数据$n, l, r \le 10$，答案可以用各种方法直接算出来= =b。
算法二
对于$20\%$的数据，$n, l, r \le 100000$，我们可以用公式 ${n + 1 \choose m} = \frac{n + 1}{n - m + 1}{n \choose m}$递推出所有组合数。
算法三
对于另外$20\%$的数据，$r - l \le 10000$，我们暴力枚举$x$之后，组合数计算可以根据Lucas定理计算，但是直接枚举计算是会超时的。
首先我不知道有多少人听到这个定理后想到的是这个公式
${a \choose b} \bmod p = {\lfloor\frac{a}{p}\rfloor \choose \lfloor\frac{b}{p}\rfloor}{a \bmod p \choose b \bmod p} \bmod p$
而不是
${a \choose b} \bmod p = \prod\limits_{i \ge 0}{a_i \choose b_i} \bmod p$，其中$a_i$表示$a$在$p$进制下从较低位数起的第$i$位。
前者和后者的等价关系很显然。
用第二个公式，我们对每一位都预处理出所有组合数，复杂度为$p \times 位数$，然后枚举$x$之后可以用$O(位数)$的时间直接查询每一位的组合数值然后算出来，如果每次重新计算$x$的$p$进制，复杂度为每次$O(位数 ^ 2)$，如果每次加$1$并进位，还可以做到$O(位数)$，两种复杂度都可以轻松通过这一部分数据。
算法四
首先问题容易转化为小于等于$r$的$x$个数减去小于等于$l - 1$的$x$个数，我们只要考虑形如$x \le bound$的限制即可。
算法三给了我们启发，我们应该从$p$进制下考虑。
很容易设计出数位DP的状态和转移方程：
$g[i, j]$表示从低位开始前$i$位任意且值为$j$的方案数。 $f[i, j]$表示从低位开始前$i$位对应的$p$进制数不超过$bound$的前$i$位对应的$p$进制数且值为$j$的方案数。
假设$n$的第$i + 1$位为$y$，$bound$的第$i + 1$位为$w$，枚举第$i + 1$位的值$x$，若${x \choose y} = z$则
$g[i + 1, jz \bmod p]$ += $g[i, j]$
若$x \lt w$则$f[i + 1, jz \bmod p]$ += $g[i, j]$
若$x = w$则$f[i + 1, jz \bmod p]$ += $f[i, j]$
时间复杂度为$O(位数 \times p ^ 2)$，结合算法三可以获得$70$分，事实上前$40$分的答案比较稀疏，通过常数优化或许可以直接通过。
算法五
由于$p$是质数那么一定存在原根$g$，在算法四的转移方程中，若$j$，$z$均不为$0$，那么一定存在原根$g$下的关于模$p$的离散对数，通过取离散对数再根据费马小定理，很容易将转移方程中的$jz \bmod p$转化为$g ^ {(ind(j) + ind(z)) \bmod (p - 1)} \bmod p(ind(x)$表示$x$在原根$g$下关于模$p$的离散对数)，从而转移方程可化为卷积的形式，FFT即可。
对于$j = 0$或者$z = 0$的情况，我们可以在转移中忽略，先将$1 \rightarrow p - 1$的答案统计出来，然后用总数减掉即可。
由于模数的特殊性，可以用数论变换解决。
于是这题被完美解决啦。
提交记录在这里。
p = 2挂掉啦！
注意枚举原根要从$1$开始而不是从$2$开始
此外数组要开到$100$左右，而不是$30$或者更少。
太麻烦了
请问你们这些说麻烦的人，都为什么会觉得麻烦？
求原根太麻烦
这题的$p$很小，加上原根很多，直接暴力从$1$到$p$枚举然后直接枚举$1$到$p - 2$次方看有没有提前出现$1$即可，连$p - 1$的约数都不用枚举！
我不想写离散对数的大步小步算法
还是那句话，这题的$p$很小，直接预处理出所有的数的离散对数值即可。
此外逆元也可以预处理，并且还可以使用$O(p \log p)$的算法，不一定要写线性算法。
我不想写高精度
你可以用自带高精度的语言比如$\mathrm{python,java}$等，当然要注意常数问题。
如果你只会$\mathrm{C}$++，UOJ支持$\mathrm{C}$++的__$\mathrm{int128}$(__$\mathrm{int128}$_$\mathrm{t}$)，可以避免高精度。
使用方法可以参考这个提交记录：__$\mathrm{int128}$(__$\mathrm{int128}$_$\mathrm{t}$)
鄂公网安备 42010202000505 号