FPS as Linear Operator
(fps_as_operator.hpp)

View this file on GitHub
Last update: 2025-01-19 15:28:01+08:00
Include: #include "fps_as_operator.hpp"

FPS as Linear Operator

Let $F(t) := \sum _ {j \geq 0}\frac{f _ j}{j!}t^j$ where $t = \frac{\mathrm{d}}{\mathrm{d}x}$, we want to apply $F(t)$ to $p(x) = \sum _ {j = 0}^{n - 1} p _ j x^j$. We have

\[\begin{aligned} F(t)p(x) &= (F(t) \bmod{t^n})p(x) \\ &= \sum _ {j = 0}^{n - 1} \frac{f _ j}{j!} p^{(j)}(x) \\ &= \sum _ {j = 0}^{n - 1}\left(\frac{f _ j}{j!}\sum _ {k = j}^{n - 1}p _ k k!\frac{x^{k - j}}{(k - j)!}\right) \\ &= \sum _ {j = 0}^{n - 1}\left(\frac{f _ j}{j!}\sum _ {k = 0}^{n - 1 - j}p _ {k + j} (k + j)!\frac{x^{k}}{k!}\right) \end{aligned}\]

\[\begin{aligned} \left\lbrack x^i\right\rbrack F(t)p(x) &= \sum _ {j = 0}^{n - 1}\left(\frac{f _ j}{j!} \left\lbrack x^i\right\rbrack \left(\sum _ {k = 0}^{n - 1 - j}p _ {k + j} (k + j)!\frac{x^{k}}{k!}\right)\right) \\ &= \sum _ {j = 0}^{n - 1 - i}\frac{f _ j}{j!} p _ {i + j}(i + j)!\frac{1}{i!} \\ &= \sum _ {j = 0}^{n - 1 - i}\binom{i + j}{i} f _ j p _ {i + j} \end{aligned}\]

for $i = 0, 1, \dots, n - 1$. We could construct $\hat p(x) := \sum _ {j = 0}^{n - 1}p _ {n - 1 - j}(n - 1 - j)!x^j$, we have

\[\begin{aligned} \left\lbrack x^{n - 1 - i}\right\rbrack F(x)\hat p(x) &= \sum _ {j = 0}^{n - 1 - i}\left(\left\lbrack x^j\right\rbrack F(x)\right) \left(\left\lbrack x^{n - 1 - i - j}\right\rbrack \hat p(x)\right) \\ &= \sum _ {j = 0}^{n - 1 - i}\frac{f _ j}{j!}p _ {i + j}(i + j)! \\ &= i! \sum _ {j = 0}^{n - 1 - i}\binom{i + j}{i} f _ j p _ {i + j} \end{aligned}\]

as desired.

Linear Operators

The operator $\mathrm{e}^{at}$ satisfies

\[\mathrm{e}^{at}p(x) = p(x + a)\]

is a translation operator.

The forward difference operator is the delta operator $\mathrm{e}^{at} - 1$, where

\[(\mathrm{e}^{at} - 1) p(x) = p(x + a) - p(x)\]

The classical difference operator $\Delta = \mathrm{e}^{t} - 1$.

The Abel operator is the delta operator $t\mathrm{e}^{at}$, where

