This is the snippet I have for FFT. But I feel it is slow in many cases.
One example is http://codeforces.net/problemset/submission/958/41610928 which takes nearly 3.85 seconds to pass for n=200000
Can somebody help me to optimise it.
Thanks.
# | 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 |
This is the snippet I have for FFT. But I feel it is slow in many cases.
One example is http://codeforces.net/problemset/submission/958/41610928 which takes nearly 3.85 seconds to pass for n=200000
Can somebody help me to optimise it.
Thanks.
Name |
---|
Since module is small (equal to 1009) in this task you don't need to use
sqrt(MOD)
hack and can manually multiply two polynoms (but don't forget to take resulting product modulo 1009 after each multiplification).Yeah. In this case I did that to get AC. But how to improve it in general ??
In case of this problem, maybe I'm blind but I see you using
fft_modulo
instead ofmul
which is definetely usesqrt(MOD)
-hack.Regarding optimizing in general case: I'm sure I've read many articles, but I can't find anything (maybe because they are on Russian). But standart trick are to precalc all roots (
wlen
andw
in your code) — it gives boost with multiple using ofmul
. Precalcingbit reverse
(or calculating it in the linear time) can give a little speed up.Anyway, you can always look at realization of fft from top participants if you have enough time and patience.
Oh sorry. I misunderstodd your first comment.
And thanks for the pre-calculation parts.