印象最深的一次做的概率dp是今年牛客多校第一场的铜牌题，那次突然意会到了最优操作，然后和队友一提，dp的式子就推出来了。。但是后来就很少有当时那么好的状态的了。。。

回到本题，题意：无序的01序列中，每次如同猴子敲键盘一样随机选两个位置，如果他们逆序，则交换，问最终排序的期望次数。

做法：每次随机的选一对，有n * (n - 1)对可供选择，假设有cnt个1占了0的位置，那么对应也有cnt个0占了1的位置，有效的交换就有cnt * cnt ，所以一次正确交换的概率是 cnt * cnt / (n * (n - 1) / 2)。概率是1/p，那么期望就是p。

设f(i)是解决了i对的期望次数，那么f(i) = f(i - 1) + 本次期望

链接： Wish I Knew How to Sort

int f[N], a[N], b[N];
int qpow (int x, int n)
{
    int ret = 1;
    while (n) {
        if (n & 1) ret = ret * x % mod;
        x = x* x % mod;
        n >>= 1;
    }
    return ret;
}
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) 
    {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] ^ b[i]) cnt++; 
    }
    cnt /= 2;
    for (int i = 0; i <= cnt; i++)
    {
        int k = qpow(i, mod - 2);
        f[i] = f[i - 1] + (n * (n - 1) / 2) % mod * k % mod * k % mod;
        f[i] %= mod;
    }
    cout << f[cnt] << "\n";
}