This link shows the algorithm that uses FFT to find differences of all pairs in an array. Can anyone explain how is this working or prove that it gives correct answer.
It looks like it is using the algorithm of finding pairwise sum using FFT.
№ | Пользователь | Рейтинг |
---|---|---|
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 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
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 |
Proof of this algorithm
This link shows the algorithm that uses FFT to find differences of all pairs in an array. Can anyone explain how is this working or prove that it gives correct answer.
It looks like it is using the algorithm of finding pairwise sum using FFT.
Название |
---|