多項式:PolynomialTalyorShift
AtCoder
AtCoder1900点
AGC-F
銅色diff
グラフ
木
FFT
高速畳み込み計算
多項式:PolynomialTalyorShift
多項式・FPS(形式的冪級数)
二項係数
主客転倒
テク:線形和への分解
線形性に着目する
各kに対して
N個からK個を選ぶ設定の問題
f(i,j)をiとjとに分離する
補集合を考える
Polynomial Taylor Shift が使えた！ 問題へのリンク 問題概要 頂点数 の木が与えられる。各 に対して、次の問いに答えよ。 頂点から 個の頂点を選ぶ 通りの方法それぞれについて その 個の頂点をすべて含む連結な部分グラフのサイズとして考えられる最小値…
面白かった！ 問題へのリンク 問題概要 整数係数の多項式 と、整数定数 が与えられる。 を展開したときの各係数を 998244353 で割った余りを求めよ。 制約 考えたこと Polynomial Taylor Shift については、次の記事に詳しく書いた。計算量は となる。 drken…
Polynomial Taylor Shift を履修したので、簡単にまとめてみます。例によって、Yosupo Library Checker の 問題 を通します。 なお、Polynomial Taylor Shift の解法は、単なるライブラリ整備の一環とみなすというよりは、その導出過程をぜひ押さえておきた…
AtCoder
AtCoder600点
ABC-G
黄色diff
期待値
期待値の線形性
テク:総和がNになる整数組の種類数はO(√N)
二項係数
多項式・FPS(形式的冪級数)
多項式:PolynomialTalyorShift
色に関する問題
各kに対して
N個からK個を選ぶ設定の問題
種類数
有理数mod998244353
最初 DP で迷走して、期待値の線形性を使って まで来れた。でも、Polynomial Taylor Shift なる解法もあるらしい！ 問題へのリンク 問題概要 個のキャンディがあって、各キャンディの色は正の整数 で表されている。 各 に対して、 個のキャンディから 個のキ…
