Subtree Budget Allocation and Optimal Path Reconstruction

The core challenge revolves around allocating a fixed budget across a binary tree structure to maximize a specific threshold value. The solution begins by analyzing the root's contribution and propagating constraints downward. We define a dynamic programming state dp_max[u][b] representing highest achievable threshold within the subtree rooted at u when exactly b units of budget are spent. The recurrence combines results from the left and right children:

dp_max[u][b] = dp_max[left][b] + min(dp_max[right][b], weight[u])

Base cases initialize the leaf nodes such that dp_max[leaf][0...limit] = 0 and dp_max[leaf][limit+1] = infinity. A key observation is that each node's DP array exhibits a piecewise constant structure. By storing only the "breakpoints" (pairs mapping budget to threshold value), we can merge child states efficiently. This optimization reduces the time complexity to O(N log N) relative to the number of nodes, where merging is performed similarly to the merge step in merge sort.

The reconstruction phase utilizes a recursive function trace_path(u, budget) to determine the exact selection sequence. By binary searching the breakpoint vectors, we identify the largest threshold j that can be satisfied within the current budget. Depending on whether j originates from the left or right branch, we allocate funds strategically. If the target lies in the right subtree, we prioritize reserving funds for the left child and execute the right subtree first. If it lies in the left subtree, we evaluate weather including weight[u] is necessary, optinng to skip it whenever the remaining budget suffices. This greedy reconstruction ensures optimal budget utilization while maintaining the required traversal order.

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

using int64 = long long;
const int64 INF_VAL = 1e18;
const int MAX_NODES = (1 << 17) + 5;

int n;
int64 node_weight[MAX_NODES], leaf_limit[MAX_NODES];
int64 leaf_index[MAX_NODES];
vector<pair<int, int64>> breaks[MAX_NODES];

inline bool is_leaf(int u) {
    return u >= (1 << n);
}

void build_dp(int u) {
    if (is_leaf(u)) {
        breaks[u].push_back({static_cast<int>(leaf_limit[u]), 0});
        return;
    }
    int left = u << 1;
    int right = (u << 1) | 1;
    build_dp(left);
    build_dp(right);

    int l_ptr = static_cast<int>(breaks[left].size()) - 1;
    int r_ptr = static_cast<int>(breaks[right].size()) - 1;
    int base_l = l_ptr;
    int base_r = r_ptr;

    auto get_left_cost = [&](int idx) -> int64 {
        return (idx <= base_l) ? breaks[left][idx].second : INF_VAL;
    };
    auto get_right_cost = [&](int idx) -> int64 {
        return (idx <= base_r) ? breaks[right][idx].second : INF_VAL;
    };

    while (l_ptr >= 0 && r_ptr >= 0) {
        int current_threshold = 0;
        if (breaks[left][l_ptr].first > breaks[right][r_ptr].first) {
            current_threshold = breaks[left][l_ptr].first;
            l_ptr--;
        } else {
            current_threshold = breaks[right][r_ptr].first;
            r_ptr--;
        }
        int64 combined_cost = get_left_cost(l_ptr + 1) + min(node_weight[u], get_right_cost(r_ptr + 1));
        breaks[u].push_back({current_threshold, combined_cost});
    }
    while (l_ptr >= 0) {
        breaks[u].push_back({breaks[left][l_ptr].first, get_left_cost(l_ptr) + min(get_right_cost(0), node_weight[u])});
        l_ptr--;
    }
    while (r_ptr >= 0) {
        breaks[u].push_back({breaks[right][r_ptr].first, get_left_cost(0) + min(get_right_cost(r_ptr), node_weight[u])});
        r_ptr--;
    }
    reverse(breaks[u].begin(), breaks[u].end());
}

