スパークリング黒ココア/多項式の計算とか色々

Created Mon, 25 Sep 2023 Modified Tue, 26 Sep 2023 09:13:30 +0000
600 Words
競プロ FPS NTT FFT 分からない

話のきっかけ

  • ABC321F
  • 終わった後のTLで強い皆さまが「FPS！」「FPS！」って連呼してたので気になって履修したいなと。

今黒ココアさんがわかってること

  • DPで行うような数え上げを、多項式で表現できる（すごい）
    • 何か、$x^d$の、係数に、数が反映される、っぽい。（かっこいい）
  • noko氏の解説でやってるようなこと
  • maspy氏のまとめた関連問題集
  • numpyでも多項式書けたけどこれじゃ不便っぽい？（modとったり？）
  • FPS=けいしきてきべききゅうすう（形式的ベキ級数）を英語に直したものを頭文字取って略したもの
  • かつっぱ氏もバタフライ演算？的なこと言ってた？（何してるのかはよく分からない）
    • 色んな人のライブラリとか色々見るとやっぱりdef butterflyみたいなのがあるから使うっぽい（何してるかはよく分からない）

ふんわりとそれっぽい気配を感じていること

  • FPSは、UnionFindみたいな「これ貼ればFPS使えるよ」みたいな話ではない、っぽい？
    • 考察の道具？とかいう説もある？
  • とりあえず多項式で色々表現できるよね
    • 多項式で表現だったり計算だったりする際に、速い計算が必要だったりとか例外で困ったケースとかがあるらしい？
      • その対応としてFPSとかNTTとかFFTとかが出てくる？（概念？）
  • なんか、modintが必要？っぽい？
  • なんか、convolutionとか使うっぽい？

現状の結論

  • 大人しくDPしましょうね、って話…？？？