题目描述
难度分:$1251$
输入$n(1 \leq n \leq 200000)$,$p(0 \leq p \leq 100)$
- 怪物的血量为$n$。
- 每次攻击,有$\frac{p}{100}$的概率会对怪物造成$2$点伤害,有$1-\frac{p}{100}$的概率会造成$1$点伤害。
让怪物血量$\leq 0$,攻击次数的期望是多少?
对答案进行分数取模,其中模数为$mod=998244353$。
输入样例$1$
3 10
输出样例$1$
229596204
输入样例$2$
5 100
输出样例$2$
3
输入样例$3$
280 59
输出样例$3$
567484387
算法
概率DP
题目比较典,一眼概率DP
。
状态定义
$f[i]$表示干掉血量为$i$的怪物的期望攻击次数。
状态转移
$base$ $case$:如果$i \leq 0$了肯定就不需要攻击了,$f[0]=0$。
一般情况:以$\frac{100-p}{100}$的概率让怪物掉两点血,或者以$\frac{p}{100}$的概率让怪物掉一点血,这两个事件都会耗费一次攻击,并且两者独立,是加法关系,因此有状态转移方程。
$f[i]=\frac{(1+f[i-1]) \times p}{100}+\frac{(1-f[i-2]) \times (100-p)}{100}$
由于需要分数取模,状态转移中的除法用逆元来计算。
复杂度分析
时间复杂度
从$n$递推到$0$,每个血量有两种扣血的策略,因此时间复杂度是线性的,为$O(n)$。
空间复杂度
开辟了$f$数组存各个血量的状态,额外空间复杂度为$O(n)$。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MOD = 998244353, N = 200010;
int f[N];
int n, p, d;
int fast_power(LL a, LL k, LL p) {
LL res = 1 % p;
while(k) {
if(k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
int inv(LL x) {
return fast_power(x, MOD - 2, MOD);
}
int dfs(int rest) {
if(rest <= 0) return 0;
int& v = f[rest];
if(v != -1) return v;
int res = (1ll + dfs(rest - 1)) * (100 - p) % MOD * d % MOD;
res = (res + (1ll + dfs(rest - 2)) * p % MOD * d % MOD) % MOD;
return v = res;
}
int main() {
d = inv(100);
scanf("%d%d", &n, &p);
memset(f, -1, sizeof f);
printf("%d\n", dfs(n));
return 0;
}