2020牛客暑期多校训练营第六场
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
比赛链接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}$$
阅读全文…
