C++写Mr. Wor's router at home is broken again. After some repairs, he needs to reconnect the Ethernet cables to the router. It is known that Mr. Wor's router has n ports, and there are n Ethernet cables. Then, Mr. Wor will sequentially insert the i -th Ethernet cable to the i -th port, for all i from 1 to n . However, due to Mr. Wor's mysterious actions, the first m cables were not inserted into their designated ports, but were inserted into m ports uniformly at random. For the remaining cables, when cable i is being inserted, if port i is not occupied, then cable i will be inserted into port i . Otherwise, cable i will be inserted into a randomly chosen unoccupied port. Mr. Wor wants to know the probability that the last cable, cable n , is plugged into port n . Input Only one line contains two integers n,m(1≤n≤10,0≤m≤n) , denoting the number of cables and the number of cables which was inserted randomly. Output Print the probability in one line. Your answer is considered correct if the relative or absolute error is less than or equal to 10−6 . Example inputCopy 3 1 outputCopy 0.5000000000

以下是C++代码实现：

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 15;

double f[MAXN][1 << MAXN];
int n, m;

int main() {
    cin >> n >> m;
    f[0][0] = 1.0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < (1 << n); j++) {
            int cnt = 0;
            for (int k = 0; k < n; k++) {
                if (j & (1 << k)) cnt++;
            }
            if (cnt <= i - m - 1) {
                f[i][j] += f[i - 1][j] * (i - cnt - 1);
            } else {
                for (int k = 0; k < n; k++) {
                    if (j & (1 << k)) {
                        f[i][j] += f[i - 1][j ^ (1 << k)];
                    }
                }
            }
            f[i][j] /= i;
        }
    }
    printf("%.10lf\n", f[n][(1 << n) - 1]);
    return 0;
}

注释：

1.数组f[i][j]表示前i个插头中，有状态j的概率。

2.状态j中二进制位为1的个数表示已经插上插头的数量。

3.若插头数量小于等于m，则第i个插头有i-1种选择，因此f[i][j] += f[i - 1][j] * (i - cnt - 1)。

4.否则，第i个插头有两种选择：插到空闲的位置或者插到已经有插头的位置。

5.如果插到空闲位置，有i-cnt种选择；如果插到有插头的位置，那么就是状态j去掉其中一个位置的状态，即f[i][j] += f[i - 1][j ^ (1 << k)]。

6.最后别忘了除以i，表示第i个插头插到哪个位置的概率是1/i。

7.答案就是f[n][(1 << n) - 1]，表示前n个插头都插上的概率。