---
title: ABC_280_E - Critical Hit
tags: 題單
disqus: hackmd
---

# ABC_280_E - Critical Hit

[題目連結](https://atcoder.jp/contests/abc280/tasks/abc280_e)

題目大意：
原來有個數 $N$，每次操作有 $1-\frac{p}{100}$ 的機會少 $1$，$\frac{p}{100}$ 的機會少 $2$
請問使 $N$ 變為 $0$ 的操作次數期望值是多少

注意事項：
- 請將答案$\mod 998244353$ 後輸出

## 解法

[官方解答](https://atcoder.jp/contests/abc280/editorial/5342)

人生第一次自己想出期望值 DP 的解法 ~~雖然這題很簡單~~
再加上人生第一次用上費馬小定理

~~兩個人生的第一次都奉獻給它了~~
所以寫個文章來紀念一下

### DP 轉移式

因為會改變的是數字，所以我用**到每個數字的期望步驟數**來做 DP

從操作的規則來看可以知道一個數 $N$ 的轉移點是 $N-1$ 和 $N-2$
而 $N = 1$ 時必定會在下一步變成 $0$

所以經過一陣通靈，得到了下面的轉移式

$\begin{cases}
dp_0 = 0 \\
dp_1 = 1 \\
dp_i = 1 + dp_{i-1} \times (1-\frac{p}{100}) + dp_{i-2} \times \frac{p}{100} \ (2 \le i \le N)
\end{cases}$

只要跟著做就行了

### 關於 mod

可想而知這樣 DP 出來的數會很大
所以題目要我們$\mod 998244353$ 後再輸出

但我們在計算 DP 中會用到除法
而 mod 運算中無法定義除法
所以需要用到[模反元素](https://zh.wikipedia.org/zh-tw/模反元素)來代替除法

模反元素大概的定義：
$a \equiv a^{-1} \mod P$
其中 $a$ 與 $a^{-1}$ 互為模反元素且 $a$ 與 $P$ 互質

而 mod 運算中的除法就需要改成乘以模反元素

所以在 mod 質數的情況下我們可以任何數做除法（也就是乘以模反元素）
因為質數與自己和 1 以外比自己小的任何數都互質

### 這題的 mod

這題 mod 的數為質數，所以不需要擔心不能除的問題

接著看一下運算式，我們從頭到尾都只有除 100
所以我們只需要把 100 的模反元素找出來就可以了

### 找模反元素

模反元素有多種找法，我這裡用的是[費馬小定理](https://zh.wikipedia.org/zh-tw/费马小定理)求 $a^{P-2}$ 也就是 $a^{998244351}$

使用[快速冪](https://zh.wikipedia.org/zh-tw/平方求幂)來求解可以得到 $100^{-1} = 828542813 \mod 998244353$

然後在每個除以 100 的地方都改成乘以 828542813 就大功告成了

這裡附上我寫的解：

#include <bits/stdc++.h>
 
using namespace std;
#define ll long long
#define N 200005
#define oo 0x3f3f3f3f
#define ool 0x3f3f3f3f3f3f3f3f
#define P (int)(998244353)
#define F first
#define S second
#define pii pair<int, int>
#define lowbit(x) (x&-x)

ll inv_ten = 828542813;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	ll p;
	cin >> n >> p;

	ll dp[N] = {0};
	dp[1] = 1;
	for(int i=2; i<=n; i++){
		dp[i] = 1;
		dp[i] += (dp[i-1] * (100 - p) % P) * inv_ten % P;
		dp[i] += (dp[i-2] * p % P) * inv_ten % P;
		if(dp[i] > P)
			dp[i] %= P;
	}
	cout << dp[n] << endl;

		
    return 0;
}