首页 > Binary Vector
开通博客写题解
头像 TitanZhang
发表于 2020-07-27 21:00:30
题目大意 设A={0,1}，每天Roundgod从（即维度为n，每一位由01组成的所有向量的集合）中随机选择一个二进制向量。现在他想知道n天中选取n个线性独立向量的概率。设表示n的答案，最后输出 ， 表示异或。 线性独立是什么？（其实就是任意一个向量不能通过其他两个的“加减”运算得到）https: 展开全文
去ta的博客 赞 (13) 回复(2) 收起
头像 hnust_yangyanjun
发表于 2020-07-27 23:56:47
题意：随机n个n维01向量，询问这个n个向量线性无关的概率？ 思路：观察样例，我们发现f(i)初始为1，分子开始乘1，分母乘2，然后每次乘前一次乘的2倍+1，分母每次乘前一次的二倍。由于n<=2*10^7,所以我们打表。我们先打出f(i)的表，f(1)=1/2的逆元ans[1]=5000000 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 梁好问tanget90°
发表于 2020-07-28 20:05:55
原题链接：https://ac.nowcoder.com/acm/contest/5671/B 线性独立相关概念：https://baike.baidu.com/item/%E7%BA%BF%E6%80%A7%E7%8B%AC%E7%AB%8B 题目描述 设A={0,1}，某无聊透顶的神每 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 11D_Beyonder
发表于 2020-08-27 03:18:33
题目描述   Roundgod is obsessive about linear algebra. Let , everyday she will generate a binary vector randomly in . Now she wonders the probability of g 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 甜心小兔叽
发表于 2020-07-30 18:19:06
B. Binary Vector 传送门 题意：随机n个n维01向量，询问这个n个向量线性无关的概率 题解：  O(n) 维护2的幂和2的幂的逆元。 #include <bits/stdc++.h> using  展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 zjnu_tjq
发表于 2020-07-28 09:37:54
链接：https://ac.nowcoder.com/acm/contest/5671/B来源：牛客网 题意： 给你一个n，让你求出n个n维向量线性无关的概率，向量由0或1组成 solution： 找规律，找出f1 * 3/4=f2,f2 * 7/8=f3，所以 f_(n-1) * (2^n-1)/ 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”