using Poly = vector; // 末尾の 0 を除去する void normalize(Poly& f) { while (f.size() > 1 && f.back() == mint(0)) { f.pop_back(); } if (f.empty()) f.push_back(0); } // 多項式の積 Poly multiply(const Poly& a, const Poly& b) { return atcoder::convolution(a, b); } // 形式的冪級数の逆元 // f[0] != 0 を仮定 // f * g = 1 (mod x^n) となる g を返す Poly fps_inv(const Poly& f, int n) { if (n == 0) return {}; assert(!f.empty() && f[0] != mint(0)); Poly g = {f[0].inv()}; for (int k = 1; k < n; k *= 2) { int m = min(2 * k, n); Poly a(min((int)f.size(), m)); for (int i = 0; i < (int)a.size(); i++) { a[i] = f[i]; } // g <- g * (2 - f*g) mod x^m Poly t = multiply(a, g); t.resize(m); for (auto& x : t) x = -x; t[0] += 2; g = multiply(g, t); g.resize(m); } return g; } // 多項式の剰余 a mod b // b != 0 を仮定 Poly poly_mod(Poly a, Poly b) { normalize(a); normalize(b); assert(!(b.size() == 1 && b[0] == mint(0))); int n = (int)a.size(); int m = (int)b.size(); if (n < m) return a; if (m == 1) return {0}; int k = n - m + 1; // 商 q = a / b を反転多項式から求める Poly ra(a.rbegin(), a.rend()); Poly rb(b.rbegin(), b.rend()); ra.resize(k); Poly ib = fps_inv(rb, k); Poly rq = multiply(ra, ib); rq.resize(k); Poly q(rq.rbegin(), rq.rend()); // 余り r = a - b*q Poly bq = multiply(b, q); Poly r(m - 1, mint(0)); for (int i = 0; i < m - 1; i++) { r[i] = a[i] - bq[i]; } normalize(r); return r; } // 多点評価 // f[i] は x^i の係数 // 戻り値 res[i] = f(xs[i]) vector multipoint_evaluation( const vector& f, const vector& xs ) { int m = (int)xs.size(); if (m == 0) return {}; int sz = 1; while (sz < m) sz *= 2; // 積木 // tree[v] = 対応する (x - xs[i]) の積 vector tree(2 * sz); for (int i = 0; i < sz; i++) { if (i < m) { tree[sz + i] = {-xs[i], mint(1)}; } else { tree[sz + i] = {mint(1)}; } } for (int i = sz - 1; i >= 1; i--) { tree[i] = multiply( tree[2 * i], tree[2 * i + 1] ); } // 各ノードにおける f の剰余 vector rem(2 * sz); if (f.empty()) { rem[1] = {0}; } else { rem[1] = poly_mod(f, tree[1]); } for (int i = 1; i < sz; i++) { rem[2 * i] = poly_mod( rem[i], tree[2 * i] ); rem[2 * i + 1] = poly_mod( rem[i], tree[2 * i + 1] ); } vector res(m); for (int i = 0; i < m; i++) { res[i] = rem[sz + i][0]; } return res; }