乱択を用いない解法です。
問題文
\( \mathbb{F}_{998244353} \)上の次数 \( N \)の多項式 \( f(x) \) が与えられるので、\( f(a) = 0 \) となる\(a \in \mathbb{F}_{998244353}\)を列挙してください。
制約: \( 1 \leq N \leq 4000 \)
解説
以下、特に注釈がなければ数式は\(\mathbb{F}_{998244353}\)上のものとします。
また、
\( p = 998244353 \)、
\( d \) は \( 8 \leq d \leq 23 \) を満たす整数、
\( r \) は \(\mathbb{F}_p\) における原始根とします。
-
\( a=0 \) は別途チェックすることにして、以下\( a \neq 0 \)とします。
\( f_0(x) := f(x) \)
\( i \geq 0 \) に対し \( f_{i+1}(x) \)は\( f_{i+1}(x^2) = f_i(x)f_i(-x) \) を満たす多項式とすると、
\( f_{i+1}(a^2) = 0 \)
\( \Leftrightarrow f_i(a) = 0 または f_i(-a) = 0 \)
が成り立つので、\( f_{i+1}(x) = 0\) の解が列挙できれば \( f_i(x) = 0 \) の解も列挙できそうです。
ここで \( 1 \leq i \leq d \)に対し\( \{ t^{2^i} | t \in \mathbb{F}_{998244353}, t \neq 0 \} = \{ 1, r^{2^i}, (r^{2^i})^2,..., (r^{2^i})^{(p-1)/2^i-1} \} \) であることを考えると、
\( f_i(x) = 0\) の解として考慮する必要があるのは高々\( \frac{p-1}{2^i} \)個になります。
特に\( i=d \) の時\( \frac{p-1}{2^d} \)個となり、\(d\)を十分大きくとれば多点評価のアルゴリズムが使えます。(等比数列上の多点評価になります)
\( f_d(x) = 0 \) の解が\( \{ r^{2^dt_0}, r^{2^dt_1}, ... \}\)と得られた時、
\( f_{d-1}(x) = 0 \) の解の候補は\( \{ (r^{2^{d-1}})^{t_0}, -(r^{2^{d-1}})^{t_0}=r^{2^{d-1}t_0+(p-1)/2}, (r^{2^d})^{t_1}, -(r^{2^{d-1}})^{t_1}=r^{2^{d-1}t_1+(p-1)/2}... \}\)
を考えればよいので、これらに対し\(f_{d-1}\)を多点評価して0にならないものを除去し、以下\( i=d-2, d-3, ..., 1, 0 \) と計算していけばよいです。(こっちは通常の多点評価になります)
\( f_i \)の次数はすべて\(N\)なので解は常に\(N\)個以下であり、考慮する解の候補の数は常に \( 2N \)で抑えられます。
計算量は、
- \(f_1,...,f_d\)を計算するのに\(\mathit{O}(dN\log N)\)
- \( f_d(x) \) 上の多点評価が \(\mathit{O}( (N+ \frac{p-1}{2^d} ) \log (N+\frac{p-1}{2^d} ) ) \)
- \( f_i(x) \) ( \( 0 \leq i \leq d-1 \)) 上の多点評価が \(\mathit{O}( dN \log ^2N ) \)
であり、全体で \(\mathit{O}( (N+ \frac{p-1}{2^d} ) \log (N+\frac{p-1}{2^d} ) + dN \log ^2N) \)となります。
私の提出では\( d=12 \)としています。(3番目の多点評価が重いのでなるべくこっちの回数を減らしたほうが良さそうです)
提出
https://judge.yosupo.jp/submission/274540 (ACLのconvolution使用、329ms)
現在のFastestは217 msで、更新を狙ってみたのですが、断念しました。
高速な自前convolutionを用意するか多点評価まわりの定数倍改善をするといけそうな気がします。
追記(2025/3/24)
\( f_{i+1}(x^2) = f_i(x)f_i(-x) \) の部分はBostan-Moriのアルゴリズム(https://qiita.com/ryuhe1/items/da5acbcce4ac1911f47a)に出てくるものでそこから思いついた解法なのですが、改めてリンク先の記事を読むと、\( \mathbb{R} \)上の多項式に対し同様の変形をして解を求めるGraeffe法(https://en.wikipedia.org/wiki/Graeffe%27s_method)というアルゴリズムが紹介されていました。
Graeffe法では解を2乗、4乗、...としていくことで解同士を「分離」し、近似解を求めていますが、この記事で説明したように、\(\mathbb{F}_p\) 上の多項式で同様の操作を行うと、解自体の候補が1/2倍、1/4倍、...とどんどん絞られていくことになります。(p-1が2で割れる回数だけ繰り返せます)
というわけで、先行研究の調査不足で車輪の再発明をしてしまっていたようです。一応(競プロ的手法に特化した)後半部分はオリジナリティがあると思っているのですが、ちゃんと調べられていないので、論文など情報を知っている方は教えていただけると助かります。
