test/library-checker/Polynomial/TaylorShift.test.cpp

• View this file on GitHub
• Last update: 2025-11-24 18:49:07+09:00
• Problem: https://judge.yosupo.jp/problem/polynomial_taylor_shift

Depends on

• build/pch/stdc++.hpp
• library/formalpowerseries/Base.hpp
• library/formalpowerseries/functions/differential.hpp
• library/formalpowerseries/functions/exp.hpp
• library/formalpowerseries/functions/integral.hpp
• library/formalpowerseries/functions/log.hpp
• library/formalpowerseries/functions/taylor_shift.hpp
• library/util/Valarray.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/polynomial_taylor_shift"
#include <bits/stdc++.h>

#define REP(i, n) for (int i = 0; i < (n); i++)

#include <atcoder/convolution>
#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;
std::ostream &operator<<(std::ostream &os, mint a) {
    os << a.val();
    return os;
}
std::istream &operator>>(std::istream &is, mint &a) {
    long long b;
    is >> b;
    a = b;
    return is;
}

#include "library/formalpowerseries/Base.hpp"
#include "library/formalpowerseries/functions/taylor_shift.hpp"
using FPS = FormalPowerSeries<mint, 524288>;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, c;
    std::cin >> n >> c;
    FPS f(n);
    REP (i, n)
        std::cin >> f[i];
    fps::taylor_shift(f, mint(c));
    REP (i, n)
        std::cout << (i < f.size() ? f[i] : 0) << "\n "[i + 1 < n];
}

#line 1 "test/library-checker/Polynomial/TaylorShift.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/polynomial_taylor_shift"
#include <bits/stdc++.h>

#define REP(i, n) for (int i = 0; i < (n); i++)

#include <atcoder/convolution>
#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;
std::ostream &operator<<(std::ostream &os, mint a) {
    os << a.val();
    return os;
}
std::istream &operator>>(std::istream &is, mint &a) {
    long long b;
    is >> b;
    a = b;
    return is;
}

#line 2 "library/util/Valarray.hpp"
#include <ranges>
#line 4 "library/util/Valarray.hpp"

template <typename T> struct Valarray : std::vector<T> {
    using std::vector<T>::vector; // コンストラクタ継承
    Valarray(const std::vector<T> &v) : std::vector<T>(v.begin(), v.end()) {}

  private:
    template <typename Op>
    Valarray &apply_inplace(const Valarray &other, Op op) {
        if (this->size() < other.size())
            this->resize(other.size(), T(0));

        for (auto [a, b] : std::views::zip(*this, other))
            a = op(a, b);

        return *this;
    }

  public:
    Valarray &operator+=(const Valarray &other) {
        return apply_inplace(other, std::plus<>());
    }
    Valarray &operator-=(const Valarray &other) {
        return apply_inplace(other, std::minus<>());
    }
    Valarray &operator*=(const Valarray &other) {
        return apply_inplace(other, std::multiplies<>());
    }
    Valarray &operator/=(const Valarray &other) {
        return apply_inplace(other, std::divides<>());
    }

    friend Valarray operator+(Valarray a, const Valarray &b) { return a += b; }
    friend Valarray operator-(Valarray a, const Valarray &b) { return a -= b; }
    friend Valarray operator*(Valarray a, const Valarray &b) { return a *= b; }
    friend Valarray operator/(Valarray a, const Valarray &b) { return a /= b; }

    Valarray operator-() const {
        Valarray g = *this;
        for (T &a : g)
            a = -a;
        return g;
    }
};
#line 3 "library/formalpowerseries/Base.hpp"

