解法 1-a. 期待値の差分に注目する解法

以下では、\(X\) だけ体力を減らす事を \(X\) だけダメージを与えたとよぶ事にし、与えたダメージの総和が \(k\) 以上となるまでに必要な攻撃回数の期待値を \(a_k\) で定義します。
例を挙げると、 \(a_0=0\), \(a_1=1\), \(a_2=2-\frac{p}{100}\) となります。

また、この期待値を考える上で高橋君は \(N\) 以上ダメージを与えた後も攻撃を止める事はないとしても問題ないため、以下ではそのように考えます。 求めたいのものは \(a_N\) です。

まず、\(a_{i+1}-a_i\) について考えます。高橋君の各攻撃におけるダメージ与え方の列それぞれについて、ダメージの総和が \(i\) 以上となるまでに必要な攻撃回数と、 \(i+1\) 以上となるまでに必要な攻撃回数では、両者は等しいか、後者が \(1\) 大きいかのどちらかです。 よって、後者が\(1\) 大きくなる確率を \(p_i\) とすると、\(a_{i+1}=a_{i}+p_i\) として書く事ができます。

ここで、与えたダメージの総和は狭義単調増加となることから、後者が\(1\) 大きくなる事は与えたダメージの総和がちょうど \(i\) になるタイミングが存在する事と同値なため、そのような確率と言い換える事ができます。さらに, その余事象(与えたダメージの総和がちょうど \(i\) になるタイミングが存在しない場合)としてあり得るのは、あるタイミングでダメージの総和がちょうど \(i-1\) になり、その次の攻撃でダメージを \(2\) 与えたような場合しかあり得ないため、\(p_i\) は \(p_{i-1}\) を用いて、 \(p_i=1-p_{i-1}\times \frac{P}{100}\cdots ①\) と書く事ができます。

\(p_0=1\) であることに注意すると、①を繰り返し用いて帰納的に \(p_i\) の値を求めることができます。
\(a_N=a_{N-1}+p_{N-1}=\cdots=a_0+\displaystyle\sum_{i=0}^{N-1}p_i=\displaystyle\sum_{i=0}^{N-1}p_i\) であるので、答えはこれらの累積和として求める事ができます。

\(\text{mod }998244353\) における計算については、modint を用いるか、\(100\) の逆元、すなわち\(100R\equiv 1 \pmod{998244353}\) となる整数 \(R\) を用いて、\(p_i\equiv1-p_{i-1}\times PR \pmod{998244353}\) と書き直せば、答えを得る事ができます。

計算量は \(O(N)\) であり、十分高速に答えを得る事ができました。 なお、漸化式の答えを、繰り返し二乗法あるいは一般項を求める事によって得ることで \(O(\log N)\) で解く事ができます。

解法 1-b. 問題, あるいは期待値を言い換える解法

この問題は、次の問題に言い換える事ができます。

• マス\(0,1,2,\ldots,N,\ldots \) が左右一列に並んでおり、最初、マス \(0\) にコマが置かれている。
• マス \(i\) にコマが置かれているとき、\(1\) ターンでは \(\frac{P}{100}\) の確率で マス \((i+2)\) に動かし、\(1-\frac{P}{100}\) の確率でマス \((i+1)\) に動かす。
• マス \(N\) 以降のマスにコマが置かれるまでにかかるターン数の期待値を求めよ。

この時、マス \(N\) 以降のマスにコマが置かれるまでにかかったターン数はマス \(1,2,\ldots, N-1\) のうち止まった事のあるマスの数に \(1\) を足したものと一致します。便宜上、最初にマス \(0\) に止まっていたとすると、これはマス \(0, 1,2,\ldots, N-1\) のうち止まった事のあるマスの期待値であり、各マスについてマス \(i\) に止まる確率を \(p'_i\) とすると、\(\displaystyle\sum_{i=0}^{N-1}p'_i\)として書く事ができます。 この \(p'_i\) は1-a の方針における \(p_i\) と一致し, 以降の計算については同様であるため、省略します。

解法 2 . 攻撃回数ごとに確率を求め、直接的に期待値を求める方法

高橋君が \(K\) 回で攻撃を止めるパターンについては次の \(2\) 通りが考えられます。

1. \(K\) 回目の攻撃でモンスターの体力が \(0\) となった。
2. \(K-1\) 回目の攻撃でモンスターの体力が \(1\) となり、 \(K\) 回目の攻撃で \(-1\) となった。

\(K\) としてあり得るのは、前者が \(\left\lceil\frac{N}{2}\right\rceil\leq K \leq N\) 、後者が \(\left\lceil\frac{N+1}{2}\right\rceil\leq K \leq N\) の範囲となります。

前者では \(N-K\) 回だけ体力を \(2\) 減らし、 \(2K-N\) 回だけ体力を \(1\) 減らしているため、そのような事が起きる確率は \({}_{K}C_{N-K}\times\left(\frac{P}{100} \right)^{N-K}\left(1-\frac{P}{100} \right)^{2K-N}\) であり、
後者では\(N-K\) 回だけ体力を \(2\) 減らし、 \(2K-N-1\) 回だけ体力を \(1\) 減らした後最後に体力を \(2\) 減らしているめ、そのような事が起きる確率は \({}_{K-1}C_{N-K}\times\left(\frac{P}{100} \right)^{N-K+1}\left(1-\frac{P}{100} \right)^{2K-N-1}\) となります。

これらの確率は、 \(0\leq m\leq N\) について、\(m! \text{ mod } 998244353\) を前計算しておく事によって、それぞれ \(O(1)\) で計算する事ができます。 あとは \(K\times\) (確率) を足し合わせることで期待値を得る事ができます。 前計算に \(O(N)\), その後に \(O(N)\) という事でこの方針でも全体で \(O(N)\) で解くことができました。

c++ による実装例(方針1):

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;

using mint = modint998244353;

int main() {
	int n,p;
	mint x=1, ans=1;
	cin >> n >> p;
	for(int i=1;i<n;i++){
		x=mint(1)-x*mint(p)/mint(100);
		ans+=x;
	}
	cout << ans.val() <<endl;
	return 0;
}

c++ による実装例(方針2):

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;

using mint = modint998244353;

int main() {
	int n,p;
	cin >> n >> p;

	mint P=mint(p)/mint(100), Q=mint(1)-P;

	vector<mint>fact(n+1);
	fact[0]=mint(1);
	for(int i=1; i<=n; i++)fact[i]=fact[i-1]*mint(i);

	mint ans=0;
	for(int k=1;k<=n;k++){
		if(k>=(n-k))ans+=mint(k)*fact[k]/(fact[n-k]*fact[2*k-n])*P.pow(n-k)*Q.pow(2*k-n);
		if((k-1)>=(n-k))ans+=mint(k)*fact[k-1]/(fact[n-k]*fact[2*k-n-1])*P.pow(n-k+1)*Q.pow(2*k-n-1);		
	}
	cout << ans.val() <<endl;
	return 0;
}