FPS inv_sparse(const vector<pair<int,mint>>& f, int deg)
FPS inv_sparse(const FPS& f, int deg)
ここで、畳み込みの定義と逆元の定義から、
$g[i+1]f[0] + g[i] f[1] + \dots + g[1] f[i] + g[0] f[i+1] = 0$。変形して
$g[i+1] = - \frac{g[1] f[1] + \dots + g[1] f[i] + g[0] f[i+1] }{f[0]} $ ここで、$f$はスパースだから、非ゼロな項は$K$個以下。よって$g[i+1]$を$O(K)$で求められる。これを$O(N)$回繰り返すから、全体で$O(NK)$で求められる。