Lucas 定理(证明)
A、B是非负整数,p是质数。AB写成p进制:A=a[n]a[n-1]...a[0],B=b[n]b[n-1]...b[0]。
则组合数C(A,B)与C(a[n],b[n])*C(a[n-1],b[n-1])*...*C(a[0],b[0]) mod p 相同
即:Lucas(n,...
De Morgan's Laws
Lemma 1: \((\bigcup_n S_n)^c=\bigcap_n S_n^c\)
Proof for Lemma 1:
\[\because \forall x \in (\bigcup_n S_n)^c, x \notin \bigcup_n S_n, \therefore x \notin S_i, \forall i \in \{1,2,\...