题目描述

难度分:$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;
}