尽管是一道E题，但真心并不很难~不难发现，有一些物品是一定要被选择的，我们所需要决策的仅仅只有那几个有重复价值的物品。
而不同名字之间的概率并不互相影响，所以我们有 \(f[i][j]\) 表示名字为 \(i\) 的物品呼唤 \(j\) 次恰好获得前 \(j\) 大的价值的物品的概率。转移方程为：
\(f[i][j] = f[i][j - 1] * j * \frac{1}{a[i][0]−j+1}\)
为什么要\(*j\) 呢？因为这第 \(j\) 个物品的排列顺序并不是固定的。
要把这 \(n\) 个物品结合起来，我们可以再建立一个 dp 数组，\(g[i][[j]\) 表示前 \(i\) 个名字中，呼唤得到恰好 \(j\) 个有重复价值的物品。我们有转移方程：
\(g[i][j] = \sum g[i - 1][j - 1] * f[i][rec[j] +1]\)
与 \(g[i][j] = \sum g[i - 1][j] * f[i][rec[i]]\)
以上两个分别表示当前名字是否呼唤到一个重复价值的物品。
有没有感觉到有什么不对？没错，在计算的时候，我们的 \(f[i][k]\) 前面是没有带系数的，也就是我们并没有去统计以这样的方式去呼唤的概率是多少。但题目中明确说明当有几种可能呼唤到最高价值的物品时，我们会等概率的任选一种。所以我们可以考虑算出总的方案数 \(c[i][j]\) ，然后再除去这个方案数，即 \(ans =\frac{g[m][cnt]}{c[m][cnt]}\)。这个的转移很简单，可以看一下代码。表面 \(n ^{3}\) ，但第二维的枚举总数限定了范围，所以完全可以承受。
不过我也很好奇……为什么 \(c[i][j]\) 一定要开 double 类型呢？不开就WA了……求解释呀，有知道的还请回复我，私信也可以呀！感激不尽QAQ
#include <bits/stdc++.h> using namespace std; #define maxn 2500 #define db long double int n, m, tot, cnt, rec[maxn]; int a[maxn][maxn], b[maxn]; db f[maxn][maxn], g[maxn][maxn], c[maxn][maxn];int read() {int x = 0, k = 1;char c; c = getchar();while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * k; }bool cmp(int x, int y) { return x > y; } void Up(db &x, db y) { x = x + y; }int main() {n = read(), m = read();for(int i = 1; i <= m; i ++){a[i][0] = read();for(int j = 1; j <= a[i][0]; j ++)a[i][j] = read(), b[++ tot] = a[i][j];sort(a[i] + 1, a[i] + 1 + a[i][0], cmp);}sort(b + 1, b + 1 + tot, cmp);for(int i = n; i; i --)if(b[i] == b[i - 1]) cnt ++;else break;cnt += 1; int K = b[n]; c[0][0] = 1;for(int i = 1; i <= m; i ++){f[i][0] = 1;for(int j = 1; j <= a[i][0]; j ++){if(a[i][j] < K) break; if(a[i][j] > K) rec[i] = j;f[i][j] = (db) f[i][j - 1] * (db) j * ((db) 1 / (db) (a[i][0] - j + 1));}}for(int i = 1, tem = 0, up = 0; i <= m; i ++){int r1 = 0;for(int j = 0; j <= up; j ++) c[i][j] = c[i - 1][j]; for(int j = rec[i] + 1; j <= a[i][0]; j ++){if(a[i][j] < K) break;int t = j - rec[i]; r1 ++; for(int k = 0; k <= up; k ++)c[i][k + t] = (c[i][k + t] + c[i - 1][k]);}up += r1;}g[0][0] = 1;for(int i = 1; i <= m; i ++)for(int j = 0; j <= cnt; j ++){if(j) Up(g[i][j], g[i - 1][j - 1] * f[i][rec[i] + 1]);Up(g[i][j], g[i - 1][j] * f[i][rec[i]]);}cout << fixed << setprecision(10) << (g[m][cnt] / (db) c[m][cnt]) << endl;return 0; }