#数学期望#洛谷 6858 深海少女与胖头鱼

题目

---

分析

设(dp[n][m])表示带盾(n)条不带盾(m)条的期望杀死次数，那么

[dp[n][m]=frac{m}{n+m}dp[n][m-1]+frac{n}{n+m}dp[n+m-1][1]+1 ]

然而它是有后效性的，考虑特殊值，

[dp[n][0]=dp[n-1][1]+1,dp[n][1]=frac{1}{n+1}dp[n][0]+frac{n}{n+1}dp[n][1]+1 ]

那么

[dp[n][1]=dp[n-1][1]+n+2=frac{(n+1)(n+4)-2}{2} ]

可以发现前面递推的式子所谓的后效性可以快速求出，那么就有了(O(m))的代码

---

代码

#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
typedef long long lll;
const int mod=998244353; lll n,m;
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
inline lll ksm(lll x,lll y){
	rr lll ans=1; x%=mod;
	for (;y;y>>=1,x=1ll*x*x%mod)
	    if (y&1) ans=1ll*ans*x%mod;
	return ans;
}
inline lll f(lll n){
	if (n&1) return (((n+1)>>1)%mod*((n+4)%mod)%mod+mod-1)%mod;
		else return (((n+4)>>1)%mod*((n+1)%mod)%mod+mod-1)%mod;
}
inline lll Dp(lll n,lll m){
	if (!n&&!m) return 0;
	if (!m) return Dp(n-1,1)+1;
	if (m==1) return f(n);
	return (ksm(n+m,mod-2)*(m*Dp(n,m-1)%mod+n%mod*f(n+m-1)%mod)+1)%mod;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	return !printf("%lld",Dp(n,m));
}