ED: Gem Island 题解

· · 题解

题目大意

题目解法

直接冲上去 dp 怎么看都不是很好做，考虑挖掘一点性质。

先看看对于一种最终状态 a_1, a_2, \ldots, a_n，其发生的方案数，我们可以分成两个部分：

第一步是将 d 天分给 n 个人，钦点这 d 天是谁手上的宝石数增加了：

\prod_{i=1}^{n}\binom{d-\sum_{j=1}^{i-1}(a_j-1)}{a_i-1}=\frac{d!}{\prod_{i=1}^{n}(a_i-1)!}

第二步是对于每一天，计算当天被钦定的人手上宝石数增加的方案数；事实上，在一个人手上的宝石第 i 次增加 1 的时候，这时候发生这种情况的方案数就一定是 i 种。则将 n 个人的方案数都乘起来，则可以认为是：

\prod_{i=1}^{n}(a_i-1)!

将两个部分乘起来，则我们可以得到一个令人兴奋的结论：对于任何一种最终状态，它发生的方案数都是 d!。这也就意味着，所有的最终状态发生的概率都是相等的！

那么我们就可以直接 dp 所有方案数以及这些方案的前 r 大的 a_i 的和就行了。

考虑一种经典的“搭楼梯”的 dp 方法：

我们维护类似这样一个“楼梯”状的东西：

***
******
******
********
********
********
**********
**********

考虑设 f_{i,j} 表示当前最高的“楼梯”有 i 列，“楼梯”里头 * 的总数为 j 的方案数。上面这个东西就是 f_{3,59} 的一种方案。

转移很简单，考虑在最高层加入一行，枚举这行里头有 k 个 *，然后从现有的 j 列里头选 k 列放到最左边，然后在这 k 行上面各加上一个 * 就是一种转移了。比如对上面的 f_{3,59}，枚举 k=2 的时候可以转移到 f_{2,61}，其转移系数为 \binom{3}{2}。转移之后的形态可以这么表示：

**          <--- 新增的行
***
******
******
********
********
********
**********
**********

将这个东西放到这个题中，我们可以将宝石对应成 *，每一列对应一个人就行了。

然后考虑计算所有方案的前 r 大的 a_i 的和。转化成上面的东西就变成了前 r 列的 * 的和。事实上也很简单，由于我们每次加入一行的那些列，一定就是前 k 大的列，而且每列都只加入了一个 *，所以我们可以直接计算贡献。具体来说，我们类比 f_{i,j} 设 g_{i,j} 为当前维护前 i 大，一共有 j 个宝石的所有方案的前 r 大的数的和。那么转移就可以写成：

g_{i,j}=\sum_{k=i}^{\min(n,i)}(g_{k,j-i}+\min(i, r) \times f_{k,j-i})\times \binom{k}{i}

最后答案也很显然，就是

\frac{\sum_{i=1}^{n}g_{i,d}}{\sum_{i=1}^{n}f_{i,d}}

了。

由于此题比较神必，所以全上 double 就行了。

Code：(实际写的转移可能和上面叙述的有一点点小区别，本质一样）

typedef long long ll;
typedef double db;

db f[1010][1010];
db g[1010][1010];
db C[1010][1010];

int main() {
    int n = ri, d = ri, r = ri;

    C[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        C[i][0] = 1;
        for(int j = 1; j <= i; j++)
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    }

    f[0][n] = 1;
    for(int i = 0; i < d; i++)
        for(int j = 1; j <= n; j++)
            for(int k = 1; k <= j; k++) {
                f[i + k][k] += f[i][j] * C[j][k];
                g[i + k][k] += (g[i][j] + min(r, k) * f[i][j]) * C[j][k];
            }

    db G = 0, F = 0;
    for(int i = 1; i <= n; i++)
        G += g[d][i], F += f[d][i];

    printf("%.8lf\n", G / F + r);

    return 0;
}