自动搬运

查看原文

来自洛谷，原作者为

	Inlay1158 **

搬运于2025-08-24 22:24:38，当前版本为作者最后更新于2020-10-20 20:55:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这道题目是一道计算期望的题目，但是不要害怕，只要先从特殊情况入手，就不难了，而对于这道题来说，就可以先从 $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);
}