Lucas 定理
若 \(p\) 是质数，则对于任意整数 \(1\leq m \leq n\)，有：
\[\dbinom{n}{m}\equiv \dbinom{n\mod p}{m\mod p}\times \dbinom{\dfrac{m}{p}}{\dfrac{n}{p}}\pmod p \]证明太难，略。
例题 \(1\)：SP18878
题目大意
求杨辉三角第 \(n\) 行中偶数个数与奇数个数。
题目分析
我们先求第 \(n\) 行的奇数个数， 用这一行总数减一下就是偶数个数。
等价于求 \(\sum ^{n}_{i=0} \dbinom {n}{i} \mod 2\)。把 \(n,i\)
拆分成二进制数，二进制每一位记为 \(n_k,i_k\)。
根据 Lucas 定理，
\[\dbinom {n}{i} \mod 2=\dbinom{n\mod 2}{i\mod 2}\times \dbinom{\dfrac{n}{2}}{\dfrac{i}{2}}\mod 2 \]当 \(\dbinom {n}{i} \mod 2=1\) 时， 那么所有的 \(n_k,i_k\) 必定满足 \(\dbinom{n_k}{i_k}=1\)。
- 当 \(n_k=0\) 时，有 \(1\) 种情况：\(i_k=0\)。
- 当 \(n_k=1\) 时，有 \(2\) 种情况：\(i_k=0\) 或 \(i_k=1\)。
综上，若 \(n\) 的二进制数里有 \(k\) 个 \(1\)，答案就是 \(2^k\)。
标签：Lucas,dfrac,定理,个数,dbinom,mod From： https://www.cnblogs.com/stOtue/p/17532449.html