大意: 给定01序列, 求随机交换k次后, 序列升序的概率.
假设一共$tot$个$0$, 设交换$i$次连续前缀$0$有$j$个的概率为$dp[i][j]$, 答案即为$\frac{dp[k][tot]}{\sum\limits_{i=0}^{tot}{dp[k][i]}}$
矩阵快速幂求出$dp[k][0]...dp[k][tot]$后即可得出答案.
Codeforces 1151F Sonya and Informatics (概率dp)
原文：https://www.cnblogs.com/uid001/p/10734772.html