\[t\mathrm{e}^{at} p(x) = p'(x + a)\]

One can check Advanced Linear Algebra by Steven Roman for more details.

Additionally, we have

\[\mathrm{e}^{x^2t}p(x) = p\left(\frac{x}{1 - x}\right)\]

to see this, we need the definition

\[\mathrm{e}^{x^2 t} x = x + x^2 tx + \frac{1}{2}x^2tx^2tx + \cdots\]

where $x^2 tx = x^2 \frac{\mathrm{d}}{\mathrm{d}x}x = x^2$ and $x^2tx^2tx = x^2tx^2=2x^3$, so

\[\mathrm{e}^{x^2 t} x = x + x^2 + x^3 + \cdots = \frac{x}{1 - x}\]

References

李⽩天. 信息学竞赛中的生成函数计算理论框架. 2021 年信息学奥林匹克中国国家集训队论文. url: https://github.com/OI-wiki/libs/tree/master/%E9%9B%86%E8%AE%AD%E9%98%9F%E5%8E%86%E5%B9%B4%E8%AE%BA%E6%96%87
Steven Roman. Advanced Linear Algebra (Graduate Texts in Mathematics). url: https://link.springer.com/book/10.1007/978-0-387-72831-5
飞雨烟雁. 论线性算法的关系：分式分解、基变换与偏序集. url: https://www.luogu.com/article/ft2eejw9
StackExchange. Formal Power Series as Linear Operators. url: https://math.stackexchange.com/questions/1958491/formal-power-series-as-linear-operators

Depends on

Verified with

test/formal_power_series/polynomial_taylor_shift.1.test.cpp

Code

#pragma once

#include "binomial.hpp"
#include "fft.hpp"
#include <algorithm>
#include <vector>

// apply FPS as linear operator
// F(t): FPS in t where t = d/dx
// p(x): polynomial in x
template<typename Tp> inline std::vector<Tp> apply_egf(std::vector<Tp> F, std::vector<Tp> p) {
    // kinda transposed algorithm of binomial convolution.
    const int n = p.size();
    auto &&bin  = Binomial<Tp>::get(n);
    F.resize(n);
    for (int i = 0; i < n; ++i) {
        F[i] *= bin.inv_factorial(i);
        p[i] *= bin.factorial(i);
    }
    std::reverse(p.begin(), p.end());
    auto res = convolution(F, p);
    res.resize(n);
    std::reverse(res.begin(), res.end());
    for (int i = 0; i < n; ++i) res[i] *= bin.inv_factorial(i);
    return res;
}

template<typename Tp>
inline std::vector<Tp> apply_fps(std::vector<Tp> F, const std::vector<Tp> &p) {
    const int n = p.size();
    auto &&bin  = Binomial<Tp>::get(n);
    F.resize(n);
    for (int i = 0; i < n; ++i) F[i] *= bin.factorial(i);
    return apply_egf(F, p);
}

#line 2 "fps_as_operator.hpp"

#line 2 "binomial.hpp"

#include <algorithm>
#include <vector>

template<typename Tp> class Binomial {
    std::vector<Tp> factorial_, invfactorial_;

    Binomial() : factorial_{Tp(1)}, invfactorial_{Tp(1)} {}

    void preprocess(int n) {
        if (const int nn = factorial_.size(); nn < n) {
            int k = nn;
            while (k < n) k *= 2;
            k = std::min<long long>(k, Tp::mod());
            factorial_.resize(k);
            invfactorial_.resize(k);
            for (int i = nn; i < k; ++i) factorial_[i] = factorial_[i - 1] * i;
            invfactorial_.back() = factorial_.back().inv();
            for (int i = k - 2; i >= nn; --i) invfactorial_[i] = invfactorial_[i + 1] * (i + 1);
        }
    }

public:
    static const Binomial &get(int n) {
        static Binomial bin;
        bin.preprocess(n);
        return bin;
    }

    Tp binom(int n, int m) const {
        return n < m ? Tp() : factorial_[n] * invfactorial_[m] * invfactorial_[n - m];
    }
    Tp inv(int n) const { return factorial_[n - 1] * invfactorial_[n]; }
    Tp factorial(int n) const { return factorial_[n]; }
    Tp inv_factorial(int n) const { return invfactorial_[n]; }
};
#line 2 "fft.hpp"

#line 4 "fft.hpp"
#include <cassert>
#include <iterator>
#include <memory>
#line 8 "fft.hpp"

template<typename Tp> class FftInfo {
    static Tp least_quadratic_nonresidue() {
        for (int i = 2;; ++i)
            if (Tp(i).pow((Tp::mod() - 1) / 2) == -1) return Tp(i);
    }

    const int ordlog2_;
    const Tp zeta_;
    const Tp invzeta_;
    const Tp imag_;
    const Tp invimag_;

    mutable std::vector<Tp> root_;
    mutable std::vector<Tp> invroot_;

    FftInfo()
        : ordlog2_(__builtin_ctzll(Tp::mod() - 1)),
          zeta_(least_quadratic_nonresidue().pow((Tp::mod() - 1) >> ordlog2_)),
          invzeta_(zeta_.inv()), imag_(zeta_.pow(1LL << (ordlog2_ - 2))), invimag_(-imag_),
          root_{Tp(1), imag_}, invroot_{Tp(1), invimag_} {}

public:
    static const FftInfo &get() {
        static FftInfo info;
        return info;
    }

    Tp imag() const { return imag_; }
    Tp inv_imag() const { return invimag_; }
    Tp zeta() const { return zeta_; }
    Tp inv_zeta() const { return invzeta_; }
    const std::vector<Tp> &root(int n) const {
        // [0, n)
        assert((n & (n - 1)) == 0);
        if (const int s = root_.size(); s < n) {
            root_.resize(n);
            for (int i = __builtin_ctz(s); (1 << i) < n; ++i) {
                const int j = 1 << i;
                root_[j]    = zeta_.pow(1LL << (ordlog2_ - i - 2));
                for (int k = j + 1; k < j * 2; ++k) root_[k] = root_[k - j] * root_[j];
            }
        }
        return root_;
    }
    const std::vector<Tp> &inv_root(int n) const {
        // [0, n)
        assert((n & (n - 1)) == 0);
        if (const int s = invroot_.size(); s < n) {
            invroot_.resize(n);
            for (int i = __builtin_ctz(s); (1 << i) < n; ++i) {
                const int j = 1 << i;
                invroot_[j] = invzeta_.pow(1LL << (ordlog2_ - i - 2));
                for (int k = j + 1; k < j * 2; ++k) invroot_[k] = invroot_[k - j] * invroot_[j];
            }
        }
        return invroot_;
    }
};

inline int fft_len(int n) {
    --n;
    n |= n >> 1, n |= n >> 2, n |= n >> 4, n |= n >> 8;
    return (n | n >> 16) + 1;
}

namespace detail {

template<typename Iterator> inline void
butterfly_n(Iterator a, int n,
            const std::vector<typename std::iterator_traits<Iterator>::value_type> &root) {
    assert(n > 0);
    assert((n & (n - 1)) == 0);
    const int bn = __builtin_ctz(n);
    if (bn & 1) {
        for (int i = 0; i < n / 2; ++i) {
            const auto a0 = a[i], a1 = a[i + n / 2];
            a[i] = a0 + a1, a[i + n / 2] = a0 - a1;
        }
    }
    for (int i = n >> (bn & 1); i >= 4; i /= 4) {
        const int i4 = i / 4;
        for (int k = 0; k < i4; ++k) {
            const auto a0 = a[k + i4 * 0], a1 = a[k + i4 * 1];
            const auto a2 = a[k + i4 * 2], a3 = a[k + i4 * 3];
            const auto a02p = a0 + a2, a02m = a0 - a2;
            const auto a13p = a1 + a3, a13m = (a1 - a3) * root[1];
            a[k + i4 * 0] = a02p + a13p, a[k + i4 * 1] = a02p - a13p;
            a[k + i4 * 2] = a02m + a13m, a[k + i4 * 3] = a02m - a13m;
        }
        for (int j = i, m = 2; j < n; j += i, m += 2) {
            const auto r = root[m], r2 = r * r, r3 = r2 * r;
            for (int k = j; k < j + i4; ++k) {
                const auto a0 = a[k + i4 * 0], a1 = a[k + i4 * 1] * r;
                const auto a2 = a[k + i4 * 2] * r2, a3 = a[k + i4 * 3] * r3;
                const auto a02p = a0 + a2, a02m = a0 - a2;
                const auto a13p = a1 + a3, a13m = (a1 - a3) * root[1];
                a[k + i4 * 0] = a02p + a13p, a[k + i4 * 1] = a02p - a13p;
                a[k + i4 * 2] = a02m + a13m, a[k + i4 * 3] = a02m - a13m;
            }
        }
    }
}

template<typename Iterator> inline void
inv_butterfly_n(Iterator a, int n,
                const std::vector<typename std::iterator_traits<Iterator>::value_type> &root) {
    assert(n > 0);
    assert((n & (n - 1)) == 0);
    const int bn = __builtin_ctz(n);
    for (int i = 4; i <= (n >> (bn & 1)); i *= 4) {
        const int i4 = i / 4;
        for (int k = 0; k < i4; ++k) {
            const auto a0 = a[k + i4 * 0], a1 = a[k + i4 * 1];
            const auto a2 = a[k + i4 * 2], a3 = a[k + i4 * 3];
            const auto a01p = a0 + a1, a01m = a0 - a1;
            const auto a23p = a2 + a3, a23m = (a2 - a3) * root[1];
            a[k + i4 * 0] = a01p + a23p, a[k + i4 * 1] = a01m + a23m;
            a[k + i4 * 2] = a01p - a23p, a[k + i4 * 3] = a01m - a23m;
        }
        for (int j = i, m = 2; j < n; j += i, m += 2) {
            const auto r = root[m], r2 = r * r, r3 = r2 * r;
            for (int k = j; k < j + i4; ++k) {
                const auto a0 = a[k + i4 * 0], a1 = a[k + i4 * 1];
                const auto a2 = a[k + i4 * 2], a3 = a[k + i4 * 3];
                const auto a01p = a0 + a1, a01m = a0 - a1;
                const auto a23p = a2 + a3, a23m = (a2 - a3) * root[1];
                a[k + i4 * 0] = a01p + a23p, a[k + i4 * 1] = (a01m + a23m) * r;
                a[k + i4 * 2] = (a01p - a23p) * r2, a[k + i4 * 3] = (a01m - a23m) * r3;
            }
        }
    }
    if (bn & 1) {
        for (int i = 0; i < n / 2; ++i) {
            const auto a0 = a[i], a1 = a[i + n / 2];
            a[i] = a0 + a1, a[i + n / 2] = a0 - a1;
        }
    }
}

} // namespace detail

// FFT_n: A(x) |-> bit-reversed order of [A(1), A(zeta_n), ..., A(zeta_n^(n-1))]
template<typename Iterator> inline void fft_n(Iterator a, int n) {
    using Tp = typename std::iterator_traits<Iterator>::value_type;
    detail::butterfly_n(a, n, FftInfo<Tp>::get().root(n / 2));
}

template<typename Tp> inline void fft(std::vector<Tp> &a) { fft_n(a.begin(), a.size()); }

// IFFT_n: bit-reversed order of [A(1), A(zeta_n), ..., A(zeta_n^(n-1))] |-> A(x)
template<typename Iterator> inline void inv_fft_n(Iterator a, int n) {
    using Tp = typename std::iterator_traits<Iterator>::value_type;
    detail::inv_butterfly_n(a, n, FftInfo<Tp>::get().inv_root(n / 2));
    const Tp iv = Tp::mod() - (Tp::mod() - 1) / n;
    for (int i = 0; i < n; ++i) a[i] *= iv;
}

template<typename Tp> inline void inv_fft(std::vector<Tp> &a) { inv_fft_n(a.begin(), a.size()); }

// IFFT_n^T: A(x) |-> 1/n FFT_n((x^n A(x^(-1))) mod (x^n - 1))
template<typename Iterator> inline void transposed_inv_fft_n(Iterator a, int n) {
    using Tp    = typename std::iterator_traits<Iterator>::value_type;
    const Tp iv = Tp::mod() - (Tp::mod() - 1) / n;
    for (int i = 0; i < n; ++i) a[i] *= iv;
    detail::butterfly_n(a, n, FftInfo<Tp>::get().inv_root(n / 2));
}

template<typename Tp> inline void transposed_inv_fft(std::vector<Tp> &a) {
    transposed_inv_fft_n(a.begin(), a.size());
}

// FFT_n^T : FFT_n((x^n A(x^(-1))) mod (x^n - 1)) |-> n A(x)
template<typename Iterator> inline void transposed_fft_n(Iterator a, int n) {
    using Tp = typename std::iterator_traits<Iterator>::value_type;
    detail::inv_butterfly_n(a, n, FftInfo<Tp>::get().root(n / 2));
}

template<typename Tp> inline void transposed_fft(std::vector<Tp> &a) {
    transposed_fft_n(a.begin(), a.size());
}

template<typename Tp> inline std::vector<Tp> convolution_fft(std::vector<Tp> a, std::vector<Tp> b) {
    if (a.empty() || b.empty()) return {};
    const int n   = a.size();
    const int m   = b.size();
    const int len = fft_len(n + m - 1);
    a.resize(len);
    b.resize(len);
    fft(a);
    fft(b);
    for (int i = 0; i < len; ++i) a[i] *= b[i];
    inv_fft(a);
    a.resize(n + m - 1);
    return a;
}

template<typename Tp> inline std::vector<Tp> square_fft(std::vector<Tp> a) {
    if (a.empty()) return {};
    const int n   = a.size();
    const int len = fft_len(n * 2 - 1);
    a.resize(len);
    fft(a);
    for (int i = 0; i < len; ++i) a[i] *= a[i];
    inv_fft(a);
    a.resize(n * 2 - 1);
    return a;
}

template<typename Tp>
inline std::vector<Tp> convolution_naive(const std::vector<Tp> &a, const std::vector<Tp> &b) {
    if (a.empty() || b.empty()) return {};
    const int n = a.size();
    const int m = b.size();
    std::vector<Tp> res(n + m - 1);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) res[i + j] += a[i] * b[j];
    return res;
}

