期望DP

所谓期望DP，就是计算某一个事件的期望废话。区别于概率DP（还不会的出门左转），期望DP是从结尾状态往前计算。
以这题举例，具体的做法如下：
1.怪物剩$0$点血时只需要$0$次攻击就可以击败废话x2
2.怪物剩$i$点血时可能下一次攻击$2$点血亮，或者$1$点。那么期望值就是

具体实现间代码。

AC CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,P=998244353;
int qpow(int a,int b)
{
	int res=1;
	for(;b;b>>=1,a=a*a%P)if(b&1)res=res*a%P;
	return res;
}
int f[N],n,p;
signed main()
{
	scanf("%lld%lld",&n,&p);
	f[0]=0;
	int _100=qpow(100,P-2);
	for(int i=1;i<=n;i++)
	{
		f[i]=((f[i-2]*p%P+f[i-1]*(100-p)%P)%P*_100%P+1)%P;
	}
	printf("%lld\n",f[n]);
	return 0;
}

还不会？等着$scy$讲课吧~~~