解説
O(NlogN)
フェルマーの小定理より、 i=1,2,3,… それぞれに対して 998244353−2 乗することで i−1 mod 998244353 を求めることができます。
O(N)
参考: https://drken1215.hatenablog.com/entry/2018/06/08/210000
mod p における 1 から N までの逆元を O(N) で求めることができます。
p(p mod i)i−1≡i⌊ip⌋+(p mod i)≡−i⌊ip⌋≡−(p mod i)−1⌊ip⌋
(i mod p)−1 から i−1 が計算でき、 i mod p は i よりも小さいため、 1−1≡1 として i=2 から順番に計算することで全体で O(N) で求めることができました。