Back To School '18: An FFT Problem

View as PDF

Submit solution



Points: 12 (partial)
Time limit: 2.0s
Memory limit: 128M
Author:

Problem type

To prepare for the upcoming school year, Richard has bought N books for his English class. Each book is assigned a value, a_i, Richard's willingness to read that book.

Richard wants to choose k of the N books and calculate his willingness to read those k books. The willingness to read those k books is the product of the willingness to read each individual book. For example, if he bought books of value a = [2, 5, 7, 9, 13], and he chose k = 3 books with indices 1, 2, 4, the willingness to read those books would be a_1 \cdot a_2 \cdot a_4 = 2 \cdot 5 \cdot 9 = 90.

Richard wants the sum of the willingness of all distinct combinations of k books for all values of k\ (1 \le k \le N).

However, since Richard does not like large numbers, he wants each sum modulo 998244353.

Two combinations are considered distinct if the indices of the books chosen are different, regardless of the values of the books.

Input Specification

The first line of input will contain a single integer N\ (1 \le N \le 2\ 000), the number of books that Richard bought.

The second line of input will contain N space-separated integers, the i^{th} integer representing a_i\ (|a_i| \le 10^9), the value of each book.

Output Specification

On one line, print N space-separated integers, the k^{th} integer representing the sum of the willingness of all distinct combinations of choosing k books, modulo 998244353.

We define A modulo B in the 2 equivalent ways:

  1. Taking the remainder of A \div B, adding B if the result is negative.
  2. Subtracting B from A, or adding B to A, until A is in the interval [0, B).

It may or may not help to know that 998244353 = 119 \cdot 2^{23} + 1.

Subtasks

Subtask 1 [5%]

N \le 10

Subtask 2 [10%]

N \le 20

Subtask 3 [35%]

|a_i| \le 10^3

Subtask 4 [50%]

No further constraints.

Sample Input 1

4
1 2 2 3

Sample Output 1

8 23 28 12

Explanation for Sample Input 1

N = 4, a = [1, 2, 2, 3].


There are 4 distinct combinations to read 1 book:

a_1 = 1

a_2 = 2

a_3 = 2

a_4 = 3

Their sum is 8.


There are 6 distinct combinations to read 2 books.

a_1 \cdot a_2 = 1 \cdot 2 = 2

a_1 \cdot a_3 = 1 \cdot 2 = 2

a_1 \cdot a_4 = 1 \cdot 3 = 3

a_2 \cdot a_3 = 2 \cdot 2 = 4

a_2 \cdot a_4 = 2 \cdot 3 = 6

a_3 \cdot a_4 = 2 \cdot 3 = 6

Their sum is 23.


There are 4 distinct combinations of reading 3 books.

a_1 \cdot a_2 \cdot a_3 = 1 \cdot 2 \cdot 2 = 4

a_1 \cdot a_2 \cdot a_4 = 1 \cdot 2 \cdot 3 = 6

a_1 \cdot a_3 \cdot a_4 = 1 \cdot 2 \cdot 3 = 6

a_2 \cdot a_3 \cdot a_4 = 2 \cdot 2 \cdot 3 = 12

Their sum is 28.


The only distinct combination of reading 4 books is a_1 \cdot a_2 \cdot a_3 \cdot a_4 = 1 \cdot 2 \cdot 2 \cdot 3 = 12.

Sample Input 2

3
-1 -1 -1

Sample Output 2

998244350 3 998244352

Comments

There are no comments at the moment.