| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 1 | 1 | 1 | 100.000% |
There are $N$ members in the parliament, and each one of them is a representative of one of the $K$ parties. Now the parties have to form a ruling colation.
For a coalition to be able to rule, it needs a majority in the parliament. On the other hand, the more parties in the coalition, the less stable it is because of possible differences of opinion. Thus, a coalition that would still have a majority in the parliament after excluding some of the parties in it is not very sensible.
More precisely, a group of parties can form a stable coalition under two conditions:
Count the number of possible groups that could form stable coalitions.
The first line of input contains $N$, the number of seats in the parliament, and $K$, the number of parties ($1 \le N \le 10^{18}$, $1 \le K \le 36$). The second line contains $K$ integers $M_1$, $M_2$, $\ldots$, $M_K$ ($1 \le M_i \le N$), where $M_i$ is the number of members of the parliament in the $i$-th party. It is guaranteed that $M_1 + M_2 + \cdots + M_K = N$.
The only line of output should contain a single integer: the number of possible stable coalitions.
14 5 6 2 1 4 1
4
Let's denote the parties as $a$, $b$, $c$, $d$, $e$ from left to right. Then the possible stable coalitions are: $$\begin{equation*} \{a, b\}, \qquad \{a, d\}, \qquad \{a, c, e\}, \qquad \{b, c, d, e\}. \end{equation*}$$ The group $\{a, c\}$ can't be a coalition, because they do not have more than $\frac{N}{2} = 7$ members of parliament in total. The group $\{a, b, c\}$ can't be a stable coalition, because after excluding $c$ it becomes $\{a, b\}$, which still has majority in the parliament.
8 8 1 1 1 1 1 1 1 1
56
Any group of 5 parties can form a stable coalition, so the answer is $C^5_8 = 56$.
101 6 34 25 19 12 10 1
5