Code : Counting Binary Strings

#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>>(n + 1, vector<int>(n + 1, 0)));

    // dp[i][x][y] represents the number of strings with suffix (x)(1)(y)
    // that contains i good substrings.
    // (x)(1)(y) means that the suffix consists of x zeroes, followed by a
    // single one followed by y zeroes.

    for (int x = 0; x < k; x++) {
        dp[x + 1][x][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 '1'.
                // (x)(1)(y) ==> (y)(1)()
                int nxt = i + 1 + y;
                if (nxt <= n) {
                    inc(dp[nxt][y][0], dp[i][x][y]);
                }

                // Append a '0'.
                // (x)(1)(y) ==> (x)(1)(y + 1)
                if (x + y + 1 < k) {
                    int nxt = i + x + 1;
                    if (nxt <= n) {
                        inc(dp[nxt][x][y + 1], 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 << endl;
}

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<int>> dp(n + 1, vector<int>(n + 1, 0));

    // dp[i][x] represents the number of strings with i good substrings
    // that contain exactly x suffix zeroes.

    // The base case should only contain strings that cannot be constructed
    // using the algorithm.
    // For example, 0001 can be constructed by extending the suffix 000 which
    // has zero good substrings.

    // Empty string. Contains no suffix zeroes and no good substrings.
    dp[0][0] = 1;

    // Only substrings which cannot be generated are those with all zeroes.
    for (int x = 1; x < k; x++) {
        dp[0][x] = 1;
    }

    for (int i = 0; i <= n; i++) {
        for (int x = 0; x < k; x++) {
            // If we have x zeroes in the suffix, then we can try appending
            // 10000.... to construct the next set of strings.
            // We cannot add >= k zeroes.
            // The sum of zeroes on the left and right cannot exceed k.
            // x + y < k
            for (int y = 0; x + y < k; y++) {
                int nxt = i + (x + 1) * (y + 1);
                if (nxt <= n) {
                    inc(dp[nxt][y], dp[i][x]);
                }
            }
        }
    }

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

    cout << ans << endl;
}

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

// Corner Case: How would you construct 10  or 100 or 1000?
// For this, you need to utilize empty string as base case.
//
// Exercise : How does this algorithm construct xyz1111?

#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>(n + 1, 0));

    // dp[i][x] represents the number of strings with i good substrings
    // that contain exactly x suffix zeroes.

    // The base case should only contain strings that cannot be constructed
    // using the algorithm.
    // For example, 0001 can be constructed by extending the suffix 000 which
    // has zero good substrings.

    // Empty string. Contains no suffix zeroes and no good substrings.
    dp[0][0] = 1;

    // Only substrings which cannot be generated are those with all zeroes.
    for (int x = 1; x < k; x++) {
        dp[0][x] = 1;
    }

    for (int i = 0; i <= n; i++) {
        for (int x = 0; x < k; x++) {
            // If we have x zeroes in the suffix, then we can try appending
            // 10000.... to construct the next set of strings.
            // We cannot add >= k zeroes.
            // The sum of zeroes on the left and right cannot exceed k.
            // x + y < k
            for (int y = 0; x + y < k; y++) {
                int nxt = i + (x + 1) * (y + 1);
                if (nxt <= n) {
                    inc(dp[nxt][y], dp[i][x]);
                } else {
                    // With appropriate break conditions, we will traverse
                    // n log(n) steps.
                    // Similar to ABC335F : Hop Sugoroku.
                    break;
                }
            }
        }
    }

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

    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

// Corner Case: How would you construct 10  or 100 or 1000?
// For this, you need to utilize empty string as base case.
//
// Exercise : How does this algorithm construct xyz1111?