#include "biscuits.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <map>
typedef long long llong;
const int MAXN = 64;
const llong INF = 1e18;
struct Key
{
int bit;
llong max;
friend bool operator < (const Key &a, const Key &b)
{
return a.bit < b.bit || (a.bit == b.bit && a.max < b.max);
}
};
int n;
llong x;
llong a[MAXN];
llong s[MAXN];
std::map <Key, llong> mem;
llong f(int bit, llong max)
{
if (max < 0)
{
return 0;
}
if (bit == -1)
{
return 1;
}
if (mem.count({bit, max}))
{
return mem[{bit, max}];
}
mem[{bit, max}] = f(bit - 1, std::min(max, s[bit]));
mem[{bit, max}] += f(bit - 1, std::min(max, s[bit]) - (1LL << bit));
return mem[{bit, max}];
}
llong count_tastiness(llong X, std::vector <llong> A)
{
n = A.size();
x = X;
for (int i = 0 ; i < n ; ++i)
{
a[i] = A[i];
s[i] = a[i] * (1LL << i);
if (i > 0) s[i] += s[i - 1];
}
for (int i = 0 ; i < n ; ++i)
{
s[i] /= x;
}
mem.clear();
return f(n - 1, INF);
}
