题意：随机的给你k个数，范围1~n，问你使得区间[1, n]的每个数都出现至少两次的期望次数。
思路：f[i][j] 表示有i个数需要出现一次，j个数需要出现两次，那么：
f[i][j] = i / n * f[i - 1][j] + j / n * f[i + 1][j - 1] + (n - i - j) / n * f[i][j] + 1
f[i][j] = i / (i + j) * f[i - 1][j] + j / (i + j) * f[i + 1][j - 1] + n / (i + j)
这题多样例要记忆化一下否则会超时，但是n不同会导致结果不同，所以把n提出来
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 3e3 + 10; double f[maxn][maxn]; int vis[maxn]; int n; double calc(int i, int j) { if(i == 0 && j == 0) return 0; if(f[i][j]) return f[i][j]; f[i][j] = 1; if(i > 0) f[i][j] += i * calc(i - 1, j); if(j > 0) f[i][j] += j * calc(i + 1, j - 1); f[i][j] = f[i][j] / (i + j); return f[i][j]; } int main() { int t; scanf("%d", &t); while(t--) { memset(vis, 0, sizeof(vis)); int k, x; scanf("%d%d", &n, &k); for(int i = 1; i <= k; ++i) scanf("%d", &x), vis[x]++; int cnt1 = 0, cnt2 = 0; for(int i = 1; i <= n; ++i) { if(vis[i] == 1) cnt1++; else if(vis[i] == 0) cnt2++; } printf("%.10f\n", n * calc(cnt1, cnt2)); } return 0; }
