尽管是一道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 
     
      using namespace std;#define maxn 2500#define db long doubleint 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;}