An FFT Problem V

View as PDF

Submit solution

Points: 35
Time limit: 5.0s
Memory limit: 256M

Author:
Problem type

I have a 1-indexed array named a with N elements.

I define a k-product as taking a subset of size k from the set \{1, 2, 3, ..., N\} and taking the product of the values of a at those indexes.

For example, if a = [2, 5, 7, 9, 13], one valid 3-product is a_1 \times a_2 \times a_4 = 2 \times 5 \times 9 = 90.

I define a k-sum of an array as the sum of all distinct k-products that can be formed with it. Two k-products are considered distinct if the subset of indexes are different, regardless of the values at the indexes.

For all 1 \leq k \leq N, find the k-sum of a, each modulo 998244353.

Input Specification

The first line of input will contain a single integer N.

The second line of input will contain N space-separated integers, the i^{th} integer representing a_i.

Output Specification

On one line, print N space-separated integers, the i^{th} integer representing the i-sum of a, 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).

Constraints

(1 \leq N \leq 200 000)

(|a_i| \leq 10^9) for all (1 \leq i \leq N)

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

Please note that this problem does not have partials enabled.

Sample Input

4
1 2 2 3

Sample Output

8 23 28 12

Explanation for Sample Input

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

There are 4 distinct 1-products:

a_1 = 1

a_2 = 2

a_3 = 2

a_4 = 3

Their sum is 8.


There are 6 distinct 2-products.

a_1 \times a_2 = 1 \times 2 = 2

a_1 \times a_3 = 1 \times 2 = 2

a_1 \times a_4 = 1 \times 3 = 3

a_2 \times a_3 = 2 \times 2 = 4

a_2 \times a_4 = 2 \times 3 = 6

a_3 \times a_4 = 2 \times 3 = 6

Their sum is 23.


There are 4 distinct 3-products.

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

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

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

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

Their sum is 28.


The is one 4-product

1 \times 2 \times 2 \times 3 = 12.

The sum is 12.


Comments

There are no comments at the moment.