c++代码

#include <iostream>
#include <map>
using namespace std;

typedef long long ll;

// 使用记忆化搜索存储已计算的结果
map<pair<int, ll>, ll> memo_patties;
map<int, ll> memo_total;

// 计算等级为L的汉堡总层数
ll getTotalLayers(int L) {
if (memo_total.count(L)) {
return memo_total[L];
}

if (L == 0) {
    return memo_total[L] = 1;  // 只有一层肉饼
}
return memo_total[L] = 2 * getTotalLayers(L - 1) + 3;  // 两层子汉堡 + 3层面包

}

// 计算等级为L的汉堡底部X层中有多少肉饼
ll countPatties(int L, ll X) {
if (memo_patties.count({L, X})) {
return memo_patties[{L, X}];
}

if (L == 0) {
    return memo_patties[{L, X}] = min(X, 1LL);  // 最底层只有1层肉饼
}

ll totalLayers = getTotalLayers(L);
ll halfLayers = getTotalLayers(L - 1);  // 子汉堡的层数

if (X <= 0) {
    return memo_patties[{L, X}] = 0;
} else if (X <= 1) {
    // 只吃了最下面的面包
    return memo_patties[{L, X}] = 0;
} else if (X <= 1 + halfLayers) {
    // 吃到了下半部分汉堡的一部分
    return memo_patties[{L, X}] = countPatties(L - 1, X - 1);
} else if (X <= 1 + halfLayers + 1) {
    // 吃完了下半部分汉堡和中间的肉饼
    return memo_patties[{L, X}] = countPatties(L - 1, halfLayers) + 1;
} else if (X <= 1 + halfLayers + 1 + halfLayers) {
    // 吃完了下半部分和中间肉饼，以及上半部分的一部分
    ll bottomPatties = countPatties(L - 1, halfLayers);
    ll topPatties = countPatties(L - 1, X - 1 - halfLayers - 1);
    return memo_patties[{L, X}] = bottomPatties + 1 + topPatties;
} else {
    // 吃完了整个汉堡
    ll pattiesInSub = countPatties(L - 1, halfLayers);
    return memo_patties[{L, X}] = pattiesInSub * 2 + 1;
}

}

int main() {
int N;
ll X;
cin >> N >> X;

cout << countPatties(N, X) << endl;

return 0;

}