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} \]
