又到了推式子环节。
卢卡斯定理
\(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 超能粒子炮·改
不妨令\(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}<j_{pos}\)的\(i,j\)数量。
什么什么数学题还能用数位DP做。我们设\(dp_{p,0/1,0/1,0/1,0/1}\)表示考虑到从高往底数第\(p\)为,有没有拿到过\(i_{pos}<j_{pos}\),之前考虑的那些位\(i,j\)是否产生过差异(是否分离了,用以满足\(i>j\)的限制),\(i\)是否贴上界,\(j\)是否贴上界。转移还是挺典的。
jzyzP2264 「CTSC2017」吉夫特
仍然是lucas,这次变成了常见的二进制分解。\(C_1^0=1,C_0^1=0,C_0^0=1,C_1^1=1\),所以不合法的情况只有二进制分解后出现了\(C_0^1\),这意味着题目中要求在二进制下\(a_{b_{i}}\)是\(a_{b_{i-1}}\)的子集。一方面也自动满足了不下降的限制。设\(dp_i\)表示以\(i\)结尾的方案数,初值设为\(1\),对于\(a_i\)令\(dp_j\gets dp_{a_i}\)即可。其中\(j\)是\(a_i\)的子集。
agc043bL 123 Triangle
先来分析一波性质。首先这是一个倒三角形的玩意儿,让人联想到杨辉三角。我们发现,\(3\)只会在第一轮出现,后面的将全部变成\(0,1,2\)。我们又发现,只要第二轮出现了\(1\),答案只可能是\(0\)或\(1\),因为\(2\)一定会被吃掉;反之,要是没出现\(1\),那么答案一定为\(0\)或\(2\)。对于后者我们不妨将每个数都除以\(2\),最后求出答案再乘上\(2\),是等价的。所以现在答案只可能是\(0\)或\(1\)了。我们不妨在模\(2\)意义下讨论,为什么这样是对的,因为即使计算过程中出现了\(2\),和\(0\)结合不变,和\(1\)结合的话等价于\(0\)和\(1\)结合,因此直接看成\(0\)即可。
然后这个绝对值减法看着非常难受啊。在目前我见过的绝大多数含有绝对值的题目中,要么通过某种转化把绝对值踢了,要么分讨一下。
那么本题中在模\(2\)意义下的绝对值要怎么踢呢?情况并不多所以不妨列一下:
\((1)_2-(0)_2=1,(1)_2-(1)_2=0,(0)_2-(0)_2=(0)_2\)。
所以结论是\(|x-y|=x \oplus y\)。所以答案为\(\sum[C_{n-1}^{i-1}\bmod2=1]a_i\mod 2\),这里\(\sum\)表示异或和。该乘二的别忘了。
jzyzP7976 「Stoi2033」园游会
套用一句话,先结合实例来分析总是有益无害的。我们掏出杨辉三角,把每个组合系数扔进\(F(x)\)里算一下,可以得到(这个图是偷的对不起):
请移步图册P1。
Z
表示\(1\),.
表示\(0\)。如果记\(G_i\)表示\(\sum_{l=0}^{n}\sum_{r=l}^{n}F(C_r^l)\),那么\(G_i\)的值显然就是上图中从顶端到第\(i\)层的所有数的和。现在来找规律。如果说\(i=3^p\),它代表了一个完整的大三角形,他可以由\(i=3^{p-1}\)那个比他小一级的三角形往顶角、左边、左下角、右边、右下角各放一个,然后全体系数取反后放在底边中间,其余地方全部填\(0\)得到。所以对于这样的\(i=3^p\),有\(G_i=5G_{i/3}-G_{i/3}=4G_{i/3}=4^{p}\),因为\(G_1=1\)。现在来考虑\(i\ne3^p\)怎么办。我们不妨分清况讨论:
1.\(i<3^p\),递归处理之。
2.\(3^{p}<i\le2\times 3^{p}\),相当于\(i\)在上图中横穿左右两边。易得答案为\(G_{p}+2G_{i\bmod3^p}\)。递归处理之。
3.\(2\times 3^{p}<i\le 3^{p+1}\),相当于\(i\)在上图中横穿左右两角。易得答案为\(3G_p+G_{i\bmod3^p}\)。递归处理之。
尝试递归转递推。这个感觉之前没怎么见过,但确实是需要。如何转?从进制角度考虑。三进制下从低位往高位考虑,上述三种情况分别对应模\(3\)的余数为\(0,1,2\),为\(0\)的话什么都不用做,因为已经在更低位做过了;为\(1\)或为\(2\)分别按式子转移即可。
这个从进制角度考虑的思路简直妙极,要细品。