当前位置: 首页 > news >正文

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

又到了推式子环节。

卢卡斯定理

\(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}<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\)分别按式子转移即可。
这个从进制角度考虑的思路简直妙极,要细品。

http://www.hskmm.com/?act=detail&tid=20312

相关文章:

  • 2025 最新中国过滤器品牌 TOP10 权威测评推荐厂家与选购指南
  • 2025 年东莞物流公司 TOP 物流服务推荐排行榜,东莞货运物流,东莞到全国物流,东莞大型设备物流,东莞到越南物流专线东莞大件物流,东莞整车物流公司推荐!
  • 使用Python网络爬虫抓取牛客网题目
  • 题解:洛谷 P1012 [NOIP 1998 提高组] 拼数
  • day 7
  • 完整教程:Python 高效实现 PDF 转 Word:告别手动复制粘贴
  • 深入解析:C# 串口通信全解析:从基础到复杂协议的设计思路
  • P6652 「SWTR-5」String
  • 模拟退火 - 学习笔记
  • Markdown语法入门一:标题,列表,表格与字体
  • 质数筛
  • pnpm 安装后无法使用
  • 数学解题中常见的“漏解”情况分析
  • 图册
  • 简单的Powershell脚本
  • 基于YOLO8+flask+layui的行人跌倒行为检测系统【源码+模型+数据集】 - 详解
  • 环形链表-leetcode
  • [ABC425C] Rotate and Sum Query 题解
  • 线程--基本使用、线程常用方法
  • 酵母表面展示技术:从蛋白分析到多领域应用,解锁可持续发展的生物新工具
  • 9/28数学错题分析
  • linux查找指定字符串的三种方法 - 指南
  • task
  • SQL逐字稿
  • 实用指南:嵌入式面试高频(十二)!!!C++语言(嵌入式八股文,嵌入式面经)c++11新特性
  • 2025 年粒度仪厂家推荐山东耐克特分析仪器,粒度分析仪,喷雾,激光,纳米,在线,图像粒形,干湿两用粒度仪公司推荐
  • 2025年匹克球厂家推荐义乌亿宁体育 ,滚塑匹克球,匹克球网,静音匹克球,LED 发光匹克球,专业比赛匹克球公司推荐
  • 2025 年粒度仪厂家推荐山东耐克特分析仪器,电位仪 / 纳米粒度及 Zeta 电位仪 / Zeta 电位仪公司推荐
  • 2025攻丝机厂家 TOP 企业品牌推荐排行榜,全自动,半自动,转盘,伺服,平推,全自动钻孔,半自动钻孔攻丝机公司推荐
  • 实用指南:微信公众号网页调试, 某讯参数,drviceToken V2