評価点が等差数列で次数よりも多い場合の多点評価

yukicoder で出そうかと思いましたが Python を通すのが難しいうえに大したことないのでここで放流します。

問題

以下の問題を考えます。

問題

多項式 $\displaystyle f(x) = \sum _ {i = 0} ^ {n-1} f_i x ^ i$ と整数 $m, c, d$ が与えられる。各 $k=0,1,\ldots,m - 1$ に対して $f(c + kd) \bmod 998244353$ を求めよ。

本記事では $m \geq n$ の場合を考えます。また、$d \not\equiv 0 \pmod{998244353}$ を仮定します。

多点評価で $\Theta(m (\log m) ^ 2)$ や $\Theta(m (\log n) ^ 2)$ 時間で解けますが、少し工夫をすると $\Theta(n (\log n) ^ 2 + m \log m)$ 時間に落とせます。

ほとんど変わらないように見えますが、$n= 10 ^ 5,\ m = 4\times 10 ^ 6$ みたいな恣意的な状況を考えると価値があるかもしれないです。また、等差数列というと使いどころが無さそうですが、$d=1$ の場合はどこかで使えるかもしれません。

解法

$g(x) \coloneqq f(dx)$ とすると求めたいものは $k=0,1,\ldots,m - 1$ に対する $g(c/d + k)$ です。$g(0),g(1),\ldots,g(n-1)$ を多点評価で計算した後に Shift of sampling points of polynomials をすると $\Theta(n (\log n) ^ 2 + m \log m)$ 時間が達成されます。