卢卡斯定理

简介

对于非负整数m和n和素数p，同余式:

${\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},$
成立。其中：
$m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},$
并且
$n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}$
是 $m$ 和 $n$ 的 $p$ 进制展开。当 $m < n$ 时，二项式系数 ${\tbinom {m}{n}}=0$ 。

代码

int C(int n, int m) {
    if (m > n || m < 0) {
        return 0;
    }
    m = min(m, n - m);
    if (n < p && m < p) {
        int re = 1;
        for (int i = 0; i < m; i++) {
            re = (long long)re * (n - i) % p * pow(i + 1, p - 2, p) % p;
        }
        // 或改为预处理阶乘和阶乘逆元的版本
        return re;
    }
    return (long long)C(n % p, m % p) * C(n / p, m / p) % p;
}

奇偶性

当只需要判断组合数奇偶性时，可以通过位运算来判断。

证明

勒让德定理

库默尔定理

库默尔定理指出，给定整数 $n \geq m \geq 0$ 和一个质数 $p$ ， $\binom{n}{m}$ 中 $p$ 的次数是在 $p$ 进制下 $m$ 加 $n-m$ 的进位次数。

参考题目

输入一个n
问1! 2! ... n! 中有多少个阶乘末尾有偶数个0
n <= 1e9

bzoj 1902

P1869 愚蠢的组合数

https://www.luogu.com.cn/problem/P1869

题目描述

最近老师教了狗狗怎么算组合数，狗狗又想到了一个问题。。。

狗狗定义C(N,K)表示从N个元素中不重复地选取K个元素的方案数。

狗狗想知道的是C(N,K)的奇偶性。

当然，这个整天都老是用竖式算123456789*987654321=？的人不会让你那么让自己那么轻松，它说：“N和K都可能相当大。”

但是狗狗也犯难了，所以它就找到了你，想请你帮他解决这个问题。

输入格式

第1行：一个正整数t，表示数据的组数。

第2~2+t-1行：两个非负整数N和K。（保证k<=n）

输出格式

每一组输入，如果C(N,K)是奇数则输出1，否则输出0。

样例 #1

样例输入 #1

样例输出 #1

1
1
0

提示

数据范围

对于100%的数据，n<=10^5 t<=10^5

参考代码

#include <bits/stdc++.h>
using namespace std;
int t, n, m;
int main() {
	cin >> t;
	for (int tt = 0; tt < t; tt++) {
		cin >> n >> m;
		cout << ((n & m) == m) << endl;
//		cout << !(~n&m) << endl;
	}
	return 0;
}

题解

C(0, 0) = 1
C(0, 1) = 0
C(1, 0) = 1
C(1, 1) = 1

计算 C(n, m) % 2 相当于判断
是否存在一位 n是0， m是1
如果存在，答案是0
如果不存在，答案是1

if ((~ n & m) > 0) 答案是0

~
&
|
^

2个参数的位运算一共有16个

!
&&
||

15 = 1111
5 = 0101
C(15, 5) % 2 = C(1, 0) * C(1, 1) * C(1, 0) * C(1, 1);

C(0, 0) = 1
C(0, 1) = 0
C(1, 0) = 1
C(1, 1) = 1

C(n, m) 的奇偶性是否存在一位n是0，m是1

C(16, 5) 其中2的次幂是多少呢？

C(n, m)
m和n-m都转化为2进制，相加，问发生了几次进位，就是2的次幂是多少
5 = 0101
11 = 1011

参考资料

https://en.wikipedia.org/wiki/Lucas's_theorem

https://en.wikipedia.org/wiki/Kummer's_theorem