概述卢卡斯定理主要用于求解组合数取模问题。公式原命题见： https://zh.wikipedia.org/wiki/%E5%8D%A2%E5%8D%A1%E6%96%AF%E5%AE%9A%E7%90%86原命题等价于：$$\binom{m}{n}=\binom{\lfloor \dfrac{m}{p}\rfloor}{\lfloor \dfrac{n}{p}\rfloor}\times ...
反向最优解 $rk3$ 达成。题意求$$\sum_{i=0}^k C_n^i\mod 2333$$其中 $t\le 10^{5} \ , \ n,k\le 10^{18}$题解令 $ha=2333$ ，先用 $\text{Lucas}$ 定理化简$$\sum_{i=0}^k C_{n\div ha}^{i\div ha}\times C_{n\ mod \ ha}^{i\ mod \ ha}...
题意求长度在 $1\sim N$ 之间，由 $[L,R]$ 之间的数构成的单调不降序列的个数。$N,L,R\le 10^{9}$ 。多组数据，组数 $t\le 100$ 。题解令 $M=R-L+1$ ，即可以使用的数的个数。先考虑固定长度为 $n$ 的情况。因为是单调不降，所以数字可以重复使用，而只要选出一部分数就能构成一个且仅有一个满足要求的序列。答案就等价于从 $M+n$ 个数中选出 $...
题意定义$$P=\sum_{i-1}^n i|n\ C_n^i$$求$$G^P\mod 999911659$$其中 $N,P\le 10^{9}$ 。题解由拓展欧拉定理得$$G^P\equiv G^{P\mod \varphi(999911659)} \pmod {999911659}$$因为 $999911659$ 是质数，所以$$\varphi(999911659)=999911658$...