Taylor Shift（高速版）

fps/taylor_shift.hpp · GitHub で見る

全体サイト（256 KiB向け） · 高速実装

軽量実装（64 KiB）はこちら

#include "lib/fps/taylor_shift.hpp"

fps f{1, 2, 3};
auto shifted = taylor_shift(f, 2); // {17,14,3}
f = taylor_shift(std::move(f), 3); // {34,20,3}

法は 998244353 です。係数列の長さは変わりません。元の f.shift(c) と異なり、結果を返す関数です。元の配列を書き換える場合は返り値を代入してください。不要な入力は std::move で渡せます。

操作	内容・返り値	計算量
taylor_shift(f,c)	\(f(x+c)\) を返す。f は値渡し、c は係数型へ変換可能な値	\(O(n\log n)\)

例の最初の呼び出しは \(1+2(x+2)+3(x+2)^2=17+14x+3x^2\) を返します。この時点で元の f は変わらないので、次の行は元の多項式を 3 だけ平行移動しています。配列の添字をずらす操作ではなく、多項式の変数に定数を足す操作です。

係数数を \(n\) として、時間 \(O(n\log n)\)、追加空間 \(O(n)\) です。

依存ライブラリ

• FPS のブロック変換
• FPS の融合畳み込み
• FPS の定数係数畳み込み
• FPS の非対称畳み込み
• FPS と多項式除算の内部変換
• FPS の指数・冪の内部変換
• FPS の一点評価
• FPS 逆数のブロック変換
• FPS の内部演算
• FPS の結果配列への一括変換
• 疎 FPS の共通演算
• 疎 FPS の次数圧縮・前処理
• 疎 FPS の項収集・演算種別
• FPS 平方根のブロック変換
• Taylor Shift の中間積
• FPS の作業領域
• modint998244353 の共通剰余演算
• modint998244353 の共有畳み込み
• modint998244353 の階乗・逆階乗生成
• NTT（998244353）（高速版）
• 形式的冪級数（高速版）
• modint998244353

検証コード

• test/fps_taylor_shift.test.cpp

コード

#ifndef CP_FPS_TAYLOR_SHIFT_HPP
#define CP_FPS_TAYLOR_SHIFT_HPP

#include "fps.hpp"
#include "../components/mint_factorials.hpp"
#include "../components/fps_taylor_blocked.hpp"

#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC push_options
#pragma GCC optimize("O3")
#endif

template<class T>
FormalPowerSeries<T> taylor_shift(FormalPowerSeries<T> f, std::type_identity_t<T> c) {
	using F = FormalPowerSeries<T>;
	using O = fps_detail::Operations<T>;
	if constexpr (!std::is_same_v<T, mint>)
		return O::export_work(taylor_shift<mint>(O::import_work(f), mint::raw(c.val())));
	else {
		const int n = static_cast<int>(f.size());
		if (n <= 1 || c == T(0)) return f;
		assert(unsigned(n) < unsigned(T::mod()));
#if defined(__linux__) && defined(__x86_64__) && defined(__GNUC__) && !defined(__clang__)
		if (n >= 256 && n <= (1 << 19) && fps_detail::NTT::vectorized()) {
			fps_detail::taylor_detail::shift(f, c);
			return f;
		}
#endif
		F a(n), b(n), weights;
		mint_detail::factorials(O::words(a), O::words(b), n);
		fps_detail::NTT::product(O::words(a), O::words(a), O::words(f), n);
		std::reverse(a.begin(), a.end());
		weights = b;
		O::geometric_scale(b, T(1), c);
		F prod = F::multiply(a, b);
		std::reverse(prod.begin(), prod.begin() + n);
		fps_detail::NTT::product(O::words(f), O::words(prod), O::words(weights), n);
		return f;
	}
}

#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC pop_options
#endif

#endif

Back to top page