問題
$N$ 要素の集合を非空な順序付き部分集合に分割する方法の総数を求めよ。ただし各部分集合のサイズは奇数でなければならず、分割の順序（ブロック順序）も区別する。答えを $\bmod 998244353$ で求めよ。
制約
| パラメータ | 範囲 |
|---|---|
| $N$ | $1 \le N \le 10^5$ |
| MOD | $998244353$（NTT 対応素数） |
入出力例
入力例 1
5出力例 1
270入力例 2
1出力例 2
1概念図: EGF と FPS 逆元の流れ
ヒント（段階的開示）
ヒント1: 方向性
EGF（指数型母関数）を用いる。奇数サイズの非空集合の EGF は $E_{odd}(z) = \sinh(z) = \sum_{k \text{ odd}} z^k / k!$。
順序付き分割（$k$ ブロック、各ブロックが奇数サイズ）の EGF は $E_{odd}^k(z)$。全 $k \ge 1$ の和は $F(z) = \frac{E_{odd}(z)}{1 - E_{odd}(z)}$。答えは $N! \cdot [z^N] F(z)$。
ヒント2: アプローチ
- $E_{odd}$ の係数列を構築:
E[k] = inv_fact[k]($k$ 奇数), else $0$ - $1 - E_{odd}$ の係数列を構築
- FPS 逆元 $G = 1 / (1 - E_{odd})$ を Newton 法 + NTT で計算 ($O(N \log N)$)
- $F = E_{odd} \cdot G$ を NTT 畳み込みで計算
- 答え: $N! \cdot F[N] \pmod{998244353}$
ヒント3: コード骨格
MOD = 998244353
# 前計算: 階乗・逆階乗
fact = [1] * (N+2)
for i in range(1, N+2): fact[i] = fact[i-1] * i % MOD
inv_fact = [1] * (N+2)
inv_fact[N+1] = pow(fact[N+1], MOD-2, MOD)
for i in range(N, -1, -1): inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
# E_odd の係数
E = [0] * (N+1)
for k in range(1, N+1, 2): E[k] = inv_fact[k]
# 1 - E_odd
f = [(-E[i]) % MOD for i in range(N+1)]
f[0] = 1
# FPS 逆元
G = poly_inv(f, N+1) # Newton法 + NTT
# F = E * G
F = poly_mul(E, G)
# 答え
print(fact[N] * F[N] % MOD)模範解答 (Python)
import sys
input = sys.stdin.readline
MOD = 998244353
g_root = 3
def ntt(a, invert):
n = len(a)
j = 0
for i in range(1, n):
bit = n >> 1
while j & bit: j ^= bit; bit >>= 1
j ^= bit
if i < j: a[i], a[j] = a[j], a[i]
length = 2
while length <= n:
w = pow(g_root, (MOD-1)//length, MOD)
if invert: w = pow(w, MOD-2, MOD)
for i in range(0, n, length):
wn = 1
for jj in range(length//2):
u = a[i+jj]; v = a[i+jj+length//2]*wn%MOD
a[i+jj] = (u+v)%MOD; a[i+jj+length//2] = (u-v)%MOD
wn = wn*w%MOD
length <<= 1
if invert:
ni = pow(n, MOD-2, MOD)
for i in range(n): a[i] = a[i]*ni%MOD
def poly_mul(a, b):
res_len = len(a)+len(b)-1
n = 1
while n < res_len: n <<= 1
fa = a+[0]*(n-len(a)); fb = b+[0]*(n-len(b))
ntt(fa, False); ntt(fb, False)
for i in range(n): fa[i] = fa[i]*fb[i]%MOD
ntt(fa, True)
return fa[:res_len]
def poly_inv(f, n):
result = [pow(f[0], MOD-2, MOD)]
k = 1
while k < n:
k <<= 1
g_cur = result+[0]*(k-len(result))
f_cur = f[:k]+[0]*(k-len(f[:k]))
fg = poly_mul(f_cur, g_cur)[:k]
fg2 = [(-x)%MOD for x in fg]
fg2[0] = (fg2[0]+2)%MOD
result = poly_mul(g_cur, fg2)[:k]
return result[:n]
def solve():
N = int(input())
fact = [1]*(N+2)
for i in range(1, N+2): fact[i] = fact[i-1]*i%MOD
inv_fact = [1]*(N+2)
inv_fact[N+1] = pow(fact[N+1], MOD-2, MOD)
for i in range(N, -1, -1): inv_fact[i] = inv_fact[i+1]*(i+1)%MOD
E = [0]*(N+1)
for k in range(1, N+1, 2): E[k] = inv_fact[k]
f = [(-E[i])%MOD for i in range(N+1)]
f[0] = 1
G = poly_inv(f, N+1)
F = poly_mul(E, G)
print(fact[N]*F[N]%MOD if N < len(F) else 0)
solve()
Step-by-Step 解説
1EGF の設計
奇数サイズの非空集合の EGF: $E_{odd}(z) = \sum_{k=1,3,5,...} z^k / k! = \sinh(z)$。EGF 係数の意味: $[z^k]E_{odd}(z) = 1/k!$ は「$k$ 要素集合を1ブロックとして選ぶ場合の数（$k!/k! = 1$ ラベル付き）」。
奇数サイズの非空集合の EGF: $E_{odd}(z) = \sum_{k=1,3,5,...} z^k / k! = \sinh(z)$。EGF 係数の意味: $[z^k]E_{odd}(z) = 1/k!$ は「$k$ 要素集合を1ブロックとして選ぶ場合の数（$k!/k! = 1$ ラベル付き）」。
2順序付き分割の EGF
$k$ ブロック分割（各ブロックが奇数サイズ）の EGF: $E_{odd}^k(z)$。ブロックの順序を区別する全 $k \ge 1$ の和: $$F(z) = \sum_{k=1}^{\infty} E_{odd}(z)^k = \frac{E_{odd}(z)}{1 - E_{odd}(z)}$$
$k$ ブロック分割（各ブロックが奇数サイズ）の EGF: $E_{odd}^k(z)$。ブロックの順序を区別する全 $k \ge 1$ の和: $$F(z) = \sum_{k=1}^{\infty} E_{odd}(z)^k = \frac{E_{odd}(z)}{1 - E_{odd}(z)}$$
3FPS 逆元（Newton 法）
$f = 1 - E_{odd}$ として $f^{-1}$ を Newton 法で計算。初期値 $g_0 = f_0^{-1} = 1$。各ステップ: $g_{k} = g_{k-1}(2 - f \cdot g_{k-1}) \pmod{x^{2^k}}$。$O(N \log N)$ で収束。
$f = 1 - E_{odd}$ として $f^{-1}$ を Newton 法で計算。初期値 $g_0 = f_0^{-1} = 1$。各ステップ: $g_{k} = g_{k-1}(2 - f \cdot g_{k-1}) \pmod{x^{2^k}}$。$O(N \log N)$ で収束。
4係数読み出し
$F = E_{odd} \cdot G$（NTT 畳み込み）。EGF の定義より答え $= N! \times [z^N] F(z) = N! \times F[N] \pmod{MOD}$。
$F = E_{odd} \cdot G$（NTT 畳み込み）。EGF の定義より答え $= N! \times [z^N] F(z) = N! \times F[N] \pmod{MOD}$。
計算量
FPS 逆元: $O(N \log N)$（Newton 法 + NTT）
多項式乗算: $O(N \log N)$（NTT）
全体: $O(N \log N)$
MOD: $998244353 = 119 \times 2^{23} + 1$（NTT 対応素数）
多項式乗算: $O(N \log N)$（NTT）
全体: $O(N \log N)$
MOD: $998244353 = 119 \times 2^{23} + 1$（NTT 対応素数）
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
f[0] が 1 でない | 1 - E_odd の定数項確認 | f[0] = 1（E[0] = 0 なので） |
| poly_inv の次数不足 | $N+1$ 項が必要 | poly_inv(f, N+1) |
| EGF と OGF の混同 | EGF の係数には $n!$ の調整 | EGF: 答えは $N! \times [z^N]F$ |
| NTT の MOD を $10^9+7$ に | NTT 対応素数でない | MOD = 998244353、原始根 = 3 |
次のステップ
- 発展問題: 偶数サイズのブロックのみの順序付き分割（$E_{even}(z) = \cosh(z) - 1$）
- 関連: EGF の
exp / logを使った連結グラフ数え上げ - 応用: サイクル長制約付き置換数え上げ（Day054 Q4 の拡張）