## An FFT Problem VI

View as PDF

Points: 30
Time limit: 10.0s
Java 15.0s
PyPy 2 20.0s
PyPy 3 20.0s
Memory limit: 256M

Author:
Problem type

#### Statement

Alice and Bob have huge dice where the possible roll values are from $$0$$ to $$N$$ (inclusive).

These huge dice have many many faces. In particular, Alice's die has $$A_i$$ faces with roll value $$i$$, while Bob's die has $$B_j$$ faces with roll value $$j$$.

Alice and Bob roll their dice at the same time. Their score is the sum of their roll values. Alice and Bob are wondering: for each of the possible scores $$s$$ from $$0$$ to $$2N$$ (inclusive), how many different ways could they have have rolled the score $$s$$?

Two ways are considered different if Alice rolls a different face or Bob rolls a different face, regardless of their value.

#### Constraints

• $$1 \leq N \leq 10^6$$
• $$1 \leq A_i, B_j \leq 10^6$$

#### Input Specification

The first line of input will contain $$N$$.

The second line of input will contain $$N + 1$$ space-separated integers, $$A_0, A_1, \dots A_N$$.

The third line of input will contain $$N + 1$$ space-separated integers, $$B_0, B_1, \dots B_N$$.

#### Output Specification

One line containing space-separated $$2N + 1$$ integers, the number of ways that a score of $$0, 1, 2, \dots 2N$$ can be rolled.

#### Sample Input 1

3
1 2 3 4
5 6 7 8

#### Sample Output 1

5 16 34 60 61 52 32

#### Explanation for Sample 1

The fifth number in the output, $$61$$, represents the number of ways to get a score of $$4$$.

There are $$3$$ cases of this happening:

1. Alice rolls a $$1$$ and Bob rolls a $$3$$. Alice has $$2$$ faces with value $$1$$ and Bob has $$8$$ faces with value $$3$$. There are $$2 \times 8 = 16$$ ways to roll a $$3$$ in this case.

2. Alice rolls a $$2$$ and Bob rolls a $$2$$. Alice has $$3$$ faces with value $$2$$ and Bob has $$7$$ faces with value $$2$$. There are $$3 \times 7 = 21$$ ways to roll a $$3$$ in this case.

3. Alice rolls a $$3$$ and Bob rolls a $$1$$. Alice has $$4$$ faces with value $$3$$ and Bob has $$6$$ faces with value $$1$$. There are $$4 \times 6 = 24$$ ways to roll a $$3$$ in this case.

The total of these cases is $$61$$.

#### Sample Input 2

15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#### Sample Output 2

17 52 106 180 275 392 532 696 885 1100 1342 1612 1911 2240 2600 2992 3095 3164 3198 3196 3157 3080 2964 2808 2611 2372 2090 1764 1393 976 512