Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

問題案:2変数 FPS operations #1145

Open
maspypy opened this issue May 3, 2024 · 2 comments
Open

問題案:2変数 FPS operations #1145

maspypy opened this issue May 3, 2024 · 2 comments
Labels

Comments

@maspypy
Copy link
Collaborator

maspypy commented May 3, 2024

  • Inv of 2-variable Formal Power Series
  • Exp of 2-variable Formal Power Series
  • Log of 2-variable Formal Power Series
  • Pow of 2-variable Formal Power Series
  • Sqrt of 2-variable Formal Power Series
  • Inv of 2-variable Formal Power Series (Sparse)
  • Exp of 2-variable Formal Power Series (Sparse)
  • Log of 2-variable Formal Power Series (Sparse)
  • Pow of 2-variable Formal Power Series (Sparse)
  • Sqrt of 2-variable Formal Power Series (Sparse)

たまに欲しくなるので、入れてはどうでしょうか。積 $NM$ を通常の制約で抑える感じかな。


整備が上手なら multi-variable と実装量はあんまり変わらないかもしれません
(例えば @NyaanNyaan さんはそのように実装していると思う)

@NyaanNyaan
Copy link
Collaborator

あまり詳しくはないんですが検索した感じ "Bivariate Formal Power Series" という表現の方がよく使われているようです。

多変数 FPS を持っていれば確かに 2 変数に限定する必要は無いですが、

  • 多変数 FPS を 2 変数以外で使った記憶がほとんど無い
  • 2 変数に特化した高速化がありそう

などの理由から 2 変数で準備してよさそうに思いました。

@maspypy
Copy link
Collaborator Author

maspypy commented May 4, 2024

  • sqrt
    • $[x^0y^0]f\neq$ の場合について sqrt を定義しないことの方が一般的だと思われるし、そうでない場合を考える実用上の動機もないと思っているので、 $[x^0y^0]f=1$ を制約にしてしまいたい。(そもそも pow の特殊ケースだし、問題を作る優先度はかなり低そう)
  • pow
    • こっちは $[x^0y^0]f=0$ のときも自然だし実用しうる。がこのときに繰り返し二乗法よりよくなるか不明
    • sparse は $O(NMK)$ でできると思う

@maspypy maspypy added the contributions-welcome 審査済み label May 8, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

2 participants