题目大意
一个人有n条命,你有p%的概率一次打它两条命,有(100-p)%的概率一次打他一条命
求你打死它需要的次数的期望值
思路
其实也就和走台阶的那个题目是一样的,用dp写就行了
每一次只会打一点血或者两点血,也就上从上面两个状态进行转移就可以了
f[i] = f[i-2]*p/100 + f[i-1]*(100-p)/100
只需要对这个值进行求逆元就可以了
代码
#include <bits/stdc++.h>
using namespace std;
const int M=2e5+5;
#define int long long
const int mod=998244353;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int kpow(int a,int b) {
int ans=1;
while(b) {
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
int f[M];
signed main() {
int n=read(),p=read();
f[0]=0;
f[1]=1;
//从哪里转移过来的概率
for(int i=2;i<=n;i++)
f[i]=(1+(f[i-2]*p+f[i-1]*(100-p))%mod*kpow(100,mod-2)%mod)%mod;
cout<<f[n];
return 0;
}
标签:abc,--,int,ch,read,280,100
From: https://www.cnblogs.com/basicecho/p/16949571.html