这题先预处理数组有多少个置换，，这样的话，每个置换最少要被选到一次，最多就是置换长度的次数，利用这些置换进行DP，和背包一样的，每个置换当成一个物品，选择的概率很容易算出，利用这点进行状态转移即可算出种数，最后在除上总情况数就可以算出概率
代码：
#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int N = 305;int t, n, k, a[N], w[N], wn, vis[N];double dp[N][N], C[N][N];int main() {for (int i = 0; i < N; i++) {C[i][0] = C[i][i] = 1;for (int j = 1; j < i; j++)C[i][j] = C[i – 1][j – 1] + C[i – 1][j];}scanf("%d", &t);while (t–) {scanf("%d%d", &n, &k);memset(vis, 0, sizeof(vis));for (int i = 1; i <= n; i++)scanf("%d", &a[i]);wn = 0;for (int i = 1; i <= n; i++) {if (vis[i]) continue;int u = a[i];int cnt = 0;while (!vis[u]) {vis[u] = 1;cnt++;u = a[u];}w[++wn] = cnt;}memset(dp, 0, sizeof(dp));dp[0][k] = 1;for (int i = 1; i <= wn; i++) {for (int j = 1; j <= w[i]; j++) {for (int x = j; x <= k; x++) {dp[i][x – j] += dp[i – 1][x] * C[w[i]][j];}}}double ans = dp[wn][0];for (int i = 0; i < k; i++)ans = ans * (i + 1) / (n – i);printf("%.4f\n", ans);}return 0;}
在认识你之后，我才发现自己可以这样情愿的付出……
