Code : Deterministic Heap (Easy Version)

O(N^4) : 3D DP ↕

Submission

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint;

void solve(int max_n, int max_k) {
    vector<vector<vector<mint>>> dp(
        max_n + 1, vector<vector<mint>>(max_k + 1, vector<mint>(2, 0)));
    // dp[n][k][on_path] is the number of deterministic heaps on n levels
    // perfect binary tree when you are allowed to do k operations on the tree
    // and on_path represents whether the root node is on the path.

    for (int k = 0; k <= max_k; k++) {
        dp[1][k][true] = 1;
        dp[1][k][false] = 1;
    }

    for (int n = 2; n <= max_n; n++) {
        for (int k = 0; k <= max_k; k++) {
            for (int root = 0; root <= k; root++) {
                int rem = k - root;
                for (int left = 0; left <= rem; left++) {
                    int right = rem - left;

                    // Root is not on path. left and right can be same.
                    dp[n][k][false] +=
                        dp[n - 1][left][false] * dp[n - 1][right][false];

                    // On path. Values can't be same.
                    if (left == right) {
                        continue;
                    }

                    // The bigger child will be on path.
                    if (left > right) {
                        dp[n][k][true] +=
                            dp[n - 1][left][true] * dp[n - 1][right][false];
                    } else {
                        dp[n][k][true] +=
                            dp[n - 1][left][false] * dp[n - 1][right][true];
                    }
                }
            }
        }
    }

    cout << dp[max_n][max_k][true].val() << "\n";
}

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

    int t;
    cin >> t;
    while (t--) {
        int n, k, p;
        cin >> n >> k >> p;
        mint::set_mod(p);
        solve(n, k);
    }
}

O(N^4) : 2D INDP and OUTDP ↕

Submission

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint;

void solve(int max_n, int max_k) {
    // indp[n][k] is the number of deterministic heaps on n levels
    // perfect binary tree when you are allowed to do k operations on the tree
    // and the root node is on the path described in problem.
    vector<vector<mint>> indp(max_n + 1, vector<mint>(max_k + 1, 0));
    vector<vector<mint>> outdp(max_n + 1, vector<mint>(max_k + 1, 0));

    for (int k = 0; k <= max_k; k++) {
        indp[1][k] = 1;
        outdp[1][k] = 1;
    }

    for (int n = 2; n <= max_n; n++) {
        for (int k = 0; k <= max_k; k++) {
            for (int root = 0; root <= k; root++) {
                int rem = k - root;
                for (int left = 0; left <= rem; left++) {
                    int right = rem - left;

                    // Root is not on path. left and right can be same.
                    outdp[n][k] += outdp[n - 1][left] * outdp[n - 1][right];

                    // On path. Values can't be same.
                    if (left == right) {
                        continue;
                    }

                    // The bigger child will be on path.
                    if (left > right) {
                        indp[n][k] += indp[n - 1][left] * outdp[n - 1][right];
                    } else {
                        indp[n][k] += outdp[n - 1][left] * indp[n - 1][right];
                    }
                }
            }
        }
    }

    cout << indp[max_n][max_k].val() << "\n";
}

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

    int t;
    cin >> t;
    while (t--) {
        int n, k, p;
        cin >> n >> k >> p;
        mint::set_mod(p);
        solve(n, k);
    }
}

O(N^4) : 2D DP in Sum Format ↕

Submission

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint;

void solve(int max_n, int max_k) {
    // indp[n][k] is the number of deterministic heaps on n levels
    // perfect binary tree when you are allowed to do k operations on the tree
    // and the root node is on the path described in problem.
    vector<vector<mint>> indp(max_n + 1, vector<mint>(max_k + 1, 0));
    vector<vector<mint>> outdp(max_n + 1, vector<mint>(max_k + 1, 0));

    for (int k = 0; k <= max_k; k++) {
        indp[1][k] = 1;
        outdp[1][k] = 1;
    }

    for (int n = 2; n <= max_n; n++) {
        for (int k = 0; k <= max_k; k++) {
            for (int left = 0; left <= k; left++) {
                int rem = k - left;
                mint sum = 0;
                for (int right = 0; right <= rem; right++) {
                    sum += outdp[n - 1][right];
                }
                outdp[n][k] += outdp[n - 1][left] * sum;

                sum = 0;
                int up = min(left - 1, rem);
                for (int right = 0; right <= up; right++) {
                    sum += outdp[n - 1][right];
                }
                indp[n][k] += indp[n - 1][left] * sum;

                sum = 0;
                for (int right = left + 1; right <= rem; right++) {
                    sum += indp[n - 1][right];
                }
                indp[n][k] += outdp[n - 1][left] * sum;
            }
        }
    }

    cout << indp[max_n][max_k].val() << "\n";
}

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

    int t;
    cin >> t;
    while (t--) {
        int n, k, p;
        cin >> n >> k >> p;
        mint::set_mod(p);
        solve(n, k);
    }
}

O(N^3) : 2D DP ↕

Submission

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint;

void solve(int max_n, int max_k) {
    // indp[n][k] is the number of deterministic heaps on n levels
    // perfect binary tree when you are allowed to do k operations on the tree
    // and the root node is on the path described in problem.
    vector<vector<mint>> indp(max_n + 1, vector<mint>(max_k + 1, 0));
    vector<vector<mint>> outdp(max_n + 1, vector<mint>(max_k + 1, 0));
    vector<vector<mint>> pref_indp(max_n + 1, vector<mint>(max_k + 1, 0));
    vector<vector<mint>> pref_outdp(max_n + 1, vector<mint>(max_k + 1, 0));

    auto convert_to_prefix_sum = [&](vector<mint> &a, vector<mint> &pref) {
        pref[0] = a[0];
        for (int i = 1; i < pref.size(); i++) {
            pref[i] += pref[i - 1] + a[i];
        }
    };

    auto get_sum = [&](vector<mint> &pref, int l, int r) {
        if (l > r) {
            return mint(0);
        }
        return pref[r] - (l ? pref[l - 1] : 0);
    };

    for (int k = 0; k <= max_k; k++) {
        indp[1][k] = 1;
        outdp[1][k] = 1;
    }

    convert_to_prefix_sum(indp[1], pref_indp[1]);
    convert_to_prefix_sum(outdp[1], pref_outdp[1]);

    for (int n = 2; n <= max_n; n++) {
        for (int k = 0; k <= max_k; k++) {
            for (int left = 0; left <= k; left++) {
                int rem = k - left;
                outdp[n][k] +=
                    outdp[n - 1][left] * get_sum(pref_outdp[n - 1], 0, rem);

                int up = min(left - 1, rem);
                indp[n][k] +=
                    indp[n - 1][left] * get_sum(pref_outdp[n - 1], 0, up);

                indp[n][k] += outdp[n - 1][left] *
                              get_sum(pref_indp[n - 1], left + 1, rem);
            }
        }
        convert_to_prefix_sum(indp[n], pref_indp[n]);
        convert_to_prefix_sum(outdp[n], pref_outdp[n]);
    }

    cout << indp[max_n][max_k].val() << "\n";
}

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

    int t;
    cin >> t;
    while (t--) {
        int n, k, p;
        cin >> n >> k >> p;
        mint::set_mod(p);
        solve(n, k);
    }
}