牛客等级之题N1（8.3场）题解

基础期望练习题。

考虑设 $f_i$ 表示第 $i$ ***作后剩余黑球期望个数。令 $q=\frac{n+m}{n+m+1}$ ， $f_0=n$ ，根据期望的线性性，则有：

$f_{i+1}=q(f_i+p)$

因为每次操作的时候，有 $p$ 的概率加入一个黑球，加上第 $i$ 轮期望剩下 $f_i$ 个黑球，则现在期望剩下 $f_i+p$ 个黑球。

然后考虑扔掉一个球后，每个黑球都有 $q$ 的概率被留下，所以期望剩下 $q(f_i+p)$ 个黑球。

得到递推式之后，我们可以得到如下两个做法：

迭代法：

$\begin{aligned} f_{i+1}&=q(f_i+p)\\ &= q(q(f_{i-1} + p) + p)\\ &= q^2f_{i-1} + q^2p + qp\\ &= q^3f_{i-2} + q^3p + q^2p + qp\\ &= \ldots\\ &= q^{i+1}f_0+\sum_{j=1}^{i+1}q^jp\\ &= q^{i+1}f_0+\frac{1-q^{i+1}}{1-q}qp \end{aligned}$

注意到答案为 $f_k$ ，则所求即为： $q^kn+\frac{1-q^k}{1-q} qp$ 。

组合意义法

考虑上面所述的组合意义，注意到每个球如果经历过 $i$ 次操作的第 $2$ 步，则最后有 $q^i$ 的概率被留下来。

则不难得到：

$\begin{aligned} Ans &= q^kn + q^kp+q^{k-1}p+\ldots+qp\\ &= q^kn+\frac{1-q^k}{1-q}qp \end{aligned}$

部分代码：

const int mod = 1e9 + 7;

inline int fsp(int x, int k = mod - 2) {
    int s = 1;
    while(k) {
        if(k & 1) s = 1LL * s * x % mod;
        x = 1LL * x * x % mod, k >>= 1;
    } return s;
}

int main() {
    int n, m, k, a, b;
    cin >> n >> m >> k >> a >> b;
    int p = 1LL * a * fsp(b) % mod;
    int q = 1LL * (n + m) * fsp(n + m + 1) % mod;
    int pw = fsp(q, k), iv = 1LL * (pw - 1) * fsp(q - 1) % mod;
    cout << (1LL * pw * n + 1LL * p * iv % mod * q) % mod << endl;
    return 0;
}