Блог пользователя sdssudhu

Help With FFT
Автор sdssudhu, история, 6 лет назад, По-английски

This is the snippet I have for FFT. But I feel it is slow in many cases.

One example is http://mirror.codeforces.com/problemset/submission/958/41610928 which takes nearly 3.85 seconds to pass for n=200000

Can somebody help me to optimise it.

Thanks.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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).

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yeah. In this case I did that to get AC. But how to improve it in general ??

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      In case of this problem, maybe I'm blind but I see you using fft_modulo instead of mul which is definetely use sqrt(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 and w in your code) — it gives boost with multiple using of mul. Precalcing bit 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.

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Oh sorry. I misunderstodd your first comment.

        And thanks for the pre-calculation parts.

        → Ответить