template <typename T, int MX> struct FormalPowerSeries : Valarray<T> {
    using FPS = FormalPowerSeries;
    static constexpr int max_size = MX;
    using Valarray<T>::Valarray;
    using Valarray<T>::size;
    using Valarray<T>::resize;
    using Valarray<T>::at;
    using Valarray<T>::begin;
    using Valarray<T>::end;
    using Valarray<T>::back;
    using Valarray<T>::pop_back;
    using value_type = T;

    void strict(int n) {
        if (size() > n)
            resize(n);
        shrink();
    }
    void shrink() {
        while (size() and back() == 0)
            pop_back();
    }

    FormalPowerSeries() = default;

    FormalPowerSeries(const std::vector<T> &f) : Valarray<T>(f) {
        strict(MX);
        shrink();
    }

    static FPS unit() { return {1}; }
    static FPS x() { return {0, 1}; }
#pragma region operator
    FPS operator-() const { return FPS(Valarray<T>::operator-()); }

    FPS &operator+=(const FPS &g) {
        Valarray<T>::operator+=(g);
        shrink();
        return *this;
    }
    FPS operator+(const FPS &g) const { return FPS(*this) += g; }

    FPS &operator-=(const FPS &g) {
        Valarray<T>::operator-=(g);
        shrink();
        return *this;
    }
    FPS operator-(const FPS &g) const { return FPS(*this) -= g; }

    FPS &operator+=(const T &a) {
        if (!size())
            resize(1);
        at(0) += a;
        return *this;
    }
    FPS operator+(const T &a) const { return FPS(*this) += a; }
    friend FPS operator+(const T &a, const FPS &f) { return f + a; }

    FPS &operator-=(const T &a) {
        if (!size())
            resize(1);
        at(0) -= a;
        return *this;
    }
    FPS operator-(const T &a) { return FPS(*this) -= a; }
    friend FPS operator-(const T &a, const FPS &f) { return a + (-f); }

    FPS operator*(const FPS &g) const { return FPS(convolution(*this, g)); }
    FPS &operator*=(const FPS &g) { return (*this) = (*this) * g; }

    FPS &operator*=(const T &a) {
        for (size_t i = 0; i < size(); i++)
            at(i) *= a;
        return *this;
    }
    FPS operator*(const T &a) const { return FPS(*this) *= a; }
    friend FPS operator*(const T &a, const FPS &f) { return f * a; }

    FPS operator/(const FPS &g) const { return (*this) * g.inv(); }
    FPS &operator/=(const FPS &g) { return (*this) = (*this) / g; }

    FPS &operator/=(const T &a) { return *this *= a.inv(); }
    FPS operator/(const T &a) { return FPS(*this) /= a; }

    FPS &operator<<=(const int d) {
        if (d >= MX)
            return *this = FPS(0);
        resize(std::min(MX, int(size()) + d));
        for (int i = int(size()) - 1 - d; i >= 0; i--)
            at(i + d) = at(i);
        for (int i = d - 1; i >= 0; i--)
            at(i) = 0;
        return *this;
    }
    FPS operator<<(const int d) const { return FPS(*this) <<= d; }
    FPS &operator>>=(const int d) {
        if (d >= size())
            return *this = FPS(0);
        for (size_t i = d; i < size(); i++)
            at(i - d) = at(i);
        strict(int(size()) - d);
        return *this;
    }
    FPS operator>>(const int d) const { return FPS(*this) >>= d; }
#pragma endregion operator

    FPS pre(int n) const {
        if (size() <= n)
            return *this;
        return FPS(Valarray<T>(this->begin(), this->begin() + n));
    }

    // 最小の非ゼロ次数（すべて 0 のときは size()）を返す
    int order() const {
        for (int i = 0; i < int(size()); i++) {
            if (at(i) != 0)
                return i;
        }
        return int(size());
    }

    FPS inv(int SZ = MX) const {
        assert(size() and at(0) != 0);
        FPS res = {at(0).inv()};
        for (int n = 1; n < SZ; n <<= 1) {
            res *= (2 - this->pre(n << 1) * res);
            res.strict(n << 1);
        }
        res.strict(SZ);
        return res;
    }

    // *this = f_1 + f_2 x^n ⇒ [*this←f_1, return f_2]
    FPS separate(int n) {
        if (size() <= n)
            return FPS(0);
        FPS f_2(size() - n);
        for (size_t i = n; i < size(); i++)
            f_2[i - n] = at(i);
        strict(n);
        return f_2;
    }

    T operator()(T a) const {
        T res = 0, b = 1;
        for (size_t i = 0; i < size(); i++, b *= a)
            res += at(i) * b;
        return res;
    }
};
#line 3 "library/formalpowerseries/functions/differential.hpp"

