#include "fps/sparse-fps.hpp"
#pragma once #include <utility> #include <vector> using namespace std; #include "formal-power-series.hpp" // g が sparse を仮定, f * g.inv() を計算 template <typename mint> FormalPowerSeries<mint> sparse_div(const FormalPowerSeries<mint>& f, const FormalPowerSeries<mint>& g, int deg = -1) { assert(g.empty() == false && g[0] != mint(0)); if (deg == -1) deg = f.size(); mint ig0 = g[0].inverse(); FormalPowerSeries<mint> s = f * ig0; s.resize(deg); vector<pair<int, mint>> gs; for (int i = 1; i < (int)g.size(); i++) { if (g[i] != 0) gs.emplace_back(i, g[i] * ig0); } for (int i = 0; i < deg; i++) { for (auto& [j, g_j] : gs) { if (i + j >= deg) break; s[i + j] -= s[i] * g_j; } } return s; } template <typename mint> FormalPowerSeries<mint> sparse_inv(const FormalPowerSeries<mint>& f, int deg = -1) { assert(f.empty() == false && f[0] != mint(0)); if (deg == -1) deg = f.size(); vector<pair<int, mint>> fs; for (int i = 1; i < (int)f.size(); i++) { if (f[i] != 0) fs.emplace_back(i, f[i]); } FormalPowerSeries<mint> g(deg); mint if0 = f[0].inverse(); if (0 < deg) g[0] = if0; for (int k = 1; k < deg; k++) { for (auto& [j, fj] : fs) { if (k < j) break; g[k] += g[k - j] * fj; } g[k] *= -if0; } return g; } template <typename mint> FormalPowerSeries<mint> sparse_log(const FormalPowerSeries<mint>& f, int deg = -1) { assert(f.empty() == false && f[0] == 1); if (deg == -1) deg = f.size(); vector<pair<int, mint>> fs; for (int i = 1; i < (int)f.size(); i++) { if (f[i] != 0) fs.emplace_back(i, f[i]); } int mod = mint::get_mod(); static vector<mint> invs{1, 1}; while ((int)invs.size() <= deg) { int i = invs.size(); invs.push_back((-invs[mod % i]) * (mod / i)); } FormalPowerSeries<mint> g(deg); for (int k = 0; k < deg - 1; k++) { for (auto& [j, fj] : fs) { if (k < j) break; int i = k - j; g[k + 1] -= g[i + 1] * fj * (i + 1); } g[k + 1] *= invs[k + 1]; if (k + 1 < (int)f.size()) g[k + 1] += f[k + 1]; } return g; } template <typename mint> FormalPowerSeries<mint> sparse_exp(const FormalPowerSeries<mint>& f, int deg = -1) { assert(f.empty() or f[0] == 0); if (deg == -1) deg = f.size(); vector<pair<int, mint>> fs; for (int i = 1; i < (int)f.size(); i++) { if (f[i] != 0) fs.emplace_back(i, f[i]); } int mod = mint::get_mod(); static vector<mint> invs{1, 1}; while ((int)invs.size() <= deg) { int i = invs.size(); invs.push_back((-invs[mod % i]) * (mod / i)); } FormalPowerSeries<mint> g(deg); if (deg) g[0] = 1; for (int k = 0; k < deg - 1; k++) { for (auto& [ip1, fip1] : fs) { int i = ip1 - 1; if (k < i) break; g[k + 1] += fip1 * g[k - i] * (i + 1); } g[k + 1] *= invs[k + 1]; } return g; } template <typename mint> FormalPowerSeries<mint> sparse_pow(const FormalPowerSeries<mint>& f, long long k, int deg = -1) { if (deg == -1) deg = f.size(); if (k == 0) { FormalPowerSeries<mint> g(deg); if (deg) g[0] = 1; return g; } int zero = 0; while (zero != (int)f.size() and f[zero] == 0) zero++; if (zero == (int)f.size() or __int128_t(zero) * k >= deg) { return FormalPowerSeries<mint>(deg, 0); } if (zero != 0) { FormalPowerSeries<mint> suf{begin(f) + zero, end(f)}; auto g = sparse_pow(suf, k, deg - zero * k); FormalPowerSeries<mint> h(zero * k, 0); copy(begin(g), end(g), back_inserter(h)); return h; } int mod = mint::get_mod(); static vector<mint> invs{1, 1}; while ((int)invs.size() <= deg) { int i = invs.size(); invs.push_back((-invs[mod % i]) * (mod / i)); } vector<pair<int, mint>> fs; for (int i = 1; i < (int)f.size(); i++) { if (f[i] != 0) fs.emplace_back(i, f[i]); } FormalPowerSeries<mint> g(deg); g[0] = f[0].pow(k); mint denom = f[0].inverse(); k %= mint::get_mod(); for (int a = 1; a < deg; a++) { for (auto& [i, f_i] : fs) { if (a < i) break; g[a] += f_i * g[a - i] * ((k + 1) * i - a); } g[a] *= denom * invs[a]; } return g; } /** * @brief sparse な形式的冪級数の演算 */
#line 2 "fps/sparse-fps.hpp" #include <utility> #include <vector> using namespace std; #line 2 "fps/formal-power-series.hpp" template <typename mint> struct FormalPowerSeries : vector<mint> { using vector<mint>::vector; using FPS = FormalPowerSeries; FPS &operator+=(const FPS &r) { if (r.size() > this->size()) this->resize(r.size()); for (int i = 0; i < (int)r.size(); i++) (*this)[i] += r[i]; return *this; } FPS &operator+=(const mint &r) { if (this->empty()) this->resize(1); (*this)[0] += r; return *this; } FPS &operator-=(const FPS &r) { if (r.size() > this->size()) this->resize(r.size()); for (int i = 0; i < (int)r.size(); i++) (*this)[i] -= r[i]; return *this; } FPS &operator-=(const mint &r) { if (this->empty()) this->resize(1); (*this)[0] -= r; return *this; } FPS &operator*=(const mint &v) { for (int k = 0; k < (int)this->size(); k++) (*this)[k] *= v; return *this; } FPS &operator/=(const FPS &r) { if (this->size() < r.size()) { this->clear(); return *this; } int n = this->size() - r.size() + 1; if ((int)r.size() <= 64) { FPS f(*this), g(r); g.shrink(); mint coeff = g.back().inverse(); for (auto &x : g) x *= coeff; int deg = (int)f.size() - (int)g.size() + 1; int gs = g.size(); FPS quo(deg); for (int i = deg - 1; i >= 0; i--) { quo[i] = f[i + gs - 1]; for (int j = 0; j < gs; j++) f[i + j] -= quo[i] * g[j]; } *this = quo * coeff; this->resize(n, mint(0)); return *this; } return *this = ((*this).rev().pre(n) * r.rev().inv(n)).pre(n).rev(); } FPS &operator%=(const FPS &r) { *this -= *this / r * r; shrink(); return *this; } FPS operator+(const FPS &r) const { return FPS(*this) += r; } FPS operator+(const mint &v) const { return FPS(*this) += v; } FPS operator-(const FPS &r) const { return FPS(*this) -= r; } FPS operator-(const mint &v) const { return FPS(*this) -= v; } FPS operator*(const FPS &r) const { return FPS(*this) *= r; } FPS operator*(const mint &v) const { return FPS(*this) *= v; } FPS operator/(const FPS &r) const { return FPS(*this) /= r; } FPS operator%(const FPS &r) const { return FPS(*this) %= r; } FPS operator-() const { FPS ret(this->size()); for (int i = 0; i < (int)this->size(); i++) ret[i] = -(*this)[i]; return ret; } void shrink() { while (this->size() && this->back() == mint(0)) this->pop_back(); } FPS rev() const { FPS ret(*this); reverse(begin(ret), end(ret)); return ret; } FPS dot(FPS r) const { FPS ret(min(this->size(), r.size())); for (int i = 0; i < (int)ret.size(); i++) ret[i] = (*this)[i] * r[i]; return ret; } // 前 sz 項を取ってくる。sz に足りない項は 0 埋めする FPS pre(int sz) const { FPS ret(begin(*this), begin(*this) + min((int)this->size(), sz)); if ((int)ret.size() < sz) ret.resize(sz); return ret; } FPS operator>>(int sz) const { if ((int)this->size() <= sz) return {}; FPS ret(*this); ret.erase(ret.begin(), ret.begin() + sz); return ret; } FPS operator<<(int sz) const { FPS ret(*this); ret.insert(ret.begin(), sz, mint(0)); return ret; } FPS diff() const { const int n = (int)this->size(); FPS ret(max(0, n - 1)); mint one(1), coeff(1); for (int i = 1; i < n; i++) { ret[i - 1] = (*this)[i] * coeff; coeff += one; } return ret; } FPS integral() const { const int n = (int)this->size(); FPS ret(n + 1); ret[0] = mint(0); if (n > 0) ret[1] = mint(1); auto mod = mint::get_mod(); for (int i = 2; i <= n; i++) ret[i] = (-ret[mod % i]) * (mod / i); for (int i = 0; i < n; i++) ret[i + 1] *= (*this)[i]; return ret; } mint eval(mint x) const { mint r = 0, w = 1; for (auto &v : *this) r += w * v, w *= x; return r; } FPS log(int deg = -1) const { assert(!(*this).empty() && (*this)[0] == mint(1)); if (deg == -1) deg = (int)this->size(); return (this->diff() * this->inv(deg)).pre(deg - 1).integral(); } FPS pow(int64_t k, int deg = -1) const { const int n = (int)this->size(); if (deg == -1) deg = n; if (k == 0) { FPS ret(deg); if (deg) ret[0] = 1; return ret; } for (int i = 0; i < n; i++) { if ((*this)[i] != mint(0)) { mint rev = mint(1) / (*this)[i]; FPS ret = (((*this * rev) >> i).log(deg) * k).exp(deg); ret *= (*this)[i].pow(k); ret = (ret << (i * k)).pre(deg); if ((int)ret.size() < deg) ret.resize(deg, mint(0)); return ret; } if (__int128_t(i + 1) * k >= deg) return FPS(deg, mint(0)); } return FPS(deg, mint(0)); } static void *ntt_ptr; static void set_fft(); FPS &operator*=(const FPS &r); void ntt(); void intt(); void ntt_doubling(); static int ntt_pr(); FPS inv(int deg = -1) const; FPS exp(int deg = -1) const; }; template <typename mint> void *FormalPowerSeries<mint>::ntt_ptr = nullptr; /** * @brief 多項式/形式的冪級数ライブラリ * @docs docs/fps/formal-power-series.md */ #line 8 "fps/sparse-fps.hpp" // g が sparse を仮定, f * g.inv() を計算 template <typename mint> FormalPowerSeries<mint> sparse_div(const FormalPowerSeries<mint>& f, const FormalPowerSeries<mint>& g, int deg = -1) { assert(g.empty() == false && g[0] != mint(0)); if (deg == -1) deg = f.size(); mint ig0 = g[0].inverse(); FormalPowerSeries<mint> s = f * ig0; s.resize(deg); vector<pair<int, mint>> gs; for (int i = 1; i < (int)g.size(); i++) { if (g[i] != 0) gs.emplace_back(i, g[i] * ig0); } for (int i = 0; i < deg; i++) { for (auto& [j, g_j] : gs) { if (i + j >= deg) break; s[i + j] -= s[i] * g_j; } } return s; } template <typename mint> FormalPowerSeries<mint> sparse_inv(const FormalPowerSeries<mint>& f, int deg = -1) { assert(f.empty() == false && f[0] != mint(0)); if (deg == -1) deg = f.size(); vector<pair<int, mint>> fs; for (int i = 1; i < (int)f.size(); i++) { if (f[i] != 0) fs.emplace_back(i, f[i]); } FormalPowerSeries<mint> g(deg); mint if0 = f[0].inverse(); if (0 < deg) g[0] = if0; for (int k = 1; k < deg; k++) { for (auto& [j, fj] : fs) { if (k < j) break; g[k] += g[k - j] * fj; } g[k] *= -if0; } return g; } template <typename mint> FormalPowerSeries<mint> sparse_log(const FormalPowerSeries<mint>& f, int deg = -1) { assert(f.empty() == false && f[0] == 1); if (deg == -1) deg = f.size(); vector<pair<int, mint>> fs; for (int i = 1; i < (int)f.size(); i++) { if (f[i] != 0) fs.emplace_back(i, f[i]); } int mod = mint::get_mod(); static vector<mint> invs{1, 1}; while ((int)invs.size() <= deg) { int i = invs.size(); invs.push_back((-invs[mod % i]) * (mod / i)); } FormalPowerSeries<mint> g(deg); for (int k = 0; k < deg - 1; k++) { for (auto& [j, fj] : fs) { if (k < j) break; int i = k - j; g[k + 1] -= g[i + 1] * fj * (i + 1); } g[k + 1] *= invs[k + 1]; if (k + 1 < (int)f.size()) g[k + 1] += f[k + 1]; } return g; } template <typename mint> FormalPowerSeries<mint> sparse_exp(const FormalPowerSeries<mint>& f, int deg = -1) { assert(f.empty() or f[0] == 0); if (deg == -1) deg = f.size(); vector<pair<int, mint>> fs; for (int i = 1; i < (int)f.size(); i++) { if (f[i] != 0) fs.emplace_back(i, f[i]); } int mod = mint::get_mod(); static vector<mint> invs{1, 1}; while ((int)invs.size() <= deg) { int i = invs.size(); invs.push_back((-invs[mod % i]) * (mod / i)); } FormalPowerSeries<mint> g(deg); if (deg) g[0] = 1; for (int k = 0; k < deg - 1; k++) { for (auto& [ip1, fip1] : fs) { int i = ip1 - 1; if (k < i) break; g[k + 1] += fip1 * g[k - i] * (i + 1); } g[k + 1] *= invs[k + 1]; } return g; } template <typename mint> FormalPowerSeries<mint> sparse_pow(const FormalPowerSeries<mint>& f, long long k, int deg = -1) { if (deg == -1) deg = f.size(); if (k == 0) { FormalPowerSeries<mint> g(deg); if (deg) g[0] = 1; return g; } int zero = 0; while (zero != (int)f.size() and f[zero] == 0) zero++; if (zero == (int)f.size() or __int128_t(zero) * k >= deg) { return FormalPowerSeries<mint>(deg, 0); } if (zero != 0) { FormalPowerSeries<mint> suf{begin(f) + zero, end(f)}; auto g = sparse_pow(suf, k, deg - zero * k); FormalPowerSeries<mint> h(zero * k, 0); copy(begin(g), end(g), back_inserter(h)); return h; } int mod = mint::get_mod(); static vector<mint> invs{1, 1}; while ((int)invs.size() <= deg) { int i = invs.size(); invs.push_back((-invs[mod % i]) * (mod / i)); } vector<pair<int, mint>> fs; for (int i = 1; i < (int)f.size(); i++) { if (f[i] != 0) fs.emplace_back(i, f[i]); } FormalPowerSeries<mint> g(deg); g[0] = f[0].pow(k); mint denom = f[0].inverse(); k %= mint::get_mod(); for (int a = 1; a < deg; a++) { for (auto& [i, f_i] : fs) { if (a < i) break; g[a] += f_i * g[a - i] * ((k + 1) * i - a); } g[a] *= denom * invs[a]; } return g; } /** * @brief sparse な形式的冪級数の演算 */