template<typename Tp>
inline std::vector<Tp> convolution(const std::vector<Tp> &a, const std::vector<Tp> &b) {
    if (std::min(a.size(), b.size()) < 60) return convolution_naive(a, b);
    if (std::addressof(a) == std::addressof(b)) return square_fft(a);
    return convolution_fft(a, b);
}
#line 7 "fps_as_operator.hpp"

// apply FPS as linear operator
// F(t): FPS in t where t = d/dx
// p(x): polynomial in x
template<typename Tp> inline std::vector<Tp> apply_egf(std::vector<Tp> F, std::vector<Tp> p) {
    // kinda transposed algorithm of binomial convolution.
    const int n = p.size();
    auto &&bin  = Binomial<Tp>::get(n);
    F.resize(n);
    for (int i = 0; i < n; ++i) {
        F[i] *= bin.inv_factorial(i);
        p[i] *= bin.factorial(i);
    }
    std::reverse(p.begin(), p.end());
    auto res = convolution(F, p);
    res.resize(n);
    std::reverse(res.begin(), res.end());
    for (int i = 0; i < n; ++i) res[i] *= bin.inv_factorial(i);
    return res;
}

template<typename Tp>
inline std::vector<Tp> apply_fps(std::vector<Tp> F, const std::vector<Tp> &p) {
    const int n = p.size();
    auto &&bin  = Binomial<Tp>::get(n);
    F.resize(n);
    for (int i = 0; i < n; ++i) F[i] *= bin.factorial(i);
    return apply_egf(F, p);
}

FPS as Linear Operator (fps_as_operator.hpp)