#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 64;
const long long inf = (1LL << 62);
int n;
long long x;
long long a[maxn];
struct key
{
int pos;
long long mx;
inline friend bool operator < (const key& x, const key& y)
{
return x.pos < y.pos || (x.pos == y.pos && x.mx < y.mx);
}
};
map<key, long long> dp;
long long s[maxn];
long long f(int pos, long long mx)
{
if (mx < 0)
{
return 0;
}
if (pos == -1)
{
return 1;
}
if (mx > ((1 << pos) + 1))
{
return 1;
}
if (dp.find({pos, mx}) != dp.end())
{
return dp[{pos, mx}];
}
long long result = f(pos - 1, min(mx, (1LL << pos) - 1));
result += f(pos - 1, min(mx, s[pos] / x) - (1LL << pos));
return dp[{pos, mx}] = result;
}
long long count_tastiness(long long X, vector<long long> arr)
{
n = arr.size();
x = X;
for (int i = 0; i < n; ++i)
{
a[i] = arr[i];
}
for (int i = 0; i < maxn; ++i)
{
if (i < n)
{
s[i] = a[i] * (1LL << i);
}
else
{
s[i] = 0;
}
if (i >= 1)
{
s[i] += s[i - 1];
}
}
return f(60, inf);
}
/*
1
3 3
5 2 1
1
3 2
2 1 2
2
3 3
5 2 1
3 2
2 1 2
*/
