FPS の合成・射影の内部処理（高速版）

components/fps_composition.hpp · GitHub で見る

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

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

Linux x86_64 / GCC 向けの内部部品です。呼び出し側で AVX2 の実行時判定を行います。通常は公開 API の 合成・power projection を使ってください。他の環境では汎用実装へ戻ります。法は \(p=998244353\) です。

このヘッダーは合成の専用変換と射影の専用変換を両方読み込む互換ヘッダーです。従来の raw API は全て使えます。内部から片方の演算だけを使う場合は対応する個別ヘッダーを include し、根表・列変換・作業領域などは共通部品を共有します。

fps_detail::composition_poly の Arena・Transform・Half はブロック変換の部品を共有します。内部配列は Arena から確保し、利用者の入力に padding や整列を要求しません。確保失敗時には通常の整列配列へ戻り、それも失敗した場合は例外となります。

内部 API	内容	計算量
compose_log(n)・compose_scratch(n)	合成に必要な変換次数と作業領域のワード数	\(O(1)\)
compose(t,f,g,h,scratch)	h.size() 項の \(f(g)\)。普通剰余の入力・出力、\(g_0=0\)。入力・出力は重ねない	\(O(n\log^2 n)\)
projection_log(n)・projection_scratch(n)	係数射影に必要な変換次数と作業領域のワード数	\(O(1)\)
power_projection(t,g,a,scratch)	\(a_k=[x^{n-1}]g^k\)、\(n=\texttt{a.size()}\)、\(g_0=0\)	\(O(n\log^2 n)\)
weighted_projection(t,g,w,a,scratch)	\(\displaystyle a_k=\sum_j w_j[x^j]g^k\)、w.size()==a.size()>32、\(g_0=0\)	\(O(n\log^2 n)\)
native_compose(f,nf,g,ng,out,n)	内部 Montgomery 係数の入力から、長さ n の合成を空の vector<mint> へ追加	\(O(n\log^2 n)\)
native_projection(g,ng,out,n)	内部 Montgomery 係数から、長さ n の係数射影を空の vector<mint> へ追加	\(O(n\log^2 n)\)
native_weighted_projection(g,ng,w,out,n,count)	n 個の重みによる射影の最初の count 項を空の vector<mint> へ追加。\(0<\texttt{count}\le n\)	\(O(n\log^2 n)\)

普通剰余の係数は \([0,p)\)、Montgomery 係数の内部ワードは \([0,2p)\) です。入力長を超える係数は 0 とし、出力次数以降は読みません。raw API の作業領域は Arena と同じ整列・余白を持たせます。重み付き raw API は projection_scratch(n) + Arena::footprint(6*detail::projection_length(n)) ワード、変換次数は projection_log(n)+1 を使います。

Kinoshita–Li 法の最初の 2 段と最後の 3 段を一変数の計算へ分解し、中間段では零となる列の変換を省きます。重み付き射影は一般の分子を最初の 2 段へ渡します。合成は外側係数に線形なので、外側入力と結果の Montgomery 変換を省略します。

合成の native 経路では \(n\le2^{21}\) とし、共通 Transform を専用列変換の根表も含む大きさで作ります。Tables はこの表を借り、別の表の生成を省きます。根と逆根の表現は共通で、借用中は Transform とその Arena が生存します。作業領域では従来の表の領域を予約したままとし、後続配列の配置を維持します。借用中にその領域は読み書きしません。

従来の raw API は根表を独立して確保し、compose_log・compose_scratch・projection_log・projection_scratch の値と前提は変わりません。Tables へ小さい Transform を渡した場合も、従来サイズの作業領域を渡せば独立した表へ戻ります。

項数を \(n\) として時間は \(O(n\log^2 n)\)、追加空間は合成が \(O(n\log n)\)、射影が \(O(n)\) です。

依存ライブラリ

• FPS のブロック変換
• FPS の合成の専用変換
• FPS の合成・射影の共通変換
• FPS の結果配列への一括変換
• FPS の射影の専用変換
• FPS の作業領域
• modint998244353 の共通剰余演算
• modint998244353

コード

#ifndef CP_COMPONENTS_FPS_COMPOSITION_HPP
#define CP_COMPONENTS_FPS_COMPOSITION_HPP

#include "fps_compose_blocked.hpp"
#include "fps_projection_blocked.hpp"

#endif

Back to top page