题目链接：

题目大意：给出四个数$p,n,l,r$，对于$\forall 0\le a\le p-1$，求$l\le x\le r,C_{x}^{n}\%p=a$的$x$的数量。$p<=3000$且保证$p$是质数，$n,l,r<=10^30$。

对于$10\%$的数据，可以直接杨辉三角推。

对于$20\%$的数据，因为$n$是确定的，可以递推出$C_{x+1}^{n}=C_{x}^{n}*\frac{x+1}{x+1-n}$。

对于另外$20\%$的数据，可以枚举$x$然后用$lucas$定理求。

对于另外$30\%$的数据，可以想到将问题转化成小于等于$r$的个数$-$小于等于$l-1$的个数。由$lucas$定理可知，$C_{x}^{n}\ mod\ p=\prod C_{b_{i}}^{a_{i}}\ mod\ p$，其中$a_{i},b_{i}$分别为$n,x$在$p$进制下的第$i$位。那么我们就可以用数位$DP$求，$f[i][j]$代表从最低为开始的前$i$位，每一位的值都不大于$b_{i}$且$\%p=j$的方案数；$g[i][j]$代表从最低为开始的前$i$位，每一位的值任意且$\%p=j$的方案数。设枚举第$i+1$位为$x$，$C_{x}^{a_{i+1}}=k$。那么可以得到$DP$转移方程$g[i+1][jk\ mod\ p]+=g[i][j]$，若$x<b_{i+1}$，则$f[i+1][jk\ mod\ p]+=g[i][j]$，若$x=b_{i+1}$，则$f[i+1][jk\ mod\ p]+=f[i][j]$。时间复杂度为$O(p^2log_{p})$。

对于$100\%$的数据，我们考虑优化上述$DP$，我们拿其中第一个转移方程来说(后两个同理)，我们设$h[k]=\sum\limits_{x=0}^{p-1}[C_{x}^{a_{i+1}}==k]$。可以发现转移可以看成是$G[j*k\ mod\ p]=\sum\limits_{j=0}^{p-1}g[j]\sum\limits_{k=0}^{p-1}h[k]$，这和卷积式子很像，但他是乘法卷积，我们想办法将它变成加法卷积：因为$p$是质数，那么$p$一定有原根(设为$g$)，也就是说对于任意$j$，其中$1\le j\le p-1$都有指标。我们设它的指标为$ind(j)$，那么$j*k\ mod\ p$就能转化为$g^{(ind(j)+ind(k))\ mod\ (p-1)}\ mod\ p$。这样我们就能用$FFT$或$NTT$来加速$DP$了，但注意到$0$没有指标，我们在转移时先忽略$0$，在最后输出答案时用总个数减掉其他答案就是$\%p=0$的个数了。注意原根从$1$开始枚举。至于$10^{30}$可以用$\_\_int128$存。时间复杂度为$O(plog_{p}^2)$。

两种写法，读者自选。

#include
     
      #include
      
     

#include
     
      #include