### PROBLEM LINK:

**Author:** Misha Chorniy

**Tester:** Tuan Anh Tran Dang

**Translators:** Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)

**Editorialist:** Tuan Anh Tran Dang

# Difficulty

MEDIUM

# PREREQUISITE

# PROBLEM

Given some integers in the ranges **[1…N]** you have **Q** query to answer each have the form of whether you can create a sum of **X** from those numbers (one number can be used multiple times).

# SOLUTION

We will need to use Fast Fourier transform in this problem. For those who do not familiar with the technique it is a method that help us do polynomial multipliation in **O(NlogN)** whe **N** is the degree of the polynomial. You can still read this editorial to see how polynomial multiplication can be applied to solved this problem before digging into the *FFT*.

Consider the polynomial A, B which have coefficients of only **0** or **1**. Let C is the polynomial which is the product of A and B. We can see that the coefficients **c_i** of **C** will be **c_i = Sum of a_x * b_y** where **a_x and b_y** are some coefficients of **A** and **B**. **c_i** is positive only when there is at least **a_x** and **b_y** that equal to **1** and **x + y = i**. With that we can apply the polynomial multiplication to find with the given set of number which number can be created by adding two number in the set. Consider the following example:

```
A = x^2 + x^3 + x^5
C = A * A = x^4 + 2*x^5 + 3x^6 + 2x^8 + x^10
we can see that the positive coefficients of C is which can be express as the sum of two coefficients of A.
4 = 2 + 2
5 = 2 + 3
6 = 3 + 3
8 = 3 + 5
10 = 5 + 5
```

So now you may guess how we solve this problem. Notices that we can use same number many times. Let create a polynomial **A** of degree **200000** with the coeffient **a_i = 1** if we have number **i** (to create sums). **A^2** will let us know which sum can be created by adding at most two numbers from the set. Notice that we should have **a_0 = 1**. Similarly **A^4** will show which sum can be created by at most 4 numbers (one number can appear more than once). So basically we just need to calculate **A ^ (2^k)** where **2^k ≥ N**. And of course we only care about the first **200000** coefficients. Now we got our first solution which is multiply the polynomial **A** with itself **logN** times. After that the positive coefficients will corressponding to the sums that can be created. **logN** multiplications take us **O(Nlog^2N)** - quite good but will not pass the time limit.

One observation can be made is that the larger numbers appear fewer times in the sum so that we can ignore them in the early multiplications. For example **100001** can appear at most once in the sum so we can only add it in the later multiplications.

More specifically we have **Logn** steps, at the **ith** step, we try to see which numbers in the range **[0…2 ^{i}]** can be created. Let see how we can calculate for each step based on the previous step.

After completed step **i - 1** we can have an vector of ** 0s ** and ** 1s** where the **kth** item quals to **1** means that we can create number **k**. Let enlarge the vector to have **2 ^{i}** items and set

**1**at the right places corresponding to the values of

**F**. Now the question is how to find all number can be created in the range

**[0…2**. One might say that just multiply

^{i}]**a**with it self but that is incorrect. Let’s see an example:

```
After 3rd step we have a = 10000100 which means in the range [0..7] only 0 and 5 can be created.
At 4th step we need to find in the range [0..15] which numbers can be created. For simplicity let assume that we do not have any F in the range [8..15].
If we just multiply a with it self we only got 0, 5 and 10 and missed 15 = 5 + 5 + 5.
```

The correct solution is multiply **a** with it self twice. The prof of this is left for you as an exercise.

So with this improve we saved a great deal of calculation. In fact this will give us the complexity of **O(1log1 + 2log2 + 4log4 + … + n Logn) = O(nlogn)**.