P6836 [IOI 2020] Packing Biscuits

### 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: ```cpp #include "biscuits.h" ```

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: ```cpp long long count_tastiness(long long x, std::vector 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.

See Implementation Details.

See Implementation Details.

#### Sample Explanation #### Example 1 Consider the following call: ```cpp 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: ```cpp 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