Viet_love_KA's blog

Searching for template for polynomials operation
By Viet_love_KA, history, 4 weeks ago, In English

Currently I am learning about generating functions and some problems of this type requires polynomials operation such as multiplication and exponents. But I cannot figure out what template to use. There are some templates such as CP-algorithms but I cannot digest it because it includes so many libraries that I cannot remember to use in some competitions. So can someone give a easy to comprehend template for Polynomials.

Requirements:

FFT , NTT for mod like 998244353 and 1e9+7 .

Logarithm of polynomials .

Exponent of polynomials .

Hopefully someone can share the link.

Thank you.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Try this? https://github.com/ngthanhtrung23/ACM_Notebook_new/tree/master/Math/Polynomial

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks. But can you give me a one that have exponent and logarithm also

    → Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

https://sotanishy.github.io/cp-library-cpp/math/polynomial.cpp (click Bundle next to Copy to include NTT with it)

Also you would need a modint<int m> class with common operations and static int modint::mod() getter for NTT to work.

→ Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Check this blog: https://codeforces.me/blog/entry/65848

It has everything you need here: https://cp-algorithms.com/algebra/polynomial.html#basic-implementation

→ Reply