题目 | Critical Hit - 颢天笔记

Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280)

E - Critical Hit

https://atcoder.jp/contests/abc280/tasks/abc280_e

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $500$ points

Problem Statement

There is a monster with initial stamina $N$ .
Takahashi repeatedly attacks the monster while the monster's stamina remains $1$ or greater.

An attack by Takahashi reduces the monster's stamina by $2$ with probability $\frac{P}{100}$ and by $1$ with probability $1 - \frac{P}{100}$ .

Find the expected value, modulo $998244353$ (see Notes), of the number of attacks before the monster's stamina becomes $0$ or less.

Notes

We can prove that the sought expected value is always a finite rational number. Moreover, under the Constraints of this problem, when the value is represented as $\frac{P}{Q}$ by two coprime integers $P$ and $Q$ , we can show that there exists a unique integer $R$ such that $R \times Q \equiv P (\mod 998244353)$ and $0 \leq R < 998244353$ . Print such $R$ .

Constraints

$1 \leq N \leq 2 \times 10^{5}$
$0 \leq P \leq 100$
All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $P$

Output

Find the expected value, modulo $998244353$ , of the number of Takahashi's attacks.

Sample Input 1

3 10

Sample Output 1

229596204

An attack by Takahashi reduces the monster's stamina by $2$ with probability $\frac{10}{100} = \frac{1}{10}$ and by $1$ with probability $\frac{100 - 10}{100} = \frac{9}{10}$ .

The monster's initial stamina is $3$ .
After the first attack, the monster's stamina is $2$ with probability $\frac{9}{10}$ and $1$ with probability $\frac{1}{10}$ .
After the second attack, the monster's stamina is $1$ with probability $\frac{81}{100}$ , $0$ with probability $\frac{18}{100}$ , and $- 1$ with probability $\frac{1}{100}$ . With probability $\frac{18}{100} + \frac{1}{100} = \frac{19}{100}$ , the stamina becomes $0$ or less, and Takahashi stops attacking after two attacks.
If the stamina remains $1$ after two attacks, the monster's stamina always becomes $0$ or less by the third attack, so he stops attacking after three attacks.

Therefore, the expected value is $2 \times \frac{19}{100} + 3 \times (1 - \frac{19}{100}) = \frac{281}{100}$ . Since $229596204 \times 100 \equiv 281 (\mod 998244353)$ , print $229596204$ .

Sample Input 2

5 100

Sample Output 2

3

Takahashi's attack always reduces the monster's stamina by $2$ . After the second attack, the stamina remains $5 - 2 \times 2 = 1$ , so the third one is required.

Sample Input 3

280 59

Sample Output 3

567484387

题解

题面分析

该题为一个非常基础的 DP + 模逆元题，只不过题面的 Notes 小节有点坑人，需要重点关注下~~（我就因为这被害了）~~

首先 Notes 中的变量 $P$ 与输入数据的变量 $P$ 是两个东西，不要把这俩当成同一个变量了，否则题目就看不明白了。

其次，要我们输出满足 $R \times Q \equiv P (\mod 998244353)$ 的 $R$ 是个啥东西。这个等式其实不要想复杂了，其实就是 $\frac{P}{Q}$ ，其中将除法运算改成用模逆元乘法运算即可。

分析后，问题就清晰了，题目就是让我们使用模逆元计算这个期望值罢了。

动态规划

我们约定 $d p_{i} :=$ 造成伤害 $i$ 需要的步数的期望。

易得 $d p_{0} = 0$ ， $d p_{1} = 1$ （每一步至少造成 $1$ 点伤害，因此只需 $1$ 步）

接下来的递推方式为：

$\begin{aligned} d p_{i} & = (d p_{i - 2} + 1) \cdot \frac{P}{100} + (d p_{i - 1} + 1) \cdot (1 - \frac{P}{100}) \\ = d p_{i - 2} \cdot \frac{P}{100} + d p_{i - 1} \cdot (1 - \frac{P}{100}) + 1 \end{aligned}$

具体解释，要达成 $i$ 点伤害，有两种情况：

前面达成了 $i - 2$ 点伤害，最后一步达成了 $2$ 点伤害，期望为 $(d p_{i - 2} + 1) \cdot \frac{P}{100}$
前面达成了 $i - 1$ 点伤害，最后一步达成了 $1$ 点伤害，期望为 $(d p_{i - 1} + 1) \cdot (1 - \frac{P}{100})$

模逆元

（关于模逆元：https://io.zouht.com/13.html）

原式转化为：

$d p_{i} = d p_{i - 2} \cdot P \cdot inv (100) + d p_{i - 1} \cdot (1 - P \cdot inv (100)) + 1$

可见只用的找 $100$ 的模逆元，完全可以直接算出来它的值为 $828542813$ .

代码

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

typedef long long ll;
const ll MOD = 998244353;
/* ll fastpow(ll a, ll b)
{
    a %= MOD;
    ll ans = 1;
    while (b)
    {
        if (b % 2 == 1)
            ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}
inline ll inv(ll x)
{
    return fastpow(x, MOD - 2);
} */
const ll MAXN = 2e5 + 10;
ll dp[MAXN];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll N, P;
    cin >> N >> P;
    // ll inv100 = inv(100);
    ll inv100 = 828542813;
    dp[1] = 1;
    for (int i = 2; i <= N; i++)
    {
        dp[i] = P * inv100 % MOD * dp[i - 2] % MOD +
                (1 - (P * inv100 % MOD) + MOD) % MOD * dp[i - 1] % MOD + 1;
        dp[i] %= MOD;
    }
    cout << dp[N] << endl;
    return 0;
}

题目 | Critical Hit