Solution 1-a. Focusing on delta of expected value

When the stamina reduces by \(X\), let us call that “\(X\) damage was dealt.” Let \(a_k\) be the expected value of the number of attacks until the sum of damage dealt accumulates \(k\) or greater.
For example, \(a_0=0\), \(a_1=1\), and \(a_2=2-\frac{p}{100}\).

Also, when considering this expected value, Takahashi do not need to stop attacking after dealing \(N\) damage, so we accept “overruns” here. What we want is \(a_N\).

First, we consider \(a_{i+1}-a_i\). For each sequence of damages of Takahashi’s attack, the number of attacks required to deal at least \(i\) damage and that at least \(i+1\) is equal, or the latter is greater by \(1\). Therefore, when the probability that the latter is greater is denoted by \(p_i\), we can write as \(a_{i+1}=a_{i}+p_i\).

Here, since the sum of dealt damage is strictly increasing, the latter is greater if and only if the dealt damage equals \(i\) at some time, so such a rephrase is valid. Moreover, the complementary event (where the dealt damage never becomes \(i\)) happens only if the damage becomes \((i-1)\) at some point and \(2\) damage is dealt in the next attack, so \(p_i\) is expressed using \(p_{i-1}\) as \(p_i=1-p_{i-1}\times \frac{P}{100}\cdots ①\).

Since \(p_0=1\), we can recursively use ① to find the values of \(p_i\).
Since \(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\), the answer is found as their cumulative sum.

In order to compute the modulo \(998244353\), you may use modint, or use the inverse of \(100\), i.e. the integer \(R\) such that \(100R\equiv 1 \pmod{998244353}\), to rewrite it as \(p_i\equiv1-p_{i-1}\times PR \pmod{998244353}\).

The complexity is \(O(N)\), which is fast enough. By the way, you can use the fast exponentiation trick or find a general term to find the answer in an \(O(\log N)\) time.

Solution 1-b. Rephrasing problem or expected value

This problem can be rephrased as follows:

• Squares \(0,1,2,\ldots,N,\ldots \) are arranged horizontally. Initially, square \(0\) has a piece on it.
• When square \(i\) has a piece, it is move to square \((i+2)\) with probability \(\frac{P}{100}\) and to square \((i+1)\) with probability \(1-\frac{P}{100}\) in one step.
• Find the expected value of the number of steps until the piece reaches square \(N\) or later.

This time, the number of steps until the piece reaches square \(N\) or later is equal to the number of squares that the piece landed among squares \(0, 1,2,\ldots, N-1\) plus \(1\). Denoting by \(p'_i\) the probability that the piece lands square \(i\), it can be expressed as \(\displaystyle\sum_{i=0}^{N-1}p'_i\). This \(p'_i\) is equivalent to \(p_i\) in 1-a, so the remaining computation can be done just as same as before, so we omit the details.

Solution 2. Find the probability of each number of attacks to find the expected value directly

Takahashi can stop attacking after \(K\) times if one of the following two holds:

1. The monster’s stamina reached \(0\) by the \(K\)-th attack.
2. The monster’s stamina reached \(1\) by the \((K-1)\)-th attack, and \(-1\) by the \(K\)-th.

The ranges of possible \(K\) are \(\left\lceil\frac{N}{2}\right\rceil\leq K \leq N\) for the former and \(\left\lceil\frac{N+1}{2}\right\rceil\leq K \leq N\) for the latter.

In the former, the stamina is reduced by \(2\) \((N-K)\) times and by \(1\) \((2K-N)\) times, so the probability of such event is \({}_{K}C_{N-K}\times\left(\frac{P}{100} \right)^{N-K}\left(1-\frac{P}{100} \right)^{2K-N}\);
in the latter, the stamina is reduced by \(2\) \((N-K)\) times and by \(1\) \((2K-N-1)\) times, and finally by \(2\) once, so the probability of such event is \({}_{K-1}C_{N-K}\times\left(\frac{P}{100} \right)^{N-K+1}\left(1-\frac{P}{100} \right)^{2K-N-1}\).

These probabilities can be computed in an \(O(1)\) time each by precalculating \(m! \text{ mod } 998244353\) for each \(0\leq m\leq N\). All that left is find the sum of \(K\times\) (probability) to obtain the expected value. The precalculation costs \(O(N)\) and the latter part costs \(O(N)\), so this approach enables us to solve it in an \(O(N)\) time again.

Sample code in C++ (Solution 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;
}

Sample code in C++ (Solution 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;
}