[ABC280E] Critical Hit 题解

· · 题解

前言

第一次赛时 10 分钟内切掉一道 E，感动。

解法

设 f_i 为把怪物的血量打到正好为 i 的期望次数。

很显然，边界条件 f_N=0；

由题意，可知每次攻击有 \frac{P}{100} 的概率血量 -2，即 f_i=f_{i+2}+1；有 1-\frac{P}{100} 的概率血量 -1，即 f_i=f_{i+1}+1；

整理得 f_i=\frac{P(f_{i+2}+1)}{100}+\frac{(100-P)(f_{i+1}+1)}{100}(1\le i<N)。

特别地，因为血量小于等于 0 即算胜利，所以定义 f_0 为血量小于等于 0 的期望次数，易得 f_0=f_1+1。

除法用乘法逆元实现即可。

放代码：


#include<bits/stdc++.h>
#define int long long // 记得开 long long
using namespace std;
const int mod=998244353;
main(){
  ios::sync_with_stdio(false);
  int n,p,inv=828542813; cin>>n>>p; // inv 为 mod 998244353 意义下 100 的逆元
  vector<int> a(n+1); a[n]=0;
  for(int i=n-1;~i;i--) // 往前倒推，注意处理边界情况
    a[i]=((i?(p*inv%mod*(i==n-1?0:a[i+2]+1))+((100-p)*inv%mod*(a[i+1]+1)):a[1]+1)%mod);
  cout<<a[0]<<endl;
  return 0;
}