#include "biscuits.h"
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
struct Node {
Node* left;
Node* right;
ll count;
Node() : left(NULL), right(NULL), count(0) {}
};
Node* clone(Node* node, ll dep, ll maxv)
{
if (!node) return NULL;
if (maxv >= (1LL << dep) - 1) {return node;}
Node* ans = new Node;
if (maxv >= (1LL << (dep - 1))) {
ans->left = node->left;
ans->right = clone(node->right, dep - 1, maxv - (1LL << (dep - 1)));
ans->count = (ans->left ? ans->left->count : 0) +
(ans->right ? ans->right->count : 0);
} else {
ans->left = clone(node->left, dep - 1, maxv);
ans->right = NULL;
ans->count = (ans->left ? ans->left->count : 0);
}
return ans;
}
ll count_tastiness(ll x, vector<ll> a) {
while (a.size() < 60) a.push_back(0LL);
Node* root = new Node; root->count = 1;
Node* curnode = root;
for (int i = 1; i <= 62; i++) {
curnode->left = new Node;
curnode = curnode->left;
curnode->count = 1;
}
ll cursum = 0;
for (ll i = 0; i < 60; i++) {
ll prevneed = max(x - a[i], 0LL);
//printf("%lld %lld\n", i, prevneed);
if (prevneed <= (cursum >> i) && (cursum - (prevneed << i)) >= 0) {
ll maxlast = (cursum - (prevneed << i)) / x;
maxlast = min(maxlast, (1LL << i) - 1);
//printf("%lld %lld ", i, maxlast);
Node* dupnode = root;
for (int j = 1; j <= 61 - i; j++) dupnode = dupnode->left;
Node* resnode = clone(dupnode->left, i, maxlast);
//printf("%lld %lld\n", dupnode->left->count, resnode->count);
dupnode->right = resnode;
dupnode = root; root->count += resnode->count;
for (int j = 1; j <= 61 - i; j++) {
dupnode = dupnode->left;
dupnode->count += resnode->count;
}
}
cursum += (a[i] << i);
}
return root->count;
}
