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

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

概要

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

$(x)_n = \prod_{0\leq 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)\pmod{p}$ を求める方法について解説します。

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

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

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

下降冪の性質

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

$$(x)_p = x^p-x, \qquad (x)_{ip+j} = (x^p-x)^i(x)_j$$

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

第 1 種 Stirling 数の計算

第 $1$ 種 Stirling 数 $s(n,k)$ は、下降冪の係数 $[x^k] (x)_n$ でした。$n = ip+j$ ($0\leq j\leq 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)\mid k-i=(p-1)a+b, 0\leq a\leq i, 0\leq b\leq 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,ip+j) (x^p-x)^i(x)_j$$

と変形できます。したがって、$S(n,ip+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,ip+j) (x)_j$ となる $S(n,ip+j)$ を求める。

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

$x^{n-i-b}=\bigl((x^{p-1}-1)+1\bigr)^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)^kx^{i+b}$$

が成り立ちます。

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

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

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

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

$1\leq 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\leq b < p-1$ ならば、$S(n,ip+j) = \binom{a}{i}S(b,j)$
$b=p-1$ ならば $S(n,ip+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\leq b \leq j\leq p – 1$) が $O(1)$ 時間で計算できる。
$n,k$ が与えられたとき、$S(n,k) = \binom{a}{i}S(b,j)$ が成り立つような $i,j,a,b$ ($0\leq j\leq b\leq p-1$) が $O(1)$ 時間で計算できる。

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

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

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

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

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

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

$n,k$ を $p$ で割った商と余りによって $n = n_0 + pn_1, k = k_0 + pk_1$ ($0\leq k_0,n_0\leq p-1$) と書けば

$$\binom{n}{k}=[x^k](1+x)^n=[x^{k_0+pk_1}](1+x)^{n_0}(1+x^p)^{n_1} = \binom{n_0}{k_0}\cdot [x^{pk_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_pn)$ 時間で計算できます。