406865: GYM102586 E Count Modulo 2
Memory Limit:1024 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
E. Count Modulo 2time limit per test3.5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output
You are given $$$K$$$ distinct nonnegative integers $$$A_1,A_2,\cdots,A_K$$$. Count the number of sequences of $$$N$$$ nonnegative integers $$$a_1,a_2,\cdots,a_N$$$ that satisfies all of the following conditions, modulo **$$$2$$$**.
- $$$a_1+a_2+\cdots+a_N=S$$$
- For each $$$i$$$ ($$$1 \leq i \leq N$$$), there exists an integer $$$j$$$ such that $$$a_i=A_j$$$.
Note that there are $$$T$$$ tests in one input file.
InputInput is given from Standard Input in the following format:
$$$T$$$
Description of the $$$1$$$-st test
Description of the $$$2$$$-nd test
$$$\vdots$$$
Description of the $$$T$$$-th test
The description of each test is in the following format:
$$$N$$$ $$$S$$$ $$$K$$$
$$$A_1$$$ $$$A_2$$$ $$$\cdots$$$ $$$A_K$$$
Constraints:
- $$$1 \leq T \leq 5$$$
- $$$1 \leq N \leq 10^{18}$$$
- $$$0 \leq S \leq 10^{18}$$$
- $$$1 \leq K \leq 200$$$
- $$$0 \leq A_1 < A_2 < \cdots < A_K \leq 10^5$$$
- All values in input are integers.
For each test, print the count modulo $$$2$$$.
ExampleInput2 5 10 3 1 2 3 1000000000000000000 25453321771239381 10 0 1683 21728 31623 35054 37834 39329 56842 68603 74742Output
1 0Note
In the first test, there are a total of $$$51$$$ sequences that satisfy conditions.