maspy's blog

By maspy, history, 5 weeks ago, In English


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.

  • Vote: I like it
  • +241
  • Vote: I do not like it

5 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

I'm not aware of many articles on techniques to reduce the number of FFT iterations and specific applications of the transposition principle, not limited to this theme. Are there any prominent references within the CodeForces community?