基础组合计数与卢卡斯定理

又到了推式子环节。

卢卡斯定理

\(c_{n}^{m}≡C_{n\mod p}^{m\mod p}C_{n/p}^{m/p} \mod p\)
abc240gL Teleporting Takahashi

\(n\leq10^7\)，启示我们可以枚举一维，但是剩下需要\(O(1)\)。
设\(a\)表示\(x\)方向上的步数。必须满足\(a\)与\(x\)的奇偶性相同，因为该方向上走一步就会改变一次奇偶性。同时\(x\leq a\leq n\)。设正向（规定向目标的方向为正）走了\(k\)步，则反向走了\(a-k\)步，有\(k-(a-k)=x\)，解得\(k=(x+a)/2\)。于是\(x\)方向上的方案是\(C_{n}^{(x+a)/2}C_{n-(x+a)/2}^{a-(x+a)/2}\)。考虑完\(x\)，设\(m=n-a\)，则接下来需要在\(m\)步后移动到\((y,z)\)。接下来，出现了两种做法。qls的做法是接着设，然后玩式子。这种做法虽然妙，但是我认为考场上是难以想到的。总结一下另一种偏套路的做法：把坐标系旋转\(45^。\)，单位长度变成原来的\(\sqrt 2\)倍。根据小学学过的三角函数二倍角公式，容易知道目标变成了\((y-z,y+z)\)，操作变成了\((1,-1)(1,1)(-1,1)(-1,-1)\)。最终要的一点，也是旋转坐标系的原因：两维相互独立了。\(y\)方向上的操作和\(z\)方向上的操作不再互相依赖，一个方向上不管正向走还是反向走，另一个方向都可以随便选择。对于任意方向，如果走\(a\)步正的，\(b\)步反的，要到\(t\)，需满足：\(a-b=t\)，\(a+b=m\)，\(a,b\)都可解。由此，这两维的答案是\(C_{m}^{(m+y-z)/2}C_{m+y+z}^{m}\)。与前面乘起来即可。
qls的解法中用到了两个东西，我觉得可能很有用：
\(C_{a+b+c}^{c}C_{b+c}^{b}=C_{a+b+c}^{a+b}C_{a+b}^{a}\)。
\(\sum_{i=0}^{k}C_{a}^{i}C_{b}^{k-i}=C_{a+b}^{k}\)。
jzyzP2038 超能粒子炮·改


\[\sum_{i=0}^{k}C_{n}^{i}\mod p\\\sum_{i=0}^{k}C_{n\% p}^{i\% p}C_{n/p}^{i/p}\mod p\\\sum_{j=0}^{k/p-1}C_{n/p}^{j}\sum_{i=0}^{p-1}C_{n\% p}^{i}+\sum_{i=0}^{k-\lfloor k/p\rfloor \times p}C_{n\% p}^{i}C_{n/p}^{k/p}\mod p\\\sum_{j=0}^{k/p-1}C_{n/p}^{j}\sum_{i=0}^{p-1}C_{n\% p}^{i}+C_{n/p}^{k/p}\sum_{i=0}^{k\%p}C_{n\% p}^{i}\mod p\]
不妨令\(f_{n,k}=sum_{i=0}^{k}C_{n}^{i}\mod p\)，则答案为\(f_{n/k,k/p-1}f_{n\%p,p-1}+C_{n/p}^{k/p}f_{n\%p,k\%p}\)。先预处理\(p\)以内的，再递归处理之直到范围落入\(p\)。
这个题的思想类似于数论分块，相同的部分提出来一块计算，感觉也是常见套路。
LuoguP8367/jzyzP3739 LNOI2022 盒

膜拜这题。移步这里。
BZOJ4737 [清华集训2016] 组合数问题


这个题可以提供一个理解lucas定理的新角度。观察式子\(c_{n}^{m}≡C_{n\mod p}^{m\mod p}C_{n/p}^{m/p} \mod p\)，惊讶的发现\(C\)的上下角标居然是在做一个\(p\)进制分解的事儿。那么一对\(i,j\)要想满足\(C_i^j\equiv 0\mod k\)，必须满足\(i,j\)在\(k\)进制分解下至少存在一对对应位置满足\(C_a^b\equiv 0\mod k\)。注意到\(a,b\in [0,p-1]\)且\(C_a^b=\cfrac{a!}{b!(a-b)!}\)，\(C_a^b\)中一定不含因子\(k\)，所以当且仅当\(a< b\)时才满足条件。原问题转化为：求对于所有\(0\le i\le n,0\le j\le \min(i,m)\)，\(i\)和\(j\)在\(k\)进制分解下存在至少一个对应位置满足\(i_{pos}