约瑟夫环

2020-牛客多校-6

 2020.07.27 20:09  2023.09.01 18:14  ACM  线性空间  约瑟夫环 󰈭 1092字

有坑待补具体数学约瑟夫的Ok做法 B 线性无关的n维01向量个数考虑每次加入元素时可取的元素个数。假设当前已经取了i个线性无关向量，则它们可以张出一共$2^i$个向量，所以第i + 1个向量只有$2^n - 2 ^ i$种可取办法。因而$f(n) = \prod_{i=0}^{n - 1}(2^n-2^i)/2^n$ 推导可得递推关系: $f(n) = (1 - 1/2^n)*f(n - 1)$ 线性处理出来O1查询即可。 ...