题意描述
给你一个 01 串，每次可以选择两个数字，当 aia iai>>>aja jaj时进行交换， 反之不交换，无论交不交换都计入次数，让你求使得该串有序（从小到大）的期望次数。
思路
我们将串中数字000 个数记为 cntcntcnt 。
观察题意发现，我们只需要将前 cntcntcnt 个数字全部交换成 000 即可，且前 cntcntcnt 个数字已经出现了$ w 个 0 $时，无论如何交换，都不会使得情况更劣（即不会出现 000 的个数变少的情况，原因见题意加粗部分）。
我们用 fif ifi表示前 cntcntcnt 个数字中有 iii 个数字为 000 的期望。
那么，问题就转化成了使得前 cntcntcnt个数字中多一个000 (当前已有 i−1i−1i−1 个 000 )，期望的选择次数是多少？
我们知道，所有可能的交换方案数为：Cn2C n2Cn2，而只有前 cntcntcnt 个数中的 111 和后 n−cnt+1n−cnt+1n−cnt+1 个数中的 000 交换有意义。所以答案是
(cnt−i+1)2(cnt−i+1) 2(cnt−i+1)2Cn2C n 2Cn2。
那么 fff 数组的转移方程就是：
fi =fi−1 + f i =f i−1 + fi =fi−1 + (cnt−i+1)2(cnt−i+1) 2(cnt−i+1)2 Cn2 C n 2 Cn2
code:
