Balance beam (2) P45300
A gymnast is at the midpoint of a balance beam of length m. The gymnast must jump n times forward or backward, never leaving the bar. The i-th jump has length ℓi. Write a program to computes in how many ways the gymnast can finish the exercise at every position. The gymnast cannot skip any jump, nor change the order of the jumps.
Input
Input consist of the length m, the number n, and the lengths ℓ1, …, ℓn. Assume 2 ≤ m ≤ 103, that m is even, 0 ≤ n ≤ 104, and 1 ≤ ℓi ≤ 100.
Output
Assuming that the initial position is 0 (hence, the valid positions belong to [−m/2, m/2]), print in order the positions where the gymnast can finish, together with the number of ways modulo 108 + 7.
Input
1000 3 100 10 1
Output
-111 1 -109 1 -91 1 -89 1 89 1 91 1 109 1 111 1
Input
40 2 10 10
Output
-20 1 0 2 20 1
Input
1000 0
Output
0 1
Input
10 1 100
Output
Input
30 4 5 1 20 2
Output
-12 1 12 1
Input
6 5 1 1 1 1 1
Output
-3 4 -1 10 1 10 3 4
Input
100 36 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Output
-36 1 -34 36 -32 630 -30 7140 -28 58905 -26 376992 -24 1947792 -22 8347680 -20 30260340 -18 94143280 -16 54186842 -14 805254 -12 51677616 -10 10789439 -8 96296941 -6 67902175 -4 7871599 -2 97496005 0 75134670 2 97496005 4 7871599 6 67902175 8 96296941 10 10789439 12 51677616 14 805254 16 54186842 18 94143280 20 30260340 22 8347680 24 1947792 26 376992 28 58905 30 7140 32 630 34 36 36 1
- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++