2020牛客暑期多校训练营第六场
比赛链接
https://ac.nowcoder.com/acm/contest/15880?&headNav=www
B Binary Vector
题意
随机n个n维01向量，询问这个n个向量线性无关的概率
题解
考虑第一个向量，可以有$2^n-1$选择，你不可以选择全为0的向量
然后考虑与第一个向量线性无关的向量，可以有$2^n-2^1$个，因为第一个向量的0倍和1倍不能选。
然后考虑与第一个和第二个向量线性无关的向量，可以有$2^n-2^2$个
于是最终的方案数为$\begin{aligned}\prod_{i=0}^{n}2^n-2^i\end{aligned}$ ， 考虑分母为$2^{n\cdot n}$
$$
\begin{aligned}
&\frac{\begin{aligned}\prod_{i=0}^{n-1}2^n-2^i\end{aligned}}{2^{n\cdot n}}
\&=\begin{aligned}\prod_{i=0}^{n-1}1-\frac{2^i}{2^n}\end{aligned}
\&=\begin{aligned}\prod_{i=1}^{n}1-2^{-i}\end{aligned}
\end{aligned}
$$
