Polynomial Taylor Shift
(Src/FPS/PolynomialTaylorShift.hpp)

• View this file on GitHub
• Last update: 2025-05-09 01:17:18+09:00
• Include: #include "Src/FPS/PolynomialTaylorShift.hpp"

概要

多項式 $f(x)$ 及び整数 $c$ に対して $f(x+c) = g(x)$ を満たす多項式 $g(x)$ の係数列を $\Theta (N\log N)$ で計算する。

ライブラリの使い方

template <class T, std::integral C, class F>
std::vector<T> PolynomialTaylorShift(std::vector<T> a, C c, F convolution) {

convolutionは畳み込み計算をする関数を渡す。atcoder::convolution<atcoder::modint998244353>を渡しておけば今の所は大丈夫そう？

Depends on

• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• ABC215-G Colorful Candies 2 (Test/AtCoder/abc215_g.test.cpp)
• Test/LC/polynomial_taylor_shift.test.cpp

Code

#pragma once

#include <algorithm>
#include <cassert>
#include <vector>
#include <concepts>

#include "../Template/TypeAlias.hpp"

namespace zawa {

template <class T, std::integral C, class F>
std::vector<T> PolynomialTaylorShift(std::vector<T> a, C c, F convolution) {
    assert(a.size());
    std::vector<T> invfact(a.size());
    T f{1};
    for (usize i = 1 ; i < a.size() ; i++) {
        f *= i;
        a[i] *= f;
    }
    invfact.back() = T{1} / f;
    for (usize i = a.size() - 1 ; i >= 1 ; i--) invfact[i - 1] = invfact[i] * T{i};
    std::vector<T> right(a.size());
    T powc = 1;
    for (usize i = 0 ; i < a.size() ; i++) {
        right[i] = invfact[i] * powc;
        powc *= T{c};
    }
    std::ranges::reverse(a);
    const usize n = a.size();
    std::vector<T> b = convolution(std::move(a), std::move(right));
    b.resize(n);
    std::ranges::reverse(b);
    for (usize i = 0 ; i < b.size() ; i++) b[i] *= invfact[i];
    return b;
}

} // namespace zawa

#line 2 "Src/FPS/PolynomialTaylorShift.hpp"

#include <algorithm>
#include <cassert>
#include <vector>
#include <concepts>

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 9 "Src/FPS/PolynomialTaylorShift.hpp"

namespace zawa {

template <class T, std::integral C, class F>
std::vector<T> PolynomialTaylorShift(std::vector<T> a, C c, F convolution) {
    assert(a.size());
    std::vector<T> invfact(a.size());
    T f{1};
    for (usize i = 1 ; i < a.size() ; i++) {
        f *= i;
        a[i] *= f;
    }
    invfact.back() = T{1} / f;
    for (usize i = a.size() - 1 ; i >= 1 ; i--) invfact[i - 1] = invfact[i] * T{i};
    std::vector<T> right(a.size());
    T powc = 1;
    for (usize i = 0 ; i < a.size() ; i++) {
        right[i] = invfact[i] * powc;
        powc *= T{c};
    }
    std::ranges::reverse(a);
    const usize n = a.size();
    std::vector<T> b = convolution(std::move(a), std::move(right));
    b.resize(n);
    std::ranges::reverse(b);
    for (usize i = 0 ; i < b.size() ; i++) b[i] *= invfact[i];
    return b;
}

} // namespace zawa

Back to top page