← 返回题目列表

Codeforces · 1912/J

J. 神奇宝贝观察的乐趣

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Joy of Pokémon Observation - 原题 PDF 第 1 页
原题PDF第13页
可复制的 PDF 提取文本
ICPC 2023–2024, NERC – Northern Eurasia Finals
                       St. Petersburg, Novosibirsk, Astana, Kutaisi, December 13th, 2023
Problem J. Joy of Pok´emon Observation

    Time limit:        3 seconds
    Memory limit:     1024 megabytes

The Pok´emon Conservation Society protects Pok´emon and their habitats all around the globe. In recent
research, data about h habitats was collected.

Each habitat may be inhabited by several Pok´emon species. Researchers know how many limbs each
species has. Pok´emon are swift and extremely good at hiding, so researchers were only able to detect the
total number of limbs in each of the habitats.

Researchers understand that it might not be possible to find the population of each species, but would
like to understand how much uncertainty is left. How many different combinations of Pok´emon would
have the observed number of limbs?

Input

The first line contains a single integer h (1 ≤h ≤1 024) — the number of habitats. The next h lines
contain the description of each habitat.
Each line starts with two integers t and s (0 ≤t ≤109, 1 ≤s ≤3), where t is the total number of limbs,
and s is the number of species in the habitat. They are followed by s integers li (1 ≤li ≤16) — the
number of limbs for each species.

Output

Output the number of possible combinations of Pok´emon in each habitat. Output should contain h lines
with a single integer.

Examples

             standard input                          standard output
 3                                       1
 6 1 3                                   2
 6 2 2 3                                 7
 6 3 1 2 3

 4                                       500000001500000001
 1000000000 3 1 1 1                      1
 0 3 2 4 5                               0
 17 2 2 4                                25
 34 3 5 3 2

Note

For the sake of example we will use LATEX Pok´emon: ¸O has one limb, ∠has two limbs, ∃has three limbs.
In the first example all three habitats have 6 limbs.

In the first example the first habitat has only one Pok´emon species — ∃. So it is likely the young family
containing ∃∃.

In the second habitat there are two Pok´emon species: ∠and ∃. So it is either ∠∠∠or ∃∃.

The third habitat may contain any of the three Pok´emon species: ¸O, ∠and ∃. There are seven possible
combinations: ∃∃, ∠∠∠, ¸O∠∃, ¸O¸O∠∠, ¸O¸O¸O∃, ¸O¸O¸O¸O∠, ¸O¸O¸O¸O¸O¸O.

In the second example the first habitat has three Pok´emon species, but all of them have only one limb:
                                ∑i≤109
∂, ¸O and ρ. There are 109 limbs and   i=0  (i + 1) combinations.
In the second habitat no limbs were detected. So there are unfortunately no Pok´emon left in the area.

In the third habitat all Pok´emon have an even number of limbs, so it is not possible to have 17 limbs.


                                        Page 13 of 15