#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
/*
key: all prefix is less than -> valid solution
*/
long long count_tastiness(long long x, vector<long long> a) {
a.resize(60);
vector<long long> sum(60,0);
for(int i = 0;i < 60;i++){
if(i > 0) sum[i] = sum[i-1];
sum[i] += a[i]*(1LL << i);
}
vector<long long> limit(60);
for(int i = 0;i < 60;i++){
limit[i] = min((1LL<<(i+1))-1,sum[i]/x);
}
map<long long,long long> mp;
mp[(1L << 60)-1] = 1;
for(int i = 59;i >= 0;i--){
map<long long,long long> nmp;
for(auto &[rclim,rcnt]:mp){
long long clim = rclim,cnt = rcnt;
clim = min(clim,limit[i]);
if(clim >= (1LL << i)){
nmp[(1LL << i)-1] += cnt;
clim -= (1LL << i);
}
nmp[clim] += cnt;
}
swap(mp,nmp);
}
long long tot = 0;
for(auto [clim,cnt]:mp){
tot += cnt;
}
return tot;
}
