首页 > 其他分享 >【学习笔记】组合数奇偶判断

【学习笔记】组合数奇偶判断

时间:2024-03-29 17:16:00浏览次数:25  
标签:lfloor 奇偶 frac 组合 text sum 个数 笔记 times

在 \(\text{dp}\) 专题的本题( Future Failure )中需要到了此结论,所以写一下

首先我们知道 \(\dbinom{m}{n}=\dfrac{n!}{m!(n-m)!}\)

假设 \(n!,m!,(n-m)!\) 的2因子个数均为 \(\text{A,B,C}\)

显然组合数为奇数时当且仅当 \(\text{A=B+C}\)

考虑 \(\text A\) 和 \(n!\) 的关系,对于一个质数 \(p\) 其在 \(n!\) 内的因数个数为

\[\sum_{p^i\le n}\lfloor\frac{n}{p^i}\rfloor \]

这个是很明显的,我和 wang54321 一小会儿就推出来了,因此其因子 \(2\) 的个数为

\[\sum_{p^i\le n}\lfloor\frac{n}{2^i}\rfloor \]

对于 \(n\) 其可以表示为

\[n=\sum 2^{i-1}a_{i} \]

那么我们可以把上面的式子进行化简

\[\begin{align} \sum_{p^i\le n}\lfloor\frac{n}{2^i}\rfloor &=\sum_{y=1}^k\lfloor\frac{(a_1\times 2^0)+(a_2\times 2^1)+...+(a_k\times 2^{k-1})}{2^y}\rfloor\\ &=\sum_{y=1}^k\frac{(a_{y+1}\times 2^{y})+...+(a_k\times 2^{k-1})}{2^y}\\ &=\sum_{y=1}^k\sum_{x=y+1}^k\frac{a_x\times 2^{x-1}}{2^y}\\ &=\sum_{x=1}^ka_x\sum_{y=0}^{x-2}{2^y}\\ &=\sum_{x=1}^k(2^{x-1}-1)a_x\\ &=\sum_{x=1}^k{a_x*2^{x-1}}-\sum_{x=1}^k{a_x}\\ &=n-\sum_{x=1}^k{a_x} \end{align} \]

我们观察可以发现 \(n\) 在二进制下 \(1\) 的个数为 \(\sum\limits_{x=1}^k{a_x}\)

因此 \(n!\)在二进制下 \(2\) 因子的个数等于 \(n\) 减去其二进制下 \(1\) 的个数。

而组合数为奇数当且仅当 \(\text{A=B+C}\)

假设 \(n,m,(n-m)\) 在二进制下 \(1\) 的数目分别为 \(a,b,c\)

\[n-a=m-b+(n-m)-c \]

\[a=b+c \]

因此很明显我们可以发现当 \(n\&m=m\) 时 \(\dbinom{m}{n}\) 为奇数

标签:lfloor,奇偶,frac,组合,text,sum,个数,笔记,times
From: https://www.cnblogs.com/Vsinger-LuoTianYi/p/18104205

相关文章

  • JavaScript快速入门笔记之七(String:字符串类型、RegExp:正则表达式)
    JavaScript快速入门笔记之七(String:字符串类型、RegExp:正则表达式)String:字符串类型什么是字符串?底层本质:一串字符组成的只读字符数组包装类型:临时封装原始类型数据,并提供对数据操作方法的对象——类型名和原始类型名相同!StringNumberBoolean何时使用:不必手动创建!......
  • 鼠鼠的拍照学习笔记
    拍照学习笔记参考:构图——【8分钟学会全部构图技巧!想拍照好看必学的19种构图方法!手机相机拍照通用!】一、关于构图1.1基本方法中心构图——将主题放在画面中心,最常见。主体明确突出。对称构图——上下或左右对称。水平线构图——让画面中的水平线(横线)保持......
  • 原语笔记:BuF系列
    参考:UG472UG953UG768BUFGPrimitive:GlobalClockSimpleBuffer介绍:该设计元素是一个高扇出缓冲器,它将信号连接到全局布线资源,以实现信号的低偏斜分布。BUFG通常用在时钟网络以及其他高扇出网络(例如设置/重置和时钟使能)上。简介:全局缓冲,BUFG的输出到达FPGA内部的I......
  • JavaWeb学习笔记——第八天
    MySQL(三)多表查询多表查询指从多张表中查询数据。可以直接使用指令select*from表1,表2;来同时查询表1和表2的数据,但此时会出现笛卡尔积的情况。笛卡尔乘积是指在数学中,两个集合(A集合和B集合)的所有组合情况。(在多表查询时,需要消除无效的笛卡尔积)使用指令select*fr......
  • 基础K线组合形态
    ------......
  • 使用MergeKit创建自己的专家混合模型:将多个模型组合成单个MoE
    由于Mixtral的发布,专家混合(MoE)架构在最近几个月变得流行起来。虽然Mixtral和其他MoE架构是从头开始预训练的,但最近出现了另一种创建MoE的方法:Arcee的MergeKit库可以通过集成几个预训练模型来创建moe。这些人通常被称为frankenMoEs或MoErges,以区别于预先训练的MoEs。在本文中,我......
  • mybatis+spring组合使用
    1、mybatis+spring配置applicationContext.xml数据库使用c3p0sqlSessionFactory被集成为一个bean<?xmlversion="1.0"encoding="UTF-8"?><beansxmlns="http://www.springframework.org/schema/beans"xmlns:xsi="http://www.w3.o......
  • vulntarget-e内网靶场笔记
    vulntarget-e一.打靶过程1.外网打点向日葵rcenmap-T4-sV-O-p0-65535192.168.126.130访问了49773端口后只有这个页面,只能扫描一下目录看看,但是扫出来也都是跳转到这个页面扫一下指纹信息,发现是向日葵(这里我自己扫不出来,俊贤哥说向日葵端口是变化的的自己写识别)未......
  • Cisco Packet Tracer模拟器下载笔记
    给初学Cisco网络设备的小伙伴演示思科模拟器下载的方法及注意事项!目录   1:百度输入“思科网络技术学院”搜索官网主页。   2:进入“思科网络技术学院”主页。   3:登录个人账号。      3-1:点击“LogIn”。      3-2:有账户自接......
  • 如何将几个长度相同的列表并列组合在一起(附:zip函数使用出错原因:巨坑~)
        Python中列表对象使用很方便,用Python编程时,经常会遇到将多个长度相同的列表是针对某一组特定对象的,如何能方便的把这些列表组合起来一起使用呢?ZIP()函数可以方便的解决这个问题。一、将几个长度相同的列表并列组合例如,设置四个列表ID=[1,2,3,4]Name=['小......