An FFT Problem VI

View as PDF

Submit solution


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

Comments

There are no comments at the moment.