#include "biscuits.h"
#include <vector>
#include <iostream>
#include <map>
using namespace std;
//x = number of people (p)
//y = tastiness of each bag (i)
const int mx = 64;
long long pow2[mx];
long long* sm = new long long[1+mx] + 1;
map<long long, long long> CT;
long long X;
vector<long long> A;
int I(long long z)
{
int I = 0;
while(pow2[I+1] <= z) I++;
return I;
}
long long Count(long long z)
{
// cerr << "count " << z << '\n';
if(z < 0) return 0;
else if(z == 0) return 1;
int i = I(z);
if(CT.find(z) == CT.end())
{
CT[z] = Count(pow2[i] - 1) + Count(min(sm[i]/X - pow2[i], z - pow2[i]));
}
return CT[z];
}
long long count_tastiness(long long x, vector<long long> a)
{
while((int)a.size() < mx) a.push_back(0);
CT.clear();
pow2[0] = 1;
for(int i = 1; i < mx; i++) pow2[i] = 2LL * pow2[i-1];
sm[-1] = 0;
for(int i = 0; i < mx; i++)
sm[i] = sm[i-1] + pow2[i]*a[i];
X = x;
A = a;
return Count(sm[mx-1]/x);
}