int locate_threshold(int u, int64 budget) {
    int lo = 0, hi = static_cast<int>(breaks[u].size()) - 1;
    int ans = 0;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (breaks[u][mid].second <= budget) {
            ans = breaks[u][mid].first;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return ans;
}

int64 fetch_cost(int u, int target) {
    int lo = 0, hi = static_cast<int>(breaks[u].size()) - 1;
    int64 ans = INF_VAL;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (breaks[u][mid].first >= target) {
            ans = breaks[u][mid].second;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    return ans;
}

int64 trace_path(int u, int64 budget) {
    if (is_leaf(u)) {
        cout << leaf_index[u] << " ";
        return 0;
    }
    int left = u << 1;
    int right = (u << 1) | 1;
    int target = locate_threshold(u, budget);
    int64 spent = 0;

    if (leaf_index[target] & (1LL << (n - __builtin_ctz(u) - 1))) {
        int64 reserve = fetch_cost(left, target);
        spent = trace_path(right, budget - reserve) + trace_path(left, budget - spent);
    } else {
        int64 right_min = fetch_cost(right, target);
        spent += trace_path(left, budget - min(right_min, node_weight[u]));
        if (right_min > budget - spent) spent += node_weight[u];
        spent += trace_path(right, budget - spent);
    }
    return spent;
}

void process_test_case() {
    int64 budget;
    cin >> n >> budget;
    for (int i = 1; i < (1 << n); ++i) cin >> node_weight[i];
    for (int i = (1 << n); i < (1 << (n + 1)); ++i) {
        cin >> leaf_limit[i];
        leaf_index[leaf_limit[i]] = i;
    }
    build_dp(1);
    trace_path(1, budget);
    cout << "\n";
}

void clear_data() {
    int limit = 1 << (n + 1);
    for (int i = 1; i < limit; ++i) breaks[i].clear();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        clear_data();
        process_test_case();
    }
    return 0;
}

Counting Modular Products via CRT and Matrix Exponentiation

This problem requires counting sequences of length N whose product modulo M equals a target value A. The solution leverages the Chinese Remainder Theorem (CRT) to decompose the modulus into independent prime power components p^e. The final answer is the product of the counts computed for each component modulo 998244353.

For a fixed prime power modulus p^e, we track the exponent of p in the cumulative product. Let val_cnt[v] represent the number of integers in [0, p^e - 1] whose p-adic valuation is exactly v. The state transition for the exponent follows new_exp = min(e, old_exp + v). Since the transition rules remain identical across all positions in the sequence, we can model the process as a linear transformation. Matrix exponentiation efficiently computes the distribution of exponents after N-1 steps in O(e^3 log N) time.

After determining the exponent distribution for the prefix, we analyze the final element. We need to solve a linear congruence derived from prefix * last ≡ A (mod p^e). When A is not divisible by p^e, we compute the modular inverse of the prefix component coprime to p and determine the valid range for the final element's offset. The contribution for each prime power is summed according to the divisibility conditions and multiplied together to yield the final result.

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

using int64 = long long;
const int64 MOD = 998244353;
const int MAX_E = 45;

int64 seq_len, target_val, modulus_val;
int64 val_counts[MAX_E];
int64 pow_p[MAX_E];

inline void add_mod(int64& a, int64 b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

struct Matrix {
    int64 mat[MAX_E][MAX_E];
    Matrix() { memset(mat, 0, sizeof(mat)); }
    static Matrix identity() {
        Matrix res;
        for (int i = 0; i < MAX_E; ++i) res.mat[i][i] = 1;
        return res;
    }
};

Matrix multiply(const Matrix& A, const Matrix& B) {
    Matrix res;
    for (int k = 0; k < MAX_E; ++k)
        for (int i = 0; i < MAX_E; ++i)
            if (A.mat[i][k])
                for (int j = 0; j < MAX_E; ++j)
                    add_mod(res.mat[i][j], A.mat[i][k] * B.mat[k][j] % MOD);
    return res;
}

Matrix power_matrix(Matrix base, int64 exp) {
    Matrix res = Matrix::identity();
    for (; exp > 0; exp >>= 1, base = multiply(base, base))
        if (exp & 1) res = multiply(res, base);
    return res;
}

int64 solve_component(int64 p, int exponent) {
    int64 ans = 0;
    pow_p[0] = 1;
    for (int i = 1; i <= exponent; ++i) pow_p[i] = pow_p[i - 1] * p;

    for (int i = 0; i < exponent; ++i)
        val_counts[i] = (pow_p[exponent - i] - pow_p[exponent - i - 1]) % MOD;
    val_counts[exponent] = 1;

    Matrix trans;
    for (int i = 0; i <= exponent; ++i)
        for (int j = 0; j <= exponent; ++j)
            add_mod(trans.mat[i][min(exponent, i + j)], val_counts[j]);

    Matrix res;
    res.mat[0][0] = 1;

    if (target_val % pow_p[exponent] == 0) {
        res = multiply(res, power_matrix(trans, seq_len));
        return res.mat[0][exponent];
    }

    res = multiply(res, power_matrix(trans, seq_len - 1));
    for (int i = 0; i <= exponent; ++i) {
        if (target_val % pow_p[i] != 0) break;
        add_mod(ans, res.mat[0][i] * pow_p[i] % MOD);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> seq_len >> target_val >> modulus_val;
    int64 final_ans = 1;

    for (int64 i = 2; i * i <= modulus_val; ++i) {
        if (modulus_val % i == 0) {
            int cnt = 0;
            while (modulus_val % i == 0) {
                modulus_val /= i;
                cnt++;
            }
            final_ans = final_ans * solve_component(i, cnt) % MOD;
        }
    }
    if (modulus_val > 1) {
        final_ans = final_ans * solve_component(modulus_val, 1) % MOD;
    }

    cout << final_ans << "\n";
    return 0;
}