AtCoder AGC 005 F - Many Easy Problems (銅色, 1900 点)

Polynomial Taylor Shift が使えた！問題へのリンク問題概要頂点数の木が与えられる。各に対して、次の問いに答えよ。頂点から個の頂点を選ぶ通りの方法それぞれについてその個の頂点をすべて含む連結な部分グラフのサイズとして考えられる最小値…

2023-09-08

Yosupo Library Checker - Polynomial Taylor Shift

YosupoLibraryChecker 多項式:PolynomialTalyorShift 多項式・FPS(形式的冪級数) FFT 高速畳み込み計算数学(代数)

面白かった！問題へのリンク問題概要整数係数の多項式と、整数定数が与えられる。を展開したときの各係数を 998244353 で割った余りを求めよ。制約考えたこと Polynomial Taylor Shift については、次の記事に詳しく書いた。計算量はとなる。 drken…

2023-09-08

「Polynomial Taylor Shift」に学ぶ畳み込み芸

テーマ解説記事多項式:PolynomialTalyorShift 多項式・FPS(形式的冪級数) FFT 高速畳み込み計算式変形数学(代数) 式変形テク:シグマの入れ替え考察：主客転倒・寄与分解

Polynomial Taylor Shift を履修したので、簡単にまとめてみます。例によって、Yosupo Library Checker の問題を通します。なお、Polynomial Taylor Shift の解法は、単なるライブラリ整備の一環とみなすというよりは、その導出過程をぜひ押さえておきた…