Stirling 数を $p$ で割った余りの計算

概要
下降冪の性質
第 1 種 Stirling 数の計算
第 2 種 Stirling 数の計算
まとめ
二項係数を $p$ で割った余りの計算

概要

下降冪 $(x)_{n}$ 、符号つき第 1 種 Stirling 数 $s (n, k)$ 、第 2 種 Stirling 数 $S (n, k)$ を次で定義します：

$(x)_{n} = \prod_{0 ≦ i < n} (x - i) = \sum_{k = 0}^{n} s (n, k) x^{k}$ .
$x^{n} = \sum_{k = 0}^{n} S (n, k) (x)_{k}$ .

これらの組合せ論的な意味などは、例えば

https://ja.wikipedia.org/wiki/スターリング数

を参照してください。

また、定数 $N$ に対して、 $s (N, k)$ の列挙や $S (N, k)$ の列挙を $O (N \log N)$ 時間で行うことができます。

解法について、私の記事 [多項式・形式的べき級数] 高速に計算できるものたち内でも言及しています。

この記事では、以下の計算量で $s (n, k), S (n, k) (\mod p)$ を求める方法について解説します。

$O (\log_{p} n + p \log p)$ 時間で計算する
$O (p^{2})$ 時間の前計算のもと、 $O (\log n)$ 時間で計算する

競技プロでの出題も何度かあるようです。

以下、素数 $p$ を固定し、整数や多項式の等式はすべて $F_{p}$ でのもの（ $\mod p$ でのもの）とします。

下降冪の性質

非負整数 $i, j$ に対して次が成り立ちます。

$(x)_{p} = x^{p} - x, (x)_{i p + j} = (x^{p} - x)^{i} (x)_{j}$

$(x)_{p} = x^{p} - x$ は、Fermat の小定理と因数定理（体 $F_{p}$ における）から証明できます。 $(x)_{i p + j}$ については $p$ 項ごとにまとめたあと $(x)_{p} = x^{p} - x$ を用いればよいです。

第 1 種 Stirling 数の計算

第 $1$ 種 Stirling 数 $s (n, k)$ は、下降冪の係数 $[x^{k}] (x)_{n}$ でした。 $n = i p + j$ ( $0 ≦ j ≦ p - 1$ ) とすれば、上で述べた下降冪の性質から

$s (n, k) = [x^{k}] (x^{p} - x)^{i} (x)_{j} = [x^{k - i}] (x^{p - 1} - 1)^{i} (x)_{j} = [x^{k - i}] \sum_{a = 0}^{i} \sum_{b = 0}^{j} (\binom{i}{a}) x^{(p - 1) a} (- 1)^{i - a} \cdot s (j, b) x^{b}$

となります。したがって

$X = {(a, b) ∣ k - i = (p - 1) a + b, 0 ≦ a ≦ i, 0 ≦ b ≦ j}$

とすれば、 $s (n, k) = \sum_{(a, b) \in X} (- 1)^{i - a} (\binom{i}{a}) s (j, b)$ が成り立ちます。

$n, k$ を固定すると、 $X$ は高々 $2$ 元集合です。 $b = 0, p - 1$ に対応する $2$ 元というパターンはありえますが、この場合も $s (0, p - 1) = 0$ や $s (j, 0) = 0$ ( $j > 0$ ) より $s (j, b) \neq 0$ となる $(a, b)$ は唯一です。したがってその場合も、 $s (n, k) = (- 1)^{i - a} (\binom{i}{a}) s (j, b)$ が成り立つような $(a, b)$ がちょうどひとつ存在します。

第 2 種 Stirling 数の計算

$x^{n} = \sum_{k = 0}^{n} S (n, k) (x)_{k}$ となる $S (n, k)$ が求めるものです。下降冪の性質より

$x^{n} = \sum_{i = 0}^{\infty} \sum_{j = 0}^{p - 1} S (n, i p + j) (x^{p} - x)^{i} (x)_{j}$

と変形できます。したがって、 $S (n, i p + j)$ は次の手順で計算できます。

$x^{n}$ を $x^{p} - x$ 進展開したときの $(x^{p} - x)^{i}$ の係数 $g_{i} (x)$ を求める。つまり $x^{n} = \sum_{i = 0}^{\infty} g_{i} (x) (x^{p} - x)^{i}$ となる $p - 1$ 次以下の多項式 $g_{i}$ を求める。
$g_{i} (x) = \sum_{j = 0}^{p - 1} S (n, i p + j) (x)_{j}$ となる $S (n, i p + j)$ を求める。

$n = (p - 1) a + (i + b)$ となる整数 $a, b$ を、 $1 ≦ b ≦ p - 1$ となるようにとります。

