\(\mathrm{dp}[i]\) を、モンスターの体力が \(N\) である状態からモンスターの体力が \(0\) 以下になるまでにかかる攻撃回数の期待値と定義します。

答えは \(\mathrm{dp}[N]\) です。この動的計画法は、最初の攻撃で与えるダメージに着目して場合分けすることで、昇順に埋めることが可能です。計算量は \(\mathrm{O}(N)\) です。

また、この動的計画法は \(i\geq 2 \) のときに遷移が \(i\) に依らないことに着目すると行列累乗で高速化可能で、\(\mathrm{O}(\log N)\) 解法が得られます。

線形時間解法の実装例(c++):

#include <bits/stdc++.h>

#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;

int main() {
    int n, p;
    cin >> n >> p;
    vector dp(n + 1, mint(0));
    mint critical = mint(p) / 100, normal = 1 - critical;
    for(int i = 1; i <= n; i++)
        dp[i] = (dp[max(0, i - 2)] * critical + dp[i - 1] * normal) + 1;
    cout << dp.back().val() << endl;
}

対数時間解法の実装例(c++):

#include <bits/stdc++.h>

#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;

template <class T>
struct matrix {
    int h, w;
    vector<vector<T>> e;
    matrix(int h_, int w_) : h(h_), w(w_), e(h_, vector<T>(w_)) {}
    std::vector<T> &operator[](int p) {
        return e[p];
    }
    const std::vector<T> &operator[](int p) const {
        return e[p];
    }
    matrix operator*(const matrix &m) {
        assert(w == m.h);
        matrix ret(h, m.w);
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < m.w; j++) {
                for(int k = 0; k < w; k++) {
                    ret[i][j] += e[i][k] * m[k][j];
                }
            }
        }
        return ret;
    }
    matrix operator^(long long p) const {
        assert(h == w);
        matrix I(h, w), b(*this);
        for(int i = 0; i < h; i++) I[i][i] = T(1);
        while(p) {
            if(p & 1) I = I * b;
            b = b * b;
            p >>= 1;
        }
        return I;
    }
};

int main() {
    int n, p;
    cin >> n >> p;
    mint critical = mint(p) / 100, normal = 1 - critical;
    matrix<mint> r(3, 1);
    r[0][0] = 1 + normal;
    r[1][0] = 1;
    r[2][0] = 1;
    matrix<mint> m(3, 3);
    m[0] = {normal, critical, 1};
    m[1] = {1, 0, 0};
    m[2] = {0, 0, 1};
    r = (m ^ (n - 1)) * r;
    cout << r[1][0].val() << endl;
}