Contest Duration: - (local time) (100 minutes) Back to Home
Official

## E - Critical Hit Editorial by en_translator

#### 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;
}


posted:
last update: