加载中...

Lucas在与位运算有关的组合数中的应用

发表于2023-09-22|OI（高中）2023-2024赛季

|总字数:206|阅读时长:1分钟|浏览量:

Lucas在与位运算有关的组合数中的应用

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133176573

求 $\binom{n}{m}\bmod 2$

根据 Lucas，有 $\binom{n\bmod 2}{m\bmod 2}\binom{n/2}{m/2}$

也就是 $\binom{n\&1 }{m\&1}\binom{n>>1}{m>>1}$

假设结果为奇数，则任意 $\binom{n\&1 }{m\&1}$ 必须为1，则 $m\&1 \subseteq n\&1$

每一位都满足，也就是 $n\&m=m$ 时为奇数

文章作者: zhangxixi

文章链接: http://zhangxixi.top/post/9cf71447

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！

组合数位运算 Lucas

相关推荐

二进制位运算相关的计数问题——巧用高维前缀和：0922T2

二进制位运算相关的计数问题——巧用高维前缀和：0922T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133183403 http://cplusoj.com/d/senior/p/SS230922B 在 https://blog.csdn.net/zhangtingxiqwq/article/details/133176573 当中，我们大致对题目进行了转化。对于询问 kkk ，我们现在要求所有 a(i,j)a(i,j)a(i,j) 的异或和，满足 ...

不可做题考虑最值来猜结论：CCPC2023深圳E

不可做题考虑最值来猜结论：CCPC2023深圳E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134369807 https://vjudge.net/contest/594105#problem/D 场上三个人死磕1.5个小时没磕出来，可以退役了正常情况下区间或的max不可做，所以这题肯定是有什么特殊性质根据对面队伍交流可得，此题为结论题。我们考虑出现次数最多的次数分别是 mx1,mx2mx1,mx2mx1,mx2 ，则 mx1∣mx2mx1|...

【CF339D Xenia and Bit Operations】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16207447.html 题目链接题目 Xenia the beginner programmer has a sequence $ a $ , consisting of $ 2^{n} $ non-negative integers: $ a_{1},a_{2},…,a_{2^{n}} $ . Xenia is currently studying bit operations. To better understand how they ...

莫队维护离线杨辉三角按行求和：ABC463 G

莫队维护离线杨辉三角按行求和：ABC463 G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162421138 https://atcoder.jp/contests/abc463/tasks/abc463_g 前面的式子处理是容易的，令 m=n−x,k=⌊m2⌋m=n-x,k=\lfloor \frac{m}{2}\rfloor m=n−x,k=⌊2m⌋ ，即求： 12n(m(∑i=0k(ni)−∑i=k+1n(ni))+2(∑i=0k(ni)(−i)...

【SSOJ 2872: 「一本通 5.4 例 1」骑士】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15818062.html 题目在 n×nn×nn×n 的棋盘上放 kkk 个国王，国王可攻击相邻的 888 个格子，求使它们无法互相攻击的方案总数。对于全部数据，1≤n≤10,0≤k≤n21≤n≤10,0≤k≤n^21≤n≤10,0≤k≤n2 思路方法一：爆搜方法二：状压dp 每行很大，不可能开个十几维数组，怎么办？把每行压成一个二进制！设 dp(i,j,x)dp(i, j, x)dp(i,j,x) 表示第 iii 行放置状态为 xx...

生成树、Prufer序列的计数问题：0912T1

生成树、Prufer序列的计数问题：0912T1 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132839073 看到生成树计数，很容易想到生成树计数然后发现每个点有度数限制，我们可以先考虑枚举每个点的度数（也可以是Prufer 序列中的出现次数）假设出现次数为 aaa ，可以得出其生成树方案为 n!∏(ai−1)!\frac{n!}{\prod {(a_i-1)!}}∏(ai−1)!n! 然后后面是个组合数的形式，然后需要推一堆式子巧拆阶乘...

数据加载中