大意: 给定01序列, 求随机交换k次后, 序列升序的概率.
假设一共$tot$个$0$, 设交换$i$次后前$tot$个数中有$j$个$0$的方案数为$dp[i][j]$, 答案即为$frac{dp[k][tot]}{sumlimits_{i=0}^{tot}{dp[k][i]}}$
矩阵快速幂求出$dp[k][0]...dp[k][tot]$后即可得出答案.
大意: 给定01序列, 求随机交换k次后, 序列升序的概率.
假设一共$tot$个$0$, 设交换$i$次后前$tot$个数中有$j$个$0$的方案数为$dp[i][j]$, 答案即为$frac{dp[k][tot]}{sumlimits_{i=0}^{tot}{dp[k][i]}}$
矩阵快速幂求出$dp[k][0]...dp[k][tot]$后即可得出答案.