CF1753C
首先求出整个数列有多少个0,设为sum0,再求出\(1--sum0\)中有多少个1,设为\(sum1\)
显然,我们的目标就是把\(1--sum0\)中全部变成0
那么考虑有意义的一步的期望次数,由于线性性,可以全部加起来
设左边还有x个1(左边就是\(1--sum0\))
交换到的概率为\(\dfrac{x^2}{n(n+1)/2}\),那么期望就取个倒数。
然后从sum1开始从高往低累加即可
CF1753D
操作的实质就是把一个非空位置变成空,把一个空的位置变成非空
那么完成的条件就是把两个空格换到一起
那么就可以根据操作建图,然后跑最短路即可
CF1750F
首先我们考虑一个不能被消除的序列,它一定是1,0段交替拼接的,而且0段的长度大于相邻的两个1段的长度
那么考虑dp+容斥