| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
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