namespace fps {

template <typename T, int MX>
FormalPowerSeries<T, MX> differential(FormalPowerSeries<T, MX> f) {
    if (f.size() <= 1) {
        return FormalPowerSeries<T, MX>{};
    }
    for (std::size_t i = 0; i < f.size() - 1; i++) {
        f[i] = (i + 1) * f[i + 1];
    }
    f.pop_back();
    return f;
}

} // namespace fps
#line 3 "library/formalpowerseries/functions/integral.hpp"

namespace fps {

template <typename T, int MX>
FormalPowerSeries<T, MX> integral(FormalPowerSeries<T, MX> f) {
    if (f.size() < MX) {
        f.resize(f.size() + 1);
    }
    for (int i = f.size() - 1; i > 0; i--) {
        f[i] = f[i - 1] / i;
    }
    f[0] = 0;
    return f;
}

} // namespace fps
#line 5 "library/formalpowerseries/functions/log.hpp"

namespace fps {

template <typename T, int MX>
FormalPowerSeries<T, MX> log(const FormalPowerSeries<T, MX> &f) {
    assert(f.size() and f[0] == 1);
    return integral(differential(f) / f);
}

} // namespace fps
#line 4 "library/formalpowerseries/functions/exp.hpp"

namespace fps {

template <typename T, int MX>
FormalPowerSeries<T, MX> exp(const FormalPowerSeries<T, MX>& f) {
    if (!f.size()) {
        return {1};
    }
    assert(f.size() > 0 && f[0] == 0);
    FormalPowerSeries<T, MX> res = {1};
    for (int n = 1; n < MX; n <<= 1) {
        res = res * (f.pre(n << 1) + 1 - log(res).pre(n << 1));
        res.strict(n << 1);
    }
    return res;
}

template <typename T, int MX>
FormalPowerSeries<T, MX> exp(const T& n) {
    if (n == 0) {
        return {1};
    }
    FormalPowerSeries<T, MX> res(MX);
    res[0] = 1;
    for (int i = 1; i < MX; i++) {
        res[i] = res[i - 1] * n / i;
    }
    return res;
}

} // namespace fps
#line 5 "library/formalpowerseries/functions/taylor_shift.hpp"

namespace fps {

template <typename T, int MX>
void taylor_shift(FormalPowerSeries<T, MX>& f, T c) {
    f.shrink();
    if (f.size() <= 1 || c == 0) {
        return;
    }
    int n = f.size();
    T fact = 1;
    for (int i = 0; i < n; i++) {
        if (i) {
            fact *= i;
        }
        f[i] *= fact;
    }
    std::reverse(f.begin(), f.end());
    f *= exp<T, MX>(c).pre(n);
    f.strict(n);
    std::reverse(f.begin(), f.end());
    T finv = fact.inv();
    for (int i = n - 1; i >= 0; i--) {
        f[i] *= finv;
        if (i) finv *= i;
    }
}

} // namespace fps
#line 23 "test/library-checker/Polynomial/TaylorShift.test.cpp"
using FPS = FormalPowerSeries<mint, 524288>;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, c;
    std::cin >> n >> c;
    FPS f(n);
    REP (i, n)
        std::cin >> f[i];
    fps::taylor_shift(f, mint(c));
    REP (i, n)
        std::cout << (i < f.size() ? f[i] : 0) << "\n "[i + 1 < n];
}

Back to top page