题解 P6858 【深海少女与胖头鱼】

· · 题解

这道题目是一道计算期望的题目，但是不要害怕，只要先从特殊情况入手，就不难了，而对于这道题来说，就可以先从 m=0,1 的情况入手。

设 f(n,m) 为有 n 个带护盾的和 m 个不带护盾的胖头鱼。

当 m=0 时，由于没有不带护盾的胖头鱼了，所以只能打有护盾的胖头鱼。

f(n,0)=f(n-1,1)+1

当 m=1 时，如果攻击一个有护盾的，那么原来没盾的就会有盾，所以有

f(n,1)=\dfrac{n}{n+1}\times f(n,1)+\dfrac{1}{n+1}\times f(n,0)+1

继续推，则有

f(n,1)=\dfrac{n}{n+1}\times f(n,1)+\dfrac{1}{n+1}\times f(n-1,1)+\dfrac{n+2}{n+1} (n+1)\times f(n,1)=n\times f(n,1)+f(n-1,1)+n+2 f(n,1)=f(n-1,1)+n+2

这个显然可以用一个二次函数来表示 f(n,1)，代入特殊值后，可得 f(n,1)=(n^2+5n+2)/2，这样，这种情况就解决了。

令 g(n)=f(n,1)=(n^2+5n+2)/2，考虑一般情况。

当 m>1 时，有

f(n,m)=\dfrac{n}{n+m}\times f(n+m-1,1)+\dfrac{m}{n+m}\times f(n,m-1)

进一步，得

f(n,m)=\dfrac{n}{n+m}\times g(n+m-1)+\dfrac{m}{n+m}\times f(n,m-1)

这样，最终得到：

f(n,m)=\begin{cases}g(n-1)+1&(m=0)\\g(n)&(m=1)\\\dfrac{n}{n+m}\times g(n+m-1)+\dfrac{m}{n+m}\times f(n,m-1)&(m>1) \end{cases}

然后记住随时取模即可。

递归版代码如下：

#include<cstdio>
#define ll long long
using namespace std;
const ll MOD = 998244353;
ll quickpow(ll a, ll b) {ll res = 1; for (; b; b >>= 1, a = a * a % MOD) if (b & 1) res = res * a % MOD; return res;}
ll calc(ll x) {return ((x * x + x * 5 + 2) / 2) % MOD;}
ll f(ll n, ll m) {
    if (!m) return (f(n - 1, 1) + 1) % MOD; if (m == 1) return calc(n);
    return ((n * quickpow(n + m, MOD - 2)) % MOD * calc(n + m - 1) % MOD + (m * quickpow(n + m, MOD - 2)) % MOD * f(n, m - 1) + 1) % MOD; 
}
ll n, m;
int main() {
    scanf("%lld%lld", &n, &m);
    return 0 & printf("%lld", f(n % MOD, m));
}

非递归版代码如下：

#include<cstdio>
#define ll long long
using namespace std;
const ll MOD = 998244353;
ll quickpow(ll a, ll b) {ll res = 1; for (; b; b >>= 1, a = a * a % MOD) if (b & 1) res = res * a % MOD; return res;}
ll calc(ll x) {return ((x * x + x * 5 + 2) / 2) % MOD;}
ll frac(ll x, ll y) {return (x * quickpow(y, MOD - 2)) % MOD;}
ll n, m, ans;
int main() {
    scanf("%lld%lld", &n, &m), n %= MOD, ans = calc(n);
    if (!m) return 0 & printf("%lld", (calc(n - 1) + 1) % MOD);
    for (ll i = 2; i <= m; ++i) ans = (frac(n, n + i) * calc(n + i - 1) + frac(i, n + i) * ans + 1) % MOD;
    return 0 & printf("%lld", ans);
}