search

kanpurin / kyoprolibrary

1 stars 0 forks source link

FormalPowerSeriesの逆関数を求める #10

Closed kanpurin closed 1 year ago

kanpurin commented 2 years ago

F(x)に対し、F(G(x))=xとなるようなG(x)をO(N\log{N})で求める。 [x^0]F(x)=0, [x^1]F(x)≠0である必要がある。

どんなF(x)でも求められるのかは分からない。

ニュートン法で求められるらしい？ https://atcoder.jp/contests/nadafes2022_day2/editorial/3871

kanpurin commented 2 years ago

これが求められれば https://codeforces.com/blog/entry/77551 より[x^k]f(x)^i(1<= i<= n)が高速に求められる

kanpurin commented 2 years ago

https://mojacoder.app/users/radix_sort/problems/biscuit_de_noel こういうのも高速になる

kanpurin commented 2 years ago

https://fredrikj.net/math/reversion.pdf 本当にO(N\log{N})でできるのか

kanpurin commented 1 year ago

無理そう