Code : K Zero Stream (Hard)

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

const int mod = 998244353;

void inc(int &a, int b) {
    a += b;
    a %= mod;
}

void solve(int n, int k) {
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
    // dp[i][x] is the number of good binary string that has a suffix
    // consisting of x zeroes.

    // Base Case : Strings that consists of all zeroes.
    for (int x = 0; x < k; x++) {
        dp[x][x] = 1;
    }

    for (int i = 0; i < n; i++) {
        for (int x = 0; x < n; x++) {
            for (int y = 0; x + y < k; y++) {
                if (i + y + 1 <= n) {
                    inc(dp[i + y + 1][y], dp[i][x]);
                }
            }
        }
    }

    int ans = 0;
    for (int x = 0; x < k; x++) {
        inc(ans, dp[n][x]);
    }
    cout << ans << "\n";
}

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n, k;
        cin >> n >> k;
        solve(n, k);
    }
    return 0;
}

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

const int mod = 998244353;

void inc(int &a, int b) {
    a += b;
    a %= mod;
}

void solve(int n, int k) {
    vector<vector<vector<int>>> dp(
        n + 1, vector<vector<int>>(k + 1, vector<int>(k + 1, 0)));
    // dp[i][x][y] is the number of good binary strings of length n that has a
    // suffix consisting of x zeroes followed by a single 1, followed by y
    // zeroes.

    dp[0][0][0] = 1;

    for (int i = 0; i < n; i++) {
        for (int x = 0; x < k; x++) {
            for (int y = 0; y < k; y++) {
                // Append a zero.
                if (x + y + 1 < k) {
                    inc(dp[i + 1][x][y + 1], dp[i][x][y]);
                }

                // Append a one.
                inc(dp[i + 1][y][0], dp[i][x][y]);
            }
        }
    }

    int ans = 0;
    for (int x = 0; x < k; x++) {
        for (int y = 0; y < k; y++) {
            inc(ans, dp[n][x][y]);
        }
    }
    cout << ans << "\n";
}

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n, k;
        cin >> n >> k;
        solve(n, k);
    }
    return 0;
}