解説

O(NlogN)O(N \log N)

フェルマーの小定理より、 i=1,2,3,i = 1, 2, 3, \ldots それぞれに対して 9982443532998244353 - 2 乗することで i1 mod 998244353i^{-1} \text{ mod }998244353 を求めることができます。

O(N)O(N)

参考: https://drken1215.hatenablog.com/entry/2018/06/08/210000

mod p\text{mod } p における 11 から NN までの逆元を O(N)O(N) で求めることができます。

pipi+(p mod i)(p mod i)ipii1(p mod i)1pi\begin{aligned} p &\equiv i \left\lfloor\frac{p}{i}\right\rfloor + (p\text{ mod }i) \\ (p\text{ mod }i) &\equiv -i \left\lfloor\frac{p}{i}\right\rfloor \\ i^{-1} &\equiv - (p\text{ mod }i)^{-1} \left\lfloor\frac{p}{i}\right\rfloor \end{aligned}

(i mod p)1(i\text{ mod }p)^{-1} から i1i^{-1} が計算でき、 i mod pi\text{ mod }pii よりも小さいため、 1111^{-1} \equiv 1 として i=2i = 2 から順番に計算することで全体で O(N)O(N) で求めることができました。