search

Harui-i / library

library for competitive programming
https://harui-i.github.io/library/
0 stars 0 forks source link

多項式を多項式で割った商と余り #14

Closed Harui-i closed 3 weeks ago

Harui-i commented 3 weeks ago

Library Checker: https://judge.yosupo.jp/problem/division_of_polynomials

mod 998244353で高速化したやつと、ナイーブな畳込みで解くやつどっちもほしいね。 てか998244353のみしかライブラリに無いのちょっと不便かもしれない。

  1. Garnerのアルゴリズムで復元するライブラリを書く
  2. ナイーブな$O(N$^2)$畳み込みで色々やるライブラリを書く

くらいの対処法がありそう。別に排反ではない。

Harui-i commented 3 weeks ago

解法について

  1. 目指せ全完!で紹介されているやつ

-https://qiita.com/hotman78/items/f0e6d2265badd84d429a#4%E5%A4%9A%E9%A0%85%E5%BC%8F%E3%81%A8%E3%81%97%E3%81%A6%E3%81%AE%E5%95%86%E4%BD%99%E3%82%8A:~:text=%E3%81%91%E3%81%BE%E3%81%9B%E3%82%93-,4.(%E5%A4%9A%E9%A0%85%E5%BC%8F%E3%81%A8%E3%81%97%E3%81%A6%E3%81%AE)%E5%95%86/%E4%BD%99%E3%82%8A,-(

など。reverseして$x^-1$を代入するっていうけど、どうしてそれが成立するのかわからんな。

Harui-i commented 3 weeks ago

なんかWolfram Alphaで計算させた感じでは、f.rev / g.rev を展開してN - M + 1項取ってきてまたrevするとqに一致するっぽいな

計算させたい式: https://www.wolframalpha.com/input?i=+%28x%5E5+%2B+2x%5E4+-x%5E3+%2B+4x%5E2+%2B+16x%29++%2F+%287x%5E3+%2B16x%5E2+-+5x+%2B+3%29

revした式: https://www.wolframalpha.com/input?i=+%28x%5E5+%2B+2x%5E4+-x%5E3+%2B+4x%5E2+%2B+16x%29++%2F+%287x%5E3+%2B16x%5E2+-+5x+%2B+3%29

Harui-i commented 3 weeks ago

解法について

  1. 目指せ全完!で紹介されているやつ

-https://qiita.com/hotman78/items/f0e6d2265badd84d429a#4%E5%A4%9A%E9%A0%85%E5%BC%8F%E3%81%A8%E3%81%97%E3%81%A6%E3%81%AE%E5%95%86%E4%BD%99%E3%82%8A:~:text=%E3%81%91%E3%81%BE%E3%81%9B%E3%82%93-,4.(%E5%A4%9A%E9%A0%85%E5%BC%8F%E3%81%A8%E3%81%97%E3%81%A6%E3%81%AE)%E5%95%86/%E4%BD%99%E3%82%8A,-(

など。reverseして$x^-1$を代入するっていうけど、どうしてそれが成立するのかわからんな。

Nyaanさんの 解説がわかりやすいな: https://nyaannyaan.github.io/library/fps/formal-power-series.hpp#:~:text=%E3%81%A7%E3%81%82%E3%82%8B%E3%80%82-,%E9%99%A4%E7%AE%97,-(%E6%B3%A8%EF%BC%9A%E3%81%93%E3%81%AE%E9%A0%85

Harui-i commented 1 week ago

コンピュータ代数ハンドブックにすべてが書いてありました。解決