线性基

常用结论

• 设 $B$ 中元素个数为 $S$，则 $B$ 可以表示出 $2^S$ 个不同的数 因为每个数可以选或不选
• 如果 $B$ 中存在第 $w$ 位为 $1$ 的数，则 $2^S$ 个数中恰好有 $2^{S-1}$ 个数第 $w$ 位为 $1$ 设第 $w$ 位为 $1$ 的数有 $k$ 个，则 $$2^{S-k}\times \sum _{i=0}^k\left(\genfrac{}{}{0ex}{}{k}{i}\right)[i\mathrm{mod}2=1]=2^{S-k}\times 2^{k-1}=2^{S-1}.$$