StirlingSmallPLargeN

クラス · 第1種・第2種スターリング数 mod 小さい素数 p を、n, k が巨大（~1e18）でも求める

struct StirlingSmallPLargeN;

概要

第1種・第2種スターリング数 mod 小さい素数 p を、n, k が巨大（~1e18）でも求める

$(x)_n\equiv(x^p-x)^q(x)_r\pmod p$ と、 その双対にあたる基底展開の周期性を利用する。

構築・破棄

メンバ関数

メンバの詳細

(constructor)

explicit StirlingSmallPLargeN(unsigned p);

法pに対する計算テーブルを構築する

• パラメータ p: 小さい素数
• 計算量: 時間・空間ともに $O(p^2)$

stirling1

unsigned stirling1(std::int64_t n, std::int64_t k) const;

符号付き第1種スターリング数 $s(n,k)\bmod p$ を返す

• パラメータ n: 行番号。0以上
• パラメータ k: 列番号。範囲外では0を返す
• 計算量: $O(\log_p n)$

stirling2

unsigned stirling2(std::int64_t n, std::int64_t k) const;

第2種スターリング数 $S(n,k)\bmod p$ を返す

• パラメータ n: 行番号。0以上
• パラメータ k: 列番号。範囲外では0を返す
• 計算量: $O(\log_p n)$