using Poly = vector; // 末尾の 0 を除去 void normalize2(Poly& a) { while (!a.empty() && a.back() == 0) a.pop_back(); } // 多項式の加算 Poly poly_add(const Poly& a, const Poly& b) { Poly c(max(a.size(), b.size())); for (int i = 0; i < (int)a.size(); i++) c[i] += a[i]; for (int i = 0; i < (int)b.size(); i++) c[i] += b[i]; normalize(c); return c; } // 多項式の乗算 Poly poly_mul(const Poly& a, const Poly& b) { if (a.empty() || b.empty()) return {}; return convolution(a, b); } // f(x)^(-1) mod x^n // f[0] != 0 を仮定 Poly poly_inv(const Poly& f, int n) { if (n == 0) return {}; Poly g = {f[0].inv()}; while ((int)g.size() < n) { int m = min(n, (int)g.size() * 2); Poly t(min((int)f.size(), m)); for (int i = 0; i < (int)t.size(); i++) { t[i] = f[i]; } t = poly_mul(t, g); t.resize(m); for (auto& x : t) x = -x; t[0] += 2; g = poly_mul(g, t); g.resize(m); } return g; } // a(x) mod b(x) // b != 0 を仮定 Poly poly_mod2(Poly a, const Poly& b) { normalize(a); if (a.size() < b.size()) return a; if (b.size() == 1) return {}; int k = (int)a.size() - (int)b.size() + 1; Poly ra = a, rb = b; reverse(ra.begin(), ra.end()); reverse(rb.begin(), rb.end()); ra.resize(k); Poly inv_rb = poly_inv(rb, k); Poly q = poly_mul(ra, inv_rb); q.resize(k); reverse(q.begin(), q.end()); Poly t = poly_mul(q, b); for (int i = 0; i < (int)t.size(); i++) { a[i] -= t[i]; } a.resize(b.size() - 1); normalize2(a); return a; } // 多項式の微分 Poly poly_derivative(const Poly& f) { if (f.size() <= 1) return {}; Poly g(f.size() - 1); for (int i = 1; i < (int)f.size(); i++) { g[i - 1] = f[i] * i; } return g; } struct SubproductTree { int n, sz; vector prod; SubproductTree(const vector& xs) { n = xs.size(); sz = 1; while (sz < n) sz <<= 1; prod.resize(sz * 2); for (int i = 0; i < sz; i++) { if (i < n) { prod[sz + i] = {-xs[i], 1}; } else { prod[sz + i] = {1}; } } for (int i = sz - 1; i >= 1; i--) { prod[i] = poly_mul(prod[i * 2], prod[i * 2 + 1]); } } // f(x_i) をすべて計算 vector evaluate(const Poly& f) const { vector res(n); if (n == 0) return res; auto dfs = [&](auto&& self, int v, const Poly& r) -> void { if (v >= sz) { int i = v - sz; if (i < n) { res[i] = r.empty() ? mint(0) : r[0]; } return; } Poly l = poly_mod2(r, prod[v * 2]); Poly rr = poly_mod2(r, prod[v * 2 + 1]); self(self, v * 2, l); self(self, v * 2 + 1, rr); }; dfs(dfs, 1, poly_mod2(f, prod[1])); return res; } // w_i から補間多項式を構成 // Σ w_i * prod[1](x) / (x - x_i) Poly build(const vector& w) const { if (n == 0) return {}; auto dfs = [&](auto&& self, int v) -> Poly { if (v >= sz) { int i = v - sz; return i < n ? Poly{w[i]} : Poly{}; } Poly l = self(self, v * 2); Poly r = self(self, v * 2 + 1); Poly a = poly_mul(l, prod[v * 2 + 1]); Poly b = poly_mul(r, prod[v * 2]); return poly_add(a, b); }; return dfs(dfs, 1); } }; // 多項式補間 // 入力: (x_i, y_i) の配列 // 出力: f(x) の係数 (定数項から昇順) // x_i は互いに相異なると仮定 vector polynomial_interpolation( const vector>& points ) { int n = points.size(); if (n == 0) return {}; vector xs(n), ys(n); for (int i = 0; i < n; i++) { xs[i] = points[i].first; ys[i] = points[i].second; } SubproductTree tree(xs); // P(x) = Π (x - x_i) const Poly& P = tree.prod[1]; // P'(x_i) を計算 Poly dP = poly_derivative(P); vector den = tree.evaluate(dP); // w_i = y_i / P'(x_i) vector w(n); for (int i = 0; i < n; i++) { assert(den[i] != 0); w[i] = ys[i] / den[i]; } // f(x) = Σ w_i * P(x) / (x - x_i) Poly f = tree.build(w); f.resize(n); return f; }