| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3803 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3627 |
| 4 | ecnerwala | 3584 |
| 5 | orzdevinwang | 3573 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | Radewoosh | 3542 |
| 9 | jqdai0815 | 3532 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 167 |
| 2 | awoo | 163 |
| 3 | adamant | 162 |
| 4 | maroonrk | 152 |
| 5 | -is-this-fft- | 151 |
| 5 | nor | 151 |
| 7 | atcoder_official | 147 |
| 8 | TheScrasse | 146 |
| 9 | Petr | 145 |
| 10 | pajenegod | 143 |
We have an array of N integers and Q queries. In each query, we are given an integer X. For each query, we have to output the number of unordered pairs in array that sum to X.
How can we efficiently answer these sort of queries?
Constraints:
1 <= N <= 2 * 105
1 <= Q <= 2 * 105
1 <= |ai| <= 1018
1 <= X <= 1018
Well this can't be done faster than $$$O(n*q)$$$ if you keep the constraints, however if you let $$$a[i] \leq 2*10^5$$$, then you've got yourself an FFT task. Consider a polynomial $$$cnt[1]*x^1+cnt[2]*x^2 +$$$ $$$...$$$ $$$+ cnt[m]*x^m$$$, if you square it you can get the number of pairs which add up to $$$k$$$ by taking the coefficient of $$$x^k$$$. Try to see why multiplying polymomials works by doing it for small $$$n$$$ on paper
Got it. Thanks
Also, I would need to cube the polynomial or raise to some appropriate sufficient power in case if k is greater than 2*m in order to obtain the term xk, right?