#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define cout cerr
#define trace(x) for (auto &el : x) cout << el << " "
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
int k = 60;
int brute(int x, vi a) {
int ans = 0;
int mx = 0; for (int i = 0; i < k; i++) mx += a[i]*(1LL<<i);
for (int i = 0; i <= mx; i++) {
vi avail = a; bool good = true;
for (int bit = 0; bit < k; bit++) {
if ((1LL<<bit) > i) break;
bool use = i & 1LL<<bit;
if (use && avail[bit] < x) good = false;
int rem = use ? avail[bit] - x : avail[bit];
avail[bit+1] += rem / 2;
}
if (good) {
ans++;
// cout << i << " ";
}
}
// cout << "\n";
return ans;
}
// start by pushing everything upstream, with limit x
// now the difference between using bit i or pushing it up to i+1
int count_tastiness(int x, vi a) {
while (a.size() <= k) a.push_back(0);
for (int i = 0; i < k; i++) {
if (a[i] <= x+1) continue;
a[i+1] += (a[i]-x) / 2;
a[i] -= 2 * ((a[i]-x) / 2);
}
/*
vvi dp(k+1, vi(2, 0)); dp[k][0] = 1;
for (int i = k-1; i >= 0; i--) {
dp[i][0] = dp[i+1][0];
if (a[i] == 1) dp[i][0] += dp[i+1][0];
else if (a[i] == 2) dp[i][0] += dp[i+1][1];
if (a[i] == 0) dp[i][1] = dp[i+1][0];
else if (a[i]+1 >= 2) dp[i][1] = dp[i+1][1] - dp[i+1][0];
dp[i][1] = dp[i][0] + dp[i][1];
}
*/
// vvi dp(k+1, vi(x+1));
vector<vector<pi>> dp(k+1, vector<pi>());
dp[60].push_back({0, 1}); // 0 in each
auto query = [&](int bit, int carry) {
int lo = 0, hi = dp[bit].size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (dp[bit][mid].first > carry) hi = mid;
else lo = mid + 1;
}
return dp[bit][lo-1].second;
};
auto compute = [&](int bit, int carry) {
int y = query(bit+1, (a[bit] + carry) / 2);
if (a[bit] + carry >= x) {
y += query(bit+1, (a[bit] + carry - x) / 2);
}
return y;
};
for (int bit = 59; bit >= 0; bit--) {
int prev = -1;
for (int carry = 0; carry <= x; carry++) {
int lo = carry, hi = x;
while (lo < hi) {
int mid = lo + (hi-lo) / 2;
if (compute(bit, mid) == prev) lo = mid+1;
else hi = mid;
}
carry = lo;
prev = compute(bit, carry);
dp[bit].push_back({carry, prev});
}
}
// int ex = brute(x, a);
// cout << "BRUTE: " << ex << " DP: " << dp[0][0] << "\n";
// return dp[0][0];
return dp[0][0].second;
// return 0;
}
