String Wars

#include "bits/stdc++.h"

using namespace std;

int main() {
    uint64_t n, m;
    cin >> n >> m;

    // dp[i][0] — how many good strings s such that (len(s) = i + 1 and s[0] = 'A') exist
    // dp[i][1] — how many good strings s such that (len(s) = i + 1 and s[0] = 'B') exist
    vector<array<uint64_t, 2>> dp(n);
    dp[0] = {1, 1};
    for (uint64_t i = 1; i < n; ++i) {
        const auto prv = dp[i - 1];
        dp[i][0] = prv[0] + prv[1];
        dp[i][1] = prv[0];
    }

    if (m > dp.back()[0] + dp.back()[1]) {
        cout << -1 << "\n";
        return EXIT_SUCCESS;
    }

    string ans{};
    for (int cur = dp.size() - 1; cur >= 0; --cur) {
        if (m <= dp[cur][0]) {
            ans += "A";
        } else {
            m -= dp[cur][0];
            ans += "B";
        }
    }
    cout << ans << "\n";
}