FPS Composition and Compositional Inverse

Revision en1, by maspy, 2024-04-24 16:36:36

Hello.

I am Japanese and have been publishing some articles within the Japanese-speaking community for some time now. This is my first attempt at translating one of my Japanese explanatory articles into English. (This is also the first CodeForces blog for me).

The theme is the computation of formal power series composition and compositional inverse.

A method to improve the known computational complexity for this theme was introduced by noshi91 in March 2024.

Several blogs about this topic have been written within the Codeforces community.

However, I couldn't find any blogs, in Japanese or English, that thoroughly explore the following topics:

  • How to implement them with a better constant factor.
  • How to derive and implement the Composition Algorithm using Transposition Principle.

Therefore, I decided to explain this topic myself.


I have studied English to some extent, but I'm not very proficient. I received assistance from ChatGPT for translating many parts of the article. However, there might still be some incorrect English expressions remaining. If you notice any issues, please feel free to provide feedback.

If you find the article interesting, you can also support me through GitHub sponsors.

Actually, there is another article that has been requested for English translation, but I've left them untouched for quite some time. Maybe it's time to take on that translation challenge as well.

Thank you for reading.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English maspy 2024-04-24 16:36:36 2373 Initial revision (published)