题目 分析 首先位运算没有进位,这样可以让它一位一位进行,如题所述,设 x x x表示 a i a_i ai的第 k k k位,当 l = = r l==r l==r的时候概率为 1 n 2 \frac{1}{n^2} n21,然后当 x = = 1 x==1 x==1时数学期望为 2 k n 2 \frac{2^k}{n^2} n22k。 Then,当 l < r l&l
做法1 参考BLOG 引理: 设 z e r o zero zero为0的个数.则 a n s ≤ m = z e r o 2 ans\le m=\dfrac {zero} 2 ans≤m=2zero.我们把下标划分成两个集合 L , R L,R L,R,其中 L L L集合内的元素左边的0的个数 ≤ m \le m ≤m. 原问题等价于每一个非0数如果成功和两边的0配对,那么答案+1.