以下，\(e\) を自然対数の底，\(i\) を虚数単位とします．

\(\cos x = \displaystyle\frac{e^{ix}+e^{-ix}}{2}\) であることを用いると，\(f(x) = \displaystyle\sum_{k=-(N-1)}^{N-1} B_k e^{ikx}\) となります．ここで，\(B_k = \begin{cases} \displaystyle\frac{1}{2}A_{|k|} & (k \neq 0) \\ A_0 & (k = 0) \end{cases}\) です．よって，\((B_{-N+1}, B_{-N+2}, \dots, B_{N-1})\) を特定できればよいです．

\(g(y) := \displaystyle\sum_{k=-(N-1)}^{N-1} B_k y^k\) とおくと，\(f(x) = g(e^{ix})\) となります．ここで，複素数 \(z\) を以下の条件を満たすように取ります．

• \(|z|=1\)．
• \(z\) の実部と虚部は有理数で，既約分数で表したとき分母が \(998244353\) の倍数でない．
• \(z\) の実部・虚部を \({} \bmod 998244353\) で表したものをそれぞれ \(a, b\) とし，\(z' := a+b\sqrt{-1} \bmod 998244353\) とおくと，\(z', z'^2, \dots, z'^{N-1} \not\equiv 1 \pmod {998244353}\)．ここれ \(\sqrt{-1}\) は \(998244353\) を法とする \(-1\) の平方根である．

\(g(1), g(z), \dots, g(z^{N-1})\) すなわち \(f(0), f(\arg z), \dots, f((N-1)\arg z)\) を質問します．ここで，\(z\) に対する条件から \(\arccos(0), \arccos(\arg z), \dots, \arccos ((N-1)\arg z)\) はすべて有理数で，既約分数で表したときの分母が \(998244353\) の倍数ではありません．これらの値は \(\arccos (k\arg z) \equiv \displaystyle\frac{z'^k + z'^{-k}}{2} \pmod {998244353}\) を用いて求めることができます．

\(B_{-k} = B_k\) であることから，任意の複素数 \(w\) に対し \(g(\overline{w}) = g(w)\) が成り立ちます．さらに \(|z^k| = 1\) であることから，\(g(z^{-k}) = g(\overline{z^k}) = g(z^k)\) となるので，\(g(z^{-N+1}), g(z^{-N+1}), \dots, g(z^{N-1})\) がわかったことになります．

等比数列の評価点に対する多項式補間を行うことで，\((B_{-N+1}, B_{-N+2}, \dots, B_{N-1})\) を \(O(N \log N)\) 時間で求めることができます．