問題
$N$ 個の区別できるボールを $K$ 個の区別できない空でないグループに分ける場合の数（第2種 Stirling 数 $S(N, K)$）と、$N$ 個を任意個の空でないグループに分ける場合の数（Bell 数 $B_N$）を $998244353$ で求めよ。
さらに、$B_N$ を Bell の三角形（Bell triangle）を用いて $O(N^2)$ で求め、$S(N, K)$ を包除原理の式
$$S(N, K) = \frac{1}{K!} \sum_{j=0}^{K} (-1)^{K-j} \binom{K}{j} j^N$$
を用いて $O(K \log N)$ で求めよ。
入力形式
N K制約
$1 \le K \le N \le 10^6$
入出力例
入力例 1
5 2出力例 1
S(5,2) = 15
B(5) = 52入力例 2
10 3出力例 2
S(10,3) = 9330
B(10) = 115975ヒント (段階的開示)
ヒント1: 方向性
$S(N, K)$ は包除原理で閉じた形の式を持つ。$B_N = \sum_{k=0}^{N} S(N, k)$。
ヒント2: アプローチ
$S(N, K)$ の公式:
$$S(N, K) = \frac{1}{K!} \sum_{j=0}^{K} (-1)^{K-j} \binom{K}{j} j^N$$
これは畳み込みとして EGF で解釈できるが、$K \le 10^6$ の場合は直接 $O(K \log N)$ で計算する。
$B_N$ は Bell の三角形：
$B_N$ は Bell の三角形：
- 初段: $b_{1,1} = 1$
- $b_{i+1, 1} = b_{i, i}$（前の行の末尾）
- $b_{i+1, j} = b_{i+1, j-1} + b_{i, j-1}$（隣と上を足す）
- $B_N = b_{N, 1}$
ヒント3: 誘導
MOD = 998244353
# 階乗・逆元のテーブル
fact = [1] * (K + 1)
for i in range(1, K + 1):
fact[i] = fact[i-1] * i % MOD
inv_fact = [1] * (K + 1)
inv_fact[K] = pow(fact[K], MOD - 2, MOD)
for i in range(K - 1, -1, -1):
inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
# S(N, K) の計算
s_n_k = 0
for j in range(K + 1):
sign = 1 if (K - j) % 2 == 0 else MOD - 1
s_n_k = (s_n_k + sign * inv_fact[K-j] % MOD * inv_fact[j] % MOD * pow(j, N, MOD)) % MOD
s_n_k = s_n_k * fact[K] % MOD # ??? ここを修正模範解答 (Python)
import sys
def main():
MOD = 998244353
data = sys.stdin.read().split()
N, K = int(data[0]), int(data[1])
# --- 1. S(N, K) を O(K log N) で計算 ---
# S(N,K) = (1/K!) * Σ_{j=0}^{K} (-1)^{K-j} * C(K,j) * j^N
# = Σ_{j=0}^{K} (-1)^{K-j} / (K-j)! * j^N / j! ... いや、整理すると
# = (1/K!) * Σ_{j=0}^{K} C(K,j) * (-1)^{K-j} * j^N
maxn = max(N, K) + 1
fact = [1] * (maxn + 1)
for i in range(1, maxn + 1):
fact[i] = fact[i-1] * i % MOD
inv_fact = [1] * (maxn + 1)
inv_fact[maxn] = pow(fact[maxn], MOD - 2, MOD)
for i in range(maxn - 1, -1, -1):
inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
s_n_k = 0
for j in range(K + 1):
# C(K,j) = fact[K] * inv_fact[j] * inv_fact[K-j]
binom = fact[K] * inv_fact[j] % MOD * inv_fact[K - j] % MOD
sign = 1 if (K - j) % 2 == 0 else MOD - 1
s_n_k = (s_n_k + sign * binom % MOD * pow(j, N, MOD)) % MOD
s_n_k = s_n_k * inv_fact[K] % MOD
# --- 2. B(N) を Bell の三角形で O(N^2) 計算 ---
# Bell の三角形: row[i] は i 段目（1始まり）
# row[0] = [B(0)] = [1]
# row[i+1][0] = row[i][-1]
# row[i+1][j] = row[i+1][j-1] + row[i][j-1]
# B(N) = row[N-1][0]（0始まりなら row[N][0]）
if N == 0:
b_n = 1
else:
prev = [1] # Bell(0) = 1
for _ in range(N):
curr = [prev[-1]]
for j in range(len(prev)):
curr.append((curr[-1] + prev[j]) % MOD)
prev = curr
b_n = prev[0]
print(f"S({N},{K}) = {s_n_k}")
print(f"B({N}) = {b_n}")
main()Step-by-Step 解説
1第2種 Stirling 数の包除原理による導出
$j^N$ = 「$N$ 個のボールを $j$ 個の区別できる箱に（空でも可）入れる場合の数」。包除原理で「少なくとも1つ空」を除くと: $$K! \cdot S(N, K) = \sum_{j=0}^{K} (-1)^{K-j} \binom{K}{j} j^N$$ 両辺を $K!$ で割ると $S(N, K)$ が得られる。
$j^N$ = 「$N$ 個のボールを $j$ 個の区別できる箱に（空でも可）入れる場合の数」。包除原理で「少なくとも1つ空」を除くと: $$K! \cdot S(N, K) = \sum_{j=0}^{K} (-1)^{K-j} \binom{K}{j} j^N$$ 両辺を $K!$ で割ると $S(N, K)$ が得られる。
2Bell の三角形
B(0)=1
1 2 B(1)=1 のとき次の行先頭 = 行末尾 = 1
2 3 5 B(2)=2
5 7 10 15 B(3)=5
15 20 27 37 52 B(4)=15 → B(5)=523Bell 数の EGF
$$\sum_{n \ge 0} B_n \frac{x^n}{n!} = e^{e^x - 1}$$ FPS を使えば $O(N \log^2 N)$ での計算も可能だが、$N \le 10^6$ では Bell 三角形 $O(N^2)$ はメモリ問題が出るため注意。
$$\sum_{n \ge 0} B_n \frac{x^n}{n!} = e^{e^x - 1}$$ FPS を使えば $O(N \log^2 N)$ での計算も可能だが、$N \le 10^6$ では Bell 三角形 $O(N^2)$ はメモリ問題が出るため注意。
4計算量
- $S(N, K)$: $O(K \log N)$（$K$ 項の sum、各項に
pow(j, N, MOD)= $O(\log N)$） - $B_N$（Bell 三角形）: $O(N^2)$ — $N \le 10^4$ 程度が実用的
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
inv_fact[K] を掛けてしまう | $S = (1/K!) \times \ldots$ なのに * fact[K] する | * inv_fact[K] で割り算 |
| Bell 三角形の初期値 | prev = [0] から始める | prev = [1]（$B_0 = 1$） |
pow(0, N) で $0^0 = 1$ を確認 | $j=0$ のとき $j^N = 0$ になる（$N \ge 1$ なら 0） | Python の pow(0, N) は $N \ge 1$ で 0 を正しく返す |
次のステップ
- 発展問題: $\sum_{n=0}^{N} B_n x^n \pmod{p}$ を FPS + Newton 法で $O(N \log^2 N)$ 計算する