加载中...

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://zhangxixi2008.github.io/post/9cf71447

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

组合数 Lucas 位运算

相关推荐

【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 ...

生成树、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! 然后后面是个组合数的形式，然后需要推一堆式子巧拆阶乘...

莫队维护离线杨辉三角按行求和：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)...

组合数与莫队——组合数前缀和

组合数与莫队——组合数前缀和本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133559588 用莫队求组合数是一种常见套路莫队求 S(n,m)=∑i=0m(ni)S(n,m)=\sum_{i=0}^m\binom n iS(n,m)=∑i=0m(in) S(n,m+1)S(n,m+1)S(n,m+1) 直接做个差，然后就相当于加上 (ni+1)\binom n {i+1}(i+1n) 求 S(n+1,m)S(n+1,m)S(n+1,m) 会麻烦点，...

二进制位运算相关的计数问题——巧用高维前缀和：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|...

数据加载中