题目大意
给定一个长为 $n$（$2 le n le 100$）的01串 $S$ 。对 $S$ 进行 $k$（$1 le k le 10^9$）次操作：等概率地选取两个下标 $i, j$（$1 le i < j le n$），交换 $S[i], S[j]$ 。问最后 $S$ 单调不减的概率。
复盘
想偏了。
我往逆序对数的方向思考，但是维护逆序对数并不容易。
正解
DP。
状态描述：有多少个 0「不在其位」。
设 $S$ 中有 $m$ 个 0，那么不在前 $m$ 个位置上的 $0$ 就是不在其位的。
Key observation：最多有 $min(m, n - m)$ 个 0 不在其位。
Another observation：不在其位的 0 与不在其位的 1 个数相等。
令 $(i, j)$ 表示状态：前 $i$ 次操作过后有 $j$ 个 0 不在其位。
状态 $(i, j)$ 可能转移到 $(i+1, j), (i+1,j + 1), (i + 1, j - 1)$ 。
令 $f[i][j]$ 表示到达转态 $(i,j)$ 的概率。
$f[i][j]$ 的转移系数只依赖于 $j$，因此可以写出转移矩阵。分析至此，题目化为矩阵快速幂。