#include "biscuits.h"
#include <numeric>
#include <cstdio>
long long count_tastiness(long long x, std::vector<long long> a) {
int k = (int) a.size();
std::vector<long long> dp(k + 1);
std::vector<int> flag(k + 1, true);
dp[0] = 1;
for (int i = 0; i < k; ++i) {
std::vector<int> digit(i);
long long cur = 0;
for (int j = 0; j < i; ++j) {
cur += a[j];
digit[j] = (cur & 1);
cur /= 2;
}
cur += a[i];
dp[i + 1] = dp[i];
if (cur < x) {
flag[i] = false;
continue;
}
if (i < k - 1 && cur >= 2 * x) {
dp[i + 1] *= 2;
continue;
}
// fprintf(stderr, "i = %d, cur = %lld\n", i, cur);
dp[i + 1] *= (cur / x);
cur %= x;
// fprintf(stderr, "i = %d, cur = %lld, dp[i + 1] = %lld\n", i, cur, dp[i + 1]);
bool tmp = true;
for (int j = i - 1; j >= 0; --j) {
cur = cur * 2 + digit[j];
if (cur >= x) {
dp[i + 1] += dp[j];
if (!flag[j]) {
tmp = false;
break;
}
cur -= x;
}
}
dp[i + 1] += tmp;
}
// for (int i = 0; i <= k; ++i) {
// fprintf(stderr, "dp[1 << %d == %lld] = %lld\n", i, 1ll << i, dp[i]);
// }
return dp[k];
}
