Background

Note: This problem only supports submissions in C++ and you should not use C++14 (GCC 9).

You do not need to add the following in your code:

#include "biscuits.h"

Problem Description

Aunt Khong is organizing a contest with $x$ participants, and she plans to give each participant a bag of biscuits. There are $k$ different types of biscuits, numbered from $0$ to $k-1$. Each biscuit of type $i$ $(0 \le i \le k-1)$ has a tastiness value of $2^i$. In Aunt Khong’s food storage, there are $a[i]$ (possibly $0$) biscuits of type $i$.

For each biscuit type, Aunt Khong may put $0$ or more biscuits of that type into each bag. Across all bags, the total number of type $i$ biscuits used must not exceed $a[i]$. The sum of tastiness values of all biscuits in a bag is called the total tastiness of that bag.

Please help Aunt Khong compute how many different values of $y$ exist such that she can pack $x$ bags of biscuits and the total tastiness of every bag is exactly $y$.

Implementation Details

You need to implement the following function:

long long count_tastiness(long long x, std::vector<long long> a)

• $x$: the number of biscuit bags to pack.
• $a$: an array of length $k$. For $0 \le i \le k-1$, $a[i]$ is the number of type $i$ biscuits in the food storage.
• This function should return the number of distinct values of $y$ such that Aunt Khong can pack $x$ bags and every bag has total tastiness $y$.
• This function will be called $q$ times (for allowed values of $q$, see Constraints and Subtasks). Each call should be considered an independent scenario.

Input Format

See Implementation Details.

Output Format

See Implementation Details.

Hint

Sample Explanation

Example 1

Consider the following call:

count_tastiness(3, [5, 2, 1])

This means Aunt Khong wants to pack $3$ bags, and there are $3$ biscuit types in the food storage in total:

• $5$ biscuits of type $0$, each with tastiness $1$,
• $2$ biscuits of type $1$, each with tastiness $2$,
• $1$ biscuit of type $2$, with tastiness $4$.

The possible values of $y$ are $[0,1,2,3,4]$. For example, to pack $3$ bags each with total tastiness $3$, Aunt Khong can pack them like this:

• one bag contains $3$ biscuits of type $0$, and
• two bags each contain one type $0$ biscuit and one type $1$ biscuit.

Since there are $5$ possible values of $y$ in total, the function should return $5$.

Example 2

Consider the following call:

count_tastiness(2, [2, 1, 2])

This means Aunt Khong wants to pack $2$ bags, and there are $3$ biscuit types in the food storage in total:

• $2$ biscuits of type $0$, each with tastiness $1$,
• $1$ biscuit of type $1$, with tastiness $2$,
• $2$ biscuits of type $2$, each with tastiness $4$.

The possible values of $y$ are $[0,1,2,4,5,6]$. Since there are $6$ possible values of $y$ in total, the function should return $6$.

Constraints

• $1 \le k \le 60$.
• $1 \le q \le 1000$.
• $1 \le x \le 10^{18}$.
• $0 \le a[i] \le 10^{18}$ (for all $0 \le i \le k-1$).
• For each call to count_tastiness, the total sum of tastiness values of all biscuits in the food storage does not exceed $10^{18}$.

Subtasks

1. (9 points) $q \le 10$, and for each call to count_tastiness, the total sum of tastiness values of all biscuits in the food storage does not exceed $10^5$.
2. (12 points) $x = 1, q \le 10$.
3. (21 points) $x \le 10^4, q \le 10$.
4. (35 points) For each call to count_tastiness, the correct return value does not exceed $2 \times 10^5$.
5. (23 points) No additional constraints.

Example Grader

The example grader will read input data in the following format. The first line contains an integer $q$. Then there are $q$ pairs of two lines, each describing one scenario in the format below:

Line $1$: $k\ x$
Line $2$: $a[0]\ a[1]\ \ldots\ a[k-1]$

The output format of the example grader is:

Line $i$ $(1 \le i \le q)$: the return value of count_tastiness for the $i$-th scenario in the input data.

Translated by ChatGPT 5