多項式行列の prefix product
(matrix/polynomial-matrix-prefix-product.hpp)
Depends on
Required by
Verified with
Code
#pragma once
#include "fps/formal-power-series.hpp"
#include "fps/sampling-points-shift.hpp"
#include "matrix/matrix.hpp"
// a(k-1) a(k-2) ... a(0)
template <class mint>
Matrix<mint> PolynomialMatrixPrefixProduct(const Matrix<FormalPowerSeries<mint>>& a, long long k) {
using mat = Matrix<mint>;
assert(k >= 0 && a.h == a.w);
int n = a.h, deg = 1;
for (const auto& f : a.a) deg = max(deg, (int)f.size() - 1);
while (deg & (deg - 1)) deg++;
auto shift = [&](const vector<mat>& g, mint x) {
int d = g.size();
vector<mat> h(d, mat(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
vector<mint> y(d);
for (int l = 0; l < d; l++) y[l] = g[l].get(i, j);
auto z = SamplingPointsShift(y, x, d);
for (int l = 0; l < d; l++) h[l].set(i, j, z[l]);
}
}
return h;
};
long long v = 1;
while ((__int128)deg * v * v < k) v *= 2;
vector<mat> g(deg + 1, mat(n));
for (int i = 0; i <= deg; i++) {
mint x = mint(v) * i;
for (int j = 0; j < n; j++)
for (int l = 0; l < n; l++) g[i].set(j, l, a.get(j, l).eval(x));
}
mint iv = mint(v).inv();
for (long long w = 1; w < v; w *= 2) {
auto g1 = shift(g, mint(w) * iv);
auto g2 = shift(g, mint(w * deg * v + v) * iv);
auto g3 = shift(g, mint(w * deg * v + v + w) * iv);
for (int i = 0; i <= w * deg; i++) {
g[i] = g1[i] * g[i];
g2[i] = g3[i] * g2[i];
}
g.insert(g.end(), g2.begin(), g2.end() - 1);
}
mat ret = mat::id(n);
long long i = 0;
while (i + v <= k) {
ret = g[i / v] * ret;
i += v;
}
while (i < k) {
mat m(n);
for (int j = 0; j < n; j++)
for (int l = 0; l < n; l++) m.set(j, l, a.get(j, l).eval(mint(i)));
ret = m * ret;
i++;
}
return ret;
}
/**
* @brief 多項式行列の prefix product
*/
#line 2 "fps/formal-power-series.hpp"
template <class mint>
struct FormalPowerSeries : vector<mint> {
using vector<mint>::vector;
using FPS = FormalPowerSeries;
FormalPowerSeries(const vector<mint>& r) : vector<mint>(r) {}
FormalPowerSeries(vector<mint>&& r) : vector<mint>(std::move(r)) {}
FPS& operator=(const vector<mint>& r) {
vector<mint>::operator=(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 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.at(g.size() - 1).inv();
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;
}
FPS pre(int sz) const {
return FPS(begin(*this), begin(*this) + min((int)this->size(), sz));
}
FPS operator>>=(int sz) {
assert(sz >= 0);
if ((int)this->size() <= sz)
this->clear();
else
this->erase(this->begin(), this->begin() + sz);
return *this;
}
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) {
assert(sz >= 0);
this->insert(this->begin(), sz, mint(0));
return *this;
}
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)[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_ntt();
FPS& operator*=(const FPS& r);
FPS middle_product(const FPS& r) const;
void ntt();
void intt();
void ntt_doubling();
static int ntt_root();
FPS inv(int deg = -1) const;
FPS exp(int deg = -1) const;
};
template <typename mint>
void* FormalPowerSeries<mint>::ntt_ptr = nullptr;
#line 2 "modint/factorial.hpp"
template <class mint>
struct Factorial {
static void reserve(int n) {
inv(n);
fact(n);
fact_inv(n);
}
static mint inv(int n) {
static long long mod = mint::get_mod();
static vector<mint> buf({0, 1});
assert(n != 0);
if (mod != mint::get_mod()) {
mod = mint::get_mod();
buf = vector<mint>({0, 1});
}
while ((int)buf.capacity() <= n) buf.reserve(buf.capacity() * 2);
while ((int)buf.size() <= n) {
long long k = buf.size(), q = (mod + k - 1) / k;
buf.push_back(q * buf[k * q - mod]);
}
return buf[n];
}
static mint fact(int n) {
static long long mod = mint::get_mod();
static vector<mint> buf({1, 1});
assert(n >= 0);
if (mod != mint::get_mod()) {
mod = mint::get_mod();
buf = vector<mint>({1, 1});
}
while ((int)buf.capacity() <= n) buf.reserve(buf.capacity() * 2);
while ((int)buf.size() <= n) {
long long k = buf.size();
buf.push_back(buf.back() * k);
}
return buf[n];
}
static mint fact_inv(int n) {
static long long mod = mint::get_mod();
static vector<mint> buf({1, 1});
assert(n >= 0);
if (mod != mint::get_mod()) {
mod = mint::get_mod();
buf = vector<mint>({1, 1});
}
if ((int)buf.size() <= n) inv(n);
while ((int)buf.capacity() <= n) buf.reserve(buf.capacity() * 2);
while ((int)buf.size() <= n) {
long long k = buf.size();
buf.push_back(buf.back() * inv(k));
}
return buf[n];
}
static mint binom(int n, int r) {
if (r < 0 || r > n) return 0;
return fact(n) * fact_inv(r) * fact_inv(n - r);
}
static mint binom_naive(int n, int r) {
if (r < 0 || r > n) return 0;
mint res = fact_inv(r);
for (int i = 0; i < r; i++) res *= n - i;
return res;
}
static mint multinom(const vector<int>& r) {
int n = 0;
for (auto& x : r) {
if (x < 0) return 0;
n += x;
}
mint res = fact(n);
for (auto& x : r) res *= fact_inv(x);
return res;
}
static mint P(int n, int r) {
if (r < 0 || r > n) return 0;
return fact(n) * fact_inv(n - r);
}
// partition n items to r groups (allow empty group)
static mint H(int n, int r) {
if (n < 0 || r < 0) return 0;
return r == 0 ? 1 : binom(n + r - 1, r);
}
};
/**
* @brief 階乗, 二項係数
*/
#line 4 "fps/sampling-points-shift.hpp"
// f(0),f(1),...,f(n-1) -> f(c),...,f(c+m-1)
template <class mint>
vector<mint> SamplingPointsShift(const vector<mint>& f, mint c, int m) {
using fps = FormalPowerSeries<mint>;
using fact = Factorial<mint>;
int n = f.size();
fact::reserve(m);
fps f1(n), ei(n);
for (int i = 0; i < n; i++) f1[i] = f[i] * fact::fact_inv(i);
for (int i = 0; i < n; i++) ei[i] = fact::fact_inv(i) * (i % 2 ? -1 : 1);
f1 *= ei;
for (int i = n; i < f1.size(); i++) f1[i] = 0;
for (int i = 0; i < n; i++) f1[i] *= fact::fact(i);
fps g(n, 1);
for (int i = 1; i < n; i++) g[i] = g[i - 1] * (c + 1 - i) * fact::inv(i);
g = g.middle_product(f1);
for (int i = 0; i < n; i++) g[i] *= fact::fact_inv(i);
fps e(m);
for (int i = 0; i < m; i++) e[i] = fact::fact_inv(i);
g *= e;
g.resize(m);
for (int i = 0; i < m; i++) g[i] *= fact::fact(i);
return g;
}
/**
* @brief 評価点シフト
* @docs docs/fps/sampling-points-shift.md
*/
#line 2 "matrix/matrix.hpp"
template <class T>
struct Matrix {
int h, w;
vector<T> a;
Matrix() {}
Matrix(int n) : h(n), w(n), a(n * n, T{}) {}
Matrix(int h_, int w_) : h(h_), w(w_), a(h * w, T{}) {}
inline T get(int i, int j) const { return a[w * i + j]; }
inline void set(int i, int j, T v) { a[w * i + j] = v; }
inline void add(int i, int j, T v) { a[w * i + j] += v; }
inline void sub(int i, int j, T v) { a[w * i + j] -= v; }
static Matrix id(int n) {
Matrix mat(n);
for (int i = 0; i < n; i++) mat.a[n * i + i] = T(1);
return mat;
}
Matrix operator+=(const Matrix& r) {
assert(h == r.h && w == r.w);
for (int i = 0; i < h * w; i++) a[i] += r.a[i];
return *this;
}
Matrix operator-=(const Matrix& r) {
assert(h == r.h && w == r.w);
for (int i = 0; i < h * w; i++) a[i] -= r.a[i];
return *this;
}
Matrix operator+(const Matrix& r) { return Matrix(*this) += r; }
Matrix operator-(const Matrix& r) { return Matrix(*this) -= r; }
Matrix operator*(const Matrix& r) {
assert(w == r.h);
Matrix ret(h, r.w);
for (int i = 0; i < h; i++)
for (int j = 0; j < r.w; j++)
for (int k = 0; k < w; k++)
ret.add(i, j, get(i, k) * r.get(k, j));
return ret;
}
Matrix& operator*=(const Matrix& r) { return *this = *this * r; }
Matrix& operator*=(T r) {
for (auto& v : a) v *= r;
return *this;
}
Matrix operator*(T r) { return Matrix(*this) *= r; }
Matrix pow(long long n) const {
Matrix ret = id(h);
Matrix mat(*this);
while (n > 0) {
if (n & 1) ret = ret * mat;
mat = mat * mat;
n >>= 1;
}
return ret;
}
T det() const {
assert(h == w);
Matrix mat(*this);
T zero{}, det(1);
for (int k = 0; k < h; k++) {
{
int i = k;
while (i < h && mat.get(i, k) == zero) i++;
if (i == h) return zero;
if (i != k) {
mat.swap_row(i, k);
det = -det;
}
}
for (int i = k + 1; i < h; i++)
mat.mul_add_row(i, k, -mat.get(i, k) / mat.get(k, k));
det *= mat.a[h * k + k];
}
return det;
}
optional<Matrix> inv() const {
assert(h == w);
Matrix mat(*this);
Matrix imat = id(h);
T zero{};
for (int k = 0; k < h; k++) {
{
int i = k;
while (i < h && mat.get(i, k) == zero) i++;
if (i == h) return nullopt;
if (i != k) {
mat.swap_row(i, k);
imat.swap_row(i, k);
}
}
{
T v = T(1) / mat.get(k, k);
mat.mul_row(k, v);
imat.mul_row(k, v);
}
for (int i = 0; i < h; i++) {
if (i == k) continue;
T v = -mat.get(i, k);
mat.mul_add_row(i, k, v);
imat.mul_add_row(i, k, v);
}
}
return imat;
}
void swap_row(int i, int j) {
for (int k = 0; k < w; k++) swap(a[w * i + k], a[w * j + k]);
}
void mul_row(int i, T v) {
for (int k = 0; k < w; k++) a[w * i + k] *= v;
}
// row i += row j * v
void mul_add_row(int i, int j, T v) {
for (int k = 0; k < w; k++) a[w * i + k] += a[w * j + k] * v;
}
friend ostream& operator<<(ostream& os, const Matrix& mat) {
for (int i = 0; i < mat.h; i++) {
for (int j = 0; j < mat.w; j++) {
os << mat.get(i, j);
if (j + 1 < mat.w) os << " ";
}
if (i + 1 < mat.h) os << "\n";
}
return os;
}
};
#line 5 "matrix/polynomial-matrix-prefix-product.hpp"
// a(k-1) a(k-2) ... a(0)
template <class mint>
Matrix<mint> PolynomialMatrixPrefixProduct(const Matrix<FormalPowerSeries<mint>>& a, long long k) {
using mat = Matrix<mint>;
assert(k >= 0 && a.h == a.w);
int n = a.h, deg = 1;
for (const auto& f : a.a) deg = max(deg, (int)f.size() - 1);
while (deg & (deg - 1)) deg++;
auto shift = [&](const vector<mat>& g, mint x) {
int d = g.size();
vector<mat> h(d, mat(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
vector<mint> y(d);
for (int l = 0; l < d; l++) y[l] = g[l].get(i, j);
auto z = SamplingPointsShift(y, x, d);
for (int l = 0; l < d; l++) h[l].set(i, j, z[l]);
}
}
return h;
};
long long v = 1;
while ((__int128)deg * v * v < k) v *= 2;
vector<mat> g(deg + 1, mat(n));
for (int i = 0; i <= deg; i++) {
mint x = mint(v) * i;
for (int j = 0; j < n; j++)
for (int l = 0; l < n; l++) g[i].set(j, l, a.get(j, l).eval(x));
}
mint iv = mint(v).inv();
for (long long w = 1; w < v; w *= 2) {
auto g1 = shift(g, mint(w) * iv);
auto g2 = shift(g, mint(w * deg * v + v) * iv);
auto g3 = shift(g, mint(w * deg * v + v + w) * iv);
for (int i = 0; i <= w * deg; i++) {
g[i] = g1[i] * g[i];
g2[i] = g3[i] * g2[i];
}
g.insert(g.end(), g2.begin(), g2.end() - 1);
}
mat ret = mat::id(n);
long long i = 0;
while (i + v <= k) {
ret = g[i / v] * ret;
i += v;
}
while (i < k) {
mat m(n);
for (int j = 0; j < n; j++)
for (int l = 0; l < n; l++) m.set(j, l, a.get(j, l).eval(mint(i)));
ret = m * ret;
i++;
}
return ret;
}
/**
* @brief 多項式行列の prefix product
*/
Back to top page