公式解説と同様に、選んだ鍵盤に貪欲法で腕・指を割り当てた標準形を数えます。ただし、鍵盤を 1 つずつ進めて現在の腕の状態を持つ代わりに、腕 1 本分の担当範囲をまとめて 1 回の遷移で処理します。

これにより「現在の腕が最初に押した鍵盤\(s\)」の次元が状態から消え、状態数 \(O(NAK)\)・1 状態あたりの遷移 \(O(D+B)\) の DP になります。

貪欲法では、腕の交代は「指が尽きた」か「距離が \(D\) を超えた」のいずれかで起こります。したがって、標準形における各腕の担当は次のいずれかの形になります（\(B \geq 2\) とします）。

• (a) \(B\) 本の指をすべて使う場合
  担当は最左 \(s\)・最右 \(t\)（\(t-s \leq D\)）と、その間から選んだ \(B-2\) 個です。指が尽きて交代するので、次の腕は鍵盤 \(t+1\) 以降の任意の位置から始まってよいです。
• (b) 使う指が \(B-1\) 本以下の場合
  指が余っているので、交代は距離超過によってのみ起こります。よって区間 \([s,\, \min(s+D, N)]\) 内で選ばれた鍵盤はすべてこの腕が担当し、次の腕は区間の外から始まります。

(a) と (b) は担当する鍵盤数が「ちょうど \(B\) 個か、\(B-1\) 個以下か」で排他的なので、鍵盤の選び方と腕ブロックの列は 1 対 1 に対応します。

DPの定義

\(\text{dp}_{i,m,p}\) を、鍵盤 \(1, 2, \ldots, i\) の押す・押さないが確定していて、担当が確定した腕が \(m\) 本、押すと決めた鍵盤が \(p\) 個である場合の数とします。初期値は\(\text{dp}_{0,0,0} = 1\) です。

DPの遷移

鍵盤 \(s = i+1\) に注目し、次の遷移を行います。

鍵盤 \(s\) を押さない

• \(\text{dp}_{s,\,m,\,p} \mathrel{{+}{=}} \text{dp}_{i,m,p}\)

鍵盤 \(s\) を \(m+1\) 本目の腕の最初の指で押す

• (a) 指を使い切る遷移（\(p + B \leq K\) のとき）
  最右の鍵盤 \(t\)（\(s + B - 1 \leq t \leq \min(s+D,\, N)\)）を全探索し、間の \(t-s-1\) 個から \(B-2\) 個を選びます。遷移は \(\text{dp}_{t,\,m+1,\,p+B} \mathrel{{+}{=}} \binom{t-s-1}{B-2} \cdot \text{dp}_{i,m,p}\) です。
• (b) 指を余らせる遷移
  \(w = \min(D,\, N-s)\) とし、区間内の \(w\) 個から追加で押す \(z\) 個（\(0 \leq z \leq \min(B-2,\, w,\, K-p-1)\)）を選びます。遷移は \(\text{dp}_{s+w,\,m+1,\,p+z+1} \mathrel{{+}{=}} \binom{w}{z} \cdot \text{dp}_{i,m,p}\) です。

ただし、\(B = 1\) のときは (a)(b) の代わりに、各腕がちょうど 1 個の鍵盤を担当する遷移 \(\text{dp}_{s,\,m+1,\,p+1} \mathrel{{+}{=}} \text{dp}_{i,m,p}\) を行います。

貪欲法が使う腕の本数は最小なので、選んだ鍵盤を同時に押せることと、使う腕が \(A\) 本以下であることは同値です。よって最終的な答えは \(\sum_{m=0}^{A} \text{dp}_{N,m,K}\) となります。

状態数が \(O(NAK)\)、時間計算量は\(O(NAK(D+B))\) です。（二項係数の前計算 \(O(D^2)\) は \(D \lt N\) よりこれに含まれます）

実装例(C++):

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using mint = atcoder::modint998244353;

int main() {
    int N, K, A, B, D;
    cin >> N >> K >> A >> B >> D;

    // 二項係数の前計算(引数は高々D)
    vector C(D + 1, vector<mint>(D + 1));
    for (int i = 0; i <= D; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }

    // dp[i][m][p]: 鍵盤iまで確定し,確定した腕がm本,押した鍵盤がp個となる組み合わせの数
    vector dp(N + 1, vector(A + 1, vector<mint>(K + 1)));
    dp[0][0][0] = 1;

    for (int i = 0; i < N; ++i) {  // 鍵盤 s = i+1 に注目
        for (int m = 0; m < A; ++m) {
            for (int p = 0; p < K; ++p) {
                const mint cur = dp[i][m][p];
                if (B == 1) {
                    dp[i + 1][m + 1][p + 1] += cur;
                }
                else {
                    // (a) 指を使い切る遷移
                    if (p + B <= K) {
                        for (int t = i + B; t <= min(i + 1 + D, N); ++t)
                            dp[t][m + 1][p + B] += C[t - i - 2][B - 2] * cur;
                    }
                    // (b) 指を余らせる遷移
                    const int w = min(D, N - (i + 1));
                    for (int z = 0; z <= min({ B - 2, w, K - p - 1 }); ++z)
                        dp[i + 1 + w][m + 1][p + z + 1] += C[w][z] * cur;
                }
            }
        }
        // 鍵盤sを押さない遷移
        for (int m = 0; m <= A; ++m)
            for (int p = 0; p <= K; ++p)
                dp[i + 1][m][p] += dp[i][m][p];
    }

    mint ans = 0;
    for (int m = 0; m <= A; ++m) ans += dp[N][m][K];
    cout << ans.val() << "\n";
}