軽量 FPS の Power Projection

fps/power_projection_light.hpp · GitHub で見る

共通ページ · 軽量実装

Power Projectionの高速実装はこちら

#include "lib/fps/power_projection_light.hpp"

light_fps f{0, 1, 1}, w{1, 2, 3};
auto a = light_fps_algorithms::power_projection(f, w, 4); // {1, 5, 3, 0}
auto b = light_fps_algorithms::power_projection(f, 2, 4); // {0, 1, 1, 0}

返り値は 軽量 FPS の LightFormalPowerSeries<T> です。定数項は任意、入力は変更しません。高速実装の FPS や専用 NTT には依存しません。

操作	内容
power_projection(f,w,deg = -1)	\(\displaystyle a_i=\sum_{j=0}^{n-1}w_j[x^j]f(x)^i\) を返す。\(n=\texttt{w.size()}\)
power_projection(f,n,deg = -1)	\(a_i=[x^n]f(x)^i\) を返す。\(n\ge0\)

名前空間は light_fps_algorithms です。deg は返す要素数で、省略時は重み付き版が w.size()、係数版が n + 1 です。0 なら空列、空の重みなら零列を返します。空の f は零多項式とし、\(f(x)^0=1\) とします。

重み数と係数版の n + 1 は \(2^{21}\) 以下、deg は \(2^{22}\) 以下とします。法や係数型の条件は軽量 FPS と同じです。定数項を除いた級数に二変数 Bostan–Mori を適用し、非零の定数項は二項変換で補います。

重み数を \(n\)、出力数を \(m\) として、時間は \(f_0=0\) なら \(O(n\log^2 n+m)\)、一般には \(O(n\log^2 n+m\log m)\)、追加空間は \(O(n\log n+m)\) です。

依存ライブラリ

• FPS の合成・射影の汎用実装
• 軽量 FPS の合成・射影の共通実装
• 軽量 FPS の共通実装
• 軽量 FPS の基本演算
• 軽量 FPS の NTT
• 軽量 FPS の疎演算
• 疎 FPS の項収集・演算種別
• 多項式の積・打ち切り積の共通処理
• 多項式の共通積木
• 軽量な形式的冪級数
• modint998244353

検証コード

• test/fps_light_power_projection.test.cpp

コード

#ifndef CP_FPS_POWER_PROJECTION_LIGHT_HPP
#define CP_FPS_POWER_PROJECTION_LIGHT_HPP
#include "../components/fps_composition_light.hpp"
#endif

Back to top page