洛谷P6858 深海少女与胖头鱼 题解

发表于 | 分类于

题意：
总共有 $n$ 条带 「圣盾」的「胖头鱼」和 $m$ 条不带圣盾的胖头鱼，每次等概率对一条存活的胖头鱼造成「剧毒」伤害。
求期望造成多少次伤害可以杀死全部胖头鱼。
「圣盾」：当拥有圣盾的胖头鱼受到伤害时，免疫这条鱼所受到的本次伤害。免疫伤害后，圣盾被破坏。
「胖头鱼」：在一条胖头鱼的圣盾被破坏后，给予其他所有没有死亡且没有圣盾的胖头鱼圣盾。
「剧毒」：立即杀死没有圣盾的胖头鱼。
$n \leq 10^{14} , m \leq 10^6$

设 $f_{i,j}$ 表示有 $i$ 个带圣盾的胖头鱼和 $j$ 个不带圣盾的胖头鱼

分两种情况

一种是你破坏了一个有圣盾的胖头鱼的圣盾，于是有圣盾的胖头鱼有 $i+j-1$ 条，没有圣盾的胖头鱼只有一条，也就是刚刚被破坏掉圣盾的那条

另一种是你杀死了一个没有圣盾的胖头鱼，那样没有圣盾的胖头鱼少了一条，有圣盾的胖头鱼没发生影响

列出 dp 转移式：$f_{i,j}=\dfrac{i}{i+j}f_{i+j-1,1}+\dfrac{j}{i+j}f_{i,j-1}+1$

然而我们发现 $n \leq 10^{14} , m \leq 10^6$，所以直接 dp 的话那 $i+j-1$ 最大会是……？

所以我们要把 $f_{i+j-1,1}$ 处理一下

考虑一下 $f_{i,1}$ 怎么求

把这个东西套到 dp 式子里面

可以得到 $f_{i,1}=\dfrac{i}{i+1}f_{i,1}+\dfrac{1}{i+1}f_{i,0}+1$

发现等式两边都有 $f_{i,1}$，那么移项

$\dfrac{1}{i+1}f_{i,1}=\dfrac{1}{i+1}f_{i,0}+1$

两边同乘 $(i+1)$

$f_{i,1}=f_{i,0}+i+1$

这下又出来个 $f_{i,0}$

然后我们再使用 dp 转移式：$f_{i,0}=f_{i-1,1}+1$

把它代入一下

$f_{i,1}=f_{i-1,1}+i+2$

这显然就是一个等差数列求和

还有初始条件 $f_{0,1}=1$

直接套公式可得

$f_{i,1}=2i+1+\dfrac{i(i+1)}{2}$

这样就求出了 $f_{i,1}$

$f_{i,0}$ 就也很好求了，它就是 $2i+\dfrac{i(i-1)}{2}$

然后我们回 dp 式子再看一下

$f_{i,j}=\dfrac{i}{i+j}f_{i+j-1,1}+\dfrac{j}{i+j}f_{i,j-1}+1$

还有一项 $f_{i,j-1}$

注意到第一维都是 $i$ 不变，所以直接枚举 $j$ 递推

复杂度 $O(m \log mod)$，其中 $mod$ 为模数，如果线性求逆元是可以做到 $O(m)$ 的。

最后一点就是上来就把 $n$ 给取模，显然这样对答案不会产生影响，还不会爆long long（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int f[1000010];

const int mod = 998244353;

inline ll qpow(ll a, ll p) { // a ^ p = ?
    ll w = 1LL;
    while(p) {
        if(p & 1) w *= a, w %= mod;
        a *= a, a %= mod;
        p >>= 1;
    }
    return w % mod;
} 

int calc0(ll n) {
    n %= mod;
    return ((n << 1) + (n * (n - 1) >> 1) % mod) % mod;
}

int calc1(ll n) {
    n %= mod;
    return ((n << 1) + 1 + (n * (n + 1) >> 1) % mod) % mod;
}

int main() {
    long long n, m; cin >> n >> m;
    n %= mod;
    if(m == 0) {
        cout << calc0(n) << endl;
        return 0;
    }
    if(m == 1) {
        cout << calc1(n) << endl;
        return 0;
    }
    f[0] = calc0(n);
    f[1] = calc1(n);
    for(register int i = 2; i <= m; i++) {
        ll inv = qpow(n + i, mod - 2);
        f[i] = ((n * calc1(n + i - 1) % mod + 1ll * i * f[i - 1] % mod) * inv + 1ll) % mod;
    }
    cout << f[m] << endl;
    return 0;
}