Day 074-Q5 — Bell 多項式・EGF（Stirling 数第2種・奇数サイズ集合分割）

問題

$N$ 要素の集合 $\{1, 2, \ldots, N\}$ をちょうど $K$ 個の非空部分集合に分割する方法の数を $998244353$ で割った余りで求めよ（Stirling 数第 2 種 $S(N, K)$）。

さらに、各部分集合のサイズが奇数でなければならないという制約のもとで、ちょうど $K$ 個に分割する方法の数 $f(N, K)$ を求めよ。

入出力例

3
4 2
5 3
6 2

7
25
31

2
5 1
7 3

1
105

概念図: EGF と sinh の関係

ヒント

def stirling2(n, k):
    if k == 0: return 1 if n == 0 else 0
    if k > n: return 0
    s = 0
    for j in range(k+1):
        sign = 1 if j % 2 == 0 else MOD - 1
        s = (s + sign * comb(k, j) * pow(k-j, n, MOD)) % MOD
    return s * inv_fact[k] % MOD

def odd_partition(n, k):
    if k == 0: return 1 if n == 0 else 0
    if k > n: return 0
    inv_2k = pow(pow(2, k, MOD), MOD-2, MOD)
    s = 0
    for j in range(k+1):
        sign = 1 if (k-j) % 2 == 0 else MOD - 1
        base = (2*j - k) % MOD
        s = (s + sign * comb(k, j) * pow(base, n, MOD)) % MOD
    return factorial[n] * inv_fact[k] % MOD * inv_2k % MOD * s % MOD

模範解答

import sys
input = sys.stdin.readline

MOD = 998244353
MAXN = 100001

factorial = [1] * MAXN
for i in range(1, MAXN):
    factorial[i] = factorial[i-1] * i % MOD

inv_fact = [1] * MAXN
inv_fact[MAXN-1] = pow(factorial[MAXN-1], MOD-2, MOD)
for i in range(MAXN-2, -1, -1):
    inv_fact[i] = inv_fact[i+1] * (i+1) % MOD

def comb(n, r):
    if r < 0 or r > n:
        return 0
    return factorial[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD

def stirling2(n, k):
    """Stirling 数第2種 S(N, K)"""
    if k == 0:
        return 1 if n == 0 else 0
    if k > n:
        return 0
    s = 0
    for j in range(k + 1):
        sign = 1 if j % 2 == 0 else MOD - 1
        s = (s + sign * comb(k, j) % MOD * pow(k - j, n, MOD)) % MOD
    return s * inv_fact[k] % MOD

def odd_partition(n, k):
    """奇数サイズの部分集合のみ、ちょうど K 個に分割"""
    if k == 0:
        return 1 if n == 0 else 0
    if k > n:
        return 0
    inv_k_fact = inv_fact[k]
    inv_2k = pow(pow(2, k, MOD), MOD - 2, MOD)
    s = 0
    for j in range(k + 1):
        sign = 1 if (k - j) % 2 == 0 else MOD - 1
        base = (2 * j - k) % MOD
        s = (s + sign * comb(k, j) % MOD * pow(base, n, MOD)) % MOD
    return factorial[n] * inv_k_fact % MOD * inv_2k % MOD * s % MOD

def solve():
    T = int(input())
    out = []
    for _ in range(T):
        N, K = map(int, input().split())
        s2 = stirling2(N, K)
        op = odd_partition(N, K)
        out.append(f"{s2}")
        out.append(f"{op}")
    print("\n".join(out))

solve()

Step-by-Step 解説

Step 1: Stirling 数第 2 種の包除公式

$S(N, K)$ は $N$ 要素を $K$ 個の非空グループに分割する方法の数。$K$ 個のラベル付きグループへの割り当て $K^N$ から包除して $K!$ で割る：

Step 2: EGF による奇数サイズ制約

「1 個の奇数サイズ非空集合」の EGF は $\sinh(x) = \frac{e^x - e^{-x}}{2}$（奇数次の項のみ）。$K$ 個の集合の EGF は $\frac{\sinh^K(x)}{K!}$（集合は区別しないため $K!$ で割る）。

Step 3: $\sinh^K$ の展開

二項定理を使って：

$[x^N]$ of $e^{cx} = c^N / N!$。よって $f(N,K) = \frac{N!}{K! \cdot 2^K} \sum_{j=0}^{K} (-1)^{K-j} \binom{K}{j} (2j-K)^N$。

Step 4: 実装上の注意

• $(2j-K)^N \bmod p$: $2j-K$ が負の場合、Python では (2*j - k) % MOD で自動的に正になる
• pow(base, n, MOD) で高速に計算
• 前計算 factorial, inv_fact で $O(T \cdot K)$ の合計計算量

よくあるミス

次のステップ

• 発展問題: サイズが $\{1, 2, 4\}$ のいずれかの集合への分割数 → EGF = $(e^x + e^{2x}/2! + e^{4x}/4!)^K / K!$
• 類題: AtCoder 「集合分割・彩色数え上げ」系の EGF 問題
• さらに: Bell 多項式と Bell 三角形を使った動的計算

自己評価