$x^{n - i - b} = ((x^{p - 1} - 1) + 1)^{a} = \sum_{k = 0}^{a} (\binom{a}{k}) (x^{p - 1} - 1)^{k}$ より

$x^{n} = \sum_{k = 0}^{a} (\binom{a}{k}) (x^{p - 1} - 1)^{k} x^{i + b}$

が成り立ちます。

$k ≧ i + 1$ に対応する項は、 $(x^{p - 1} - 1)^{i + 1} x^{i + 1} = (x^{p} - x)^{i + 1}$ で割り切れるため、 $(x^{p} - x)$ 進展開の $(x^{p} - x)^{i}$ の係数へは寄与しません。
$k ≦ i - 2$ に対応する項は、次数が高々 $(p - 1) k + i + b ≦ p i - 2 (p - 1) + b < p i$ なので、 $(x^{p} - x)$ 進展開の $(x^{p} - x)^{i}$ の係数へは寄与しません。

よって、 $g_{i} (x)$ を求めるには、 $k = i, i - 1$ の部分

$(\binom{a}{i}) (x^{p} - x)^{i} x^{b} + (\binom{a}{i - 1}) (x^{p} - x)^{i - 1} x^{b + 1}$

を $(x^{p} - x)$ 進展開すればよいです。よって

$1 ≦ b < p - 1$ ならば、 $g_{i} (x) = (\binom{a}{i}) x^{b}$
$b = p - 1$ ならば、 $g_{i} (x) = (\binom{a}{i}) x^{p - 1} + (\binom{a}{i - 1})$

であることが分かります。第 2 種 Stirling 数については、

$1 ≦ b < p - 1$ ならば、 $S (n, i p + j) = (\binom{a}{i}) S (b, j)$
$b = p - 1$ ならば $S (n, i p + j) = (\binom{a}{i}) S (p - 1, j) + (\binom{a}{i - 1}) S (0, j)$

であることが分かります。後者の場合には一見 $2$ つの和ですが、 $j = 0$ であるか否かに応じて $S (p - 1, j)$ および $S (0, j)$ のうちちょうど一方のみが非 $0$ です。いずれにせよ、 $S (n, k) = (\binom{a}{i}) S (b, j)$ となる $(a, b)$ がちょうど一組見つかりました。

まとめ

次が示されました。

$n, k$ が与えられたとき、 $s (n, k) = (- 1)^{i - a} (\binom{i}{a}) s (j, b)$ が成り立つような $i, j, a, b$ ( $0 ≦ b ≦ j ≦ p - 1$ ) が $O (1)$ 時間で計算できる。
$n, k$ が与えられたとき、 $S (n, k) = (\binom{a}{i}) S (b, j)$ が成り立つような $i, j, a, b$ ( $0 ≦ j ≦ b ≦ p - 1$ ) が $O (1)$ 時間で計算できる。

これによって、 $s (n, k)$ や $S (n, k)$ は、

$n ≦ p - 1$ の場合の計算
二項係数の計算

により計算することができます。 $n ≦ p - 1$ の場合のすべての $s (n, k)$ , $S (n, k)$ は全体で $O (p^{2})$ 時間で前計算できます。前計算なしの場合でも $O (p \log p)$ 時間で計算できます。

二項係数を $p$ で割った余りの計算

有名ですが、ついでにこれも解説しておきます。 $(\binom{n}{k}) = [x^{k}] (1 + x)^{n}$ を計算します。

体 $F_{p}$ で（あるいは $\mod p$ で） $(1 + x)^{p} = 1 + x^{p}$ が成り立つことを利用します。

$n, k$ を $p$ で割った商と余りによって $n = n_{0} + p n_{1}, k = k_{0} + p k_{1}$ ( $0 ≦ k_{0}, n_{0} ≦ p - 1$ ) と書けば

$(\binom{n}{k}) = [x^{k}] (1 + x)^{n} = [x^{k_{0} + p k_{1}}] (1 + x)^{n_{0}} (1 + x^{p})^{n_{1}} = (\binom{n_{0}}{k_{0}}) \cdot [x^{p k_{1}}] (1 + x^{p})^{n_{1}} = (\binom{n_{0}}{k_{0}}) \cdot (\binom{n_{1}}{k_{1}})$

が得られます。この性質は Lucas の定理として知られています。

これを用いると、 $n < p$ の場合の二項係数のための前計算のもと、 $(\binom{n}{k})$ は $O (\log_{p} n)$ 時間で計算できます。

概要

下降冪の性質

第 1 種 Stirling 数の計算

第 2 種 Stirling 数の計算

まとめ

二項係数を p で割った余りの計算

二項係数を $p$ で割った余りの計算