乱択を用いない解法です。 問題文 judge.yosupo.jp \( \mathbb{F}_{998244353} \)上の次数 \( N \)の多項式 \( f(x) \) が与えられるので、\( f(a) = 0 \) となる\(a \in \mathbb{F}_{998244353}\)を列挙してください。 制約: \( 1 \leq N \leq 4000 \) 解説…

Alien DPの自分なりの理解をメモ。 アルゴリズムの説明 を広義で上に凸であることがわかっている未知の数列とする。 与えられたに対してを求めることを目指す。 とおくと、が広義で上に凸であることからは広義単調減少である。 この時関数を、 で定義すると…