問題
$n$ 個の要素の置換 $\sigma \in S_n$ のうち、すべてのサイクルの長さが集合 $A$ に属する ものの個数を $\bmod 10^9+7$ で求めよ。
制約
| パラメータ | 範囲 |
|---|---|
| $n$ | $1 \le n \le 10^5$ |
| $|A|$ | $1 \le |A| \le n$ |
| $A$ の要素 | $1 \le a_i \le n$ |
| 出力 | $\bmod 10^9+7$ |
入出力例
入力例 1
6
2
1 2出力例 1
76サイクル長が 1 か 2 のみ（対合: $\sigma^2 = \text{id}$）の $S_6$ 置換の個数。対合の個数は $\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k}(2k-1)!!$。
概念図: 置換のサイクル分解と EGF
ヒント（段階的開示）
ヒント1: 方向性
置換の指数型母関数（EGF）を使う。EGF の「集合の exp 公式」: 「ラベル付き構造 A のマルチセット」の EGF = $\exp(\text{A の EGF})$。サイクルは置換を構成するマルチセットであり、長さ $\ell$ のサイクルの EGF は $x^\ell / \ell$（$(\ell-1)! / \ell! \cdot \ell! \cdot [x^\ell]$）。
ヒント2: アプローチ
- $f(x) = \sum_{\ell \in A, \ell \le n} x^\ell / \ell$ を $O(n)$ で構築（各 $\ell$ の mod 逆元を使用）
- $G(x) = \exp(f(x)) \bmod x^{n+1}$ を FPS exp（Newton 法）で $O(n \log n)$ 計算
- 答え = $[x^n] G(x) \times n! \bmod p$
ヒント3: FPS exp の Newton 法
# FPS exp の Newton 法（概要）
# g = exp(f) を満たす g を g_0=1 から反復
# g_{k+1} = g_k * (1 - log(g_k) + f) mod x^{2^{k+1}}
#
# 必要なサブルーチン:
# - poly_mul(a, b): NTT を使った多項式乗算
# - poly_inv(f, n): f の mod x^n での逆元
# - poly_deriv(f): 微分
# - poly_integ(f): 積分
# - poly_log(f, n): integral(f'/f) mod x^n
# - poly_exp(f, n): Newton 法で exp(f) mod x^n模範解答 (Python)
import sys
input = sys.stdin.readline
MOD = 10**9 + 7
def ntt(a, invert=False):
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(3, (MOD-1)//length, MOD)
if invert: w = pow(w, MOD-2, MOD)
for i in range(0, n, length):
wn = 1
for k in range(length//2):
u = a[i+k]; v = a[i+k+length//2]*wn%MOD
a[i+k] = (u+v)%MOD; a[i+k+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):
rl = len(a)+len(b)-1; n = 1
while n < rl: n <<= 1
fa = a+[0]*(n-len(a)); fb = b+[0]*(n-len(b))
ntt(fa); ntt(fb)
for i in range(n): fa[i] = fa[i]*fb[i]%MOD
ntt(fa, True); return fa[:rl]
def poly_inv(f, n):
g = [pow(f[0], MOD-2, MOD)]; size = 1
while size < n:
size <<= 1
fg = poly_mul(f[:size], g)[:size]
fg = [(-x)%MOD for x in fg]; fg[0] = (fg[0]+2)%MOD
g = poly_mul(g, fg)[:size]
return g[:n]
def poly_log(f, n):
df = [(i*f[i])%MOD for i in range(1, n)]
fi = poly_inv(f, n)
r = poly_mul(df, fi)[:n-1]
inv = [0]*n; inv[1] = 1
for i in range(2, n): inv[i] = -(MOD//i)*inv[MOD%i]%MOD
return [0]+[r[i]*inv[i+1]%MOD for i in range(n-1)]
def poly_exp(f, n):
g = [1]; size = 1
while size < n:
size <<= 1
lg = poly_log(g, size)
h = [0]*size
for i in range(min(len(f), size)): h[i] = (h[i]+f[i])%MOD
for i in range(size): h[i] = (h[i]-lg[i])%MOD
h[0] = (h[0]+1)%MOD
g = poly_mul(g, h)[:size]
return g[:n]
def solve():
n = int(input())
k = int(input())
A = set(map(int, input().split()))
f = [0]*(n+1)
for a in A:
if a <= n: f[a] = pow(a, MOD-2, MOD)
g = poly_exp(f, n+1)
fact = 1
for i in range(1, n+1): fact = fact*i%MOD
print(g[n]*fact%MOD)
solve()
Step-by-Step 解説
1置換の EGF 理論
置換は「サイクルの集合」として一意に分解される（cycle decomposition）。EGF の積公式: 「ラベル付き構造Aのマルチセット」の EGF = $\exp(\text{A の EGF})$。長さ $\ell$ のサイクルの EGF は $x^\ell / \ell$。
置換は「サイクルの集合」として一意に分解される（cycle decomposition）。EGF の積公式: 「ラベル付き構造Aのマルチセット」の EGF = $\exp(\text{A の EGF})$。長さ $\ell$ のサイクルの EGF は $x^\ell / \ell$。
2FPS exp の Newton 法
$g = e^f$ を満たす $g$ を $g_0=1$ から反復: $g_{k+1} = g_k(1 - \ln g_k + f) \bmod x^{2^{k+1}}$。各ステップ $O(n \log n)$、合計 $O(n \log n)$。
$g = e^f$ を満たす $g$ を $g_0=1$ から反復: $g_{k+1} = g_k(1 - \ln g_k + f) \bmod x^{2^{k+1}}$。各ステップ $O(n \log n)$、合計 $O(n \log n)$。
3FPS log の実装
$\ln g = \int (g'/g) \, dx$。微分 $O(n)$、逆元 $O(n \log n)$、積 $O(n \log n)$、積分 $O(n)$。全体 $O(n \log n)$。
$\ln g = \int (g'/g) \, dx$。微分 $O(n)$、逆元 $O(n \log n)$、積 $O(n \log n)$、積分 $O(n)$。全体 $O(n \log n)$。
4係数から答えを求める
EGF の定義より $[x^n] G(x) = (\text{n 元構造の個数}) / n!$。よって答え = $[x^n] G(x) \times n! \bmod p$。
EGF の定義より $[x^n] G(x) = (\text{n 元構造の個数}) / n!$。よって答え = $[x^n] G(x) \times n! \bmod p$。
計算量
FPS exp: $O(n \log n)$
NTT（1回）: $O(n \log n)$、定数 $\approx 5$
全体: $O(n \log n)$ — $n = 10^5$ で約 $10^7$ 演算
NTT（1回）: $O(n \log n)$、定数 $\approx 5$
全体: $O(n \log n)$ — $n = 10^5$ で約 $10^7$ 演算
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
f[0] != 0 のまま exp を呼ぶ | $\exp(c + \ldots)$ は $f[0]=0$ が前提 | サイクル長は $\ge 1$ なので $f[0]=0$ 自動的に成立 |
| NTT サイズが足りない | poly_mul の結果が切れる | 常に $\text{len}(a)+\text{len}(b)-1$ 以上の 2 冪 |
| 微分で次数ずれ | $[x^i]$ ではなく $[x^{i-1}]$ に書く | poly_deriv(f)[i] = (i+1)*f[i+1] |
| $n!$ を掛け忘れ | EGF の係数は個数 / $n!$ | g[n] * fact % MOD |
次のステップ
- 発展問題: サイクル長が偶数のみ / 奇数のみの置換の個数（$\cosh$, $\sinh$ の EGF）
- 関連: Bell 数（集合分割）= $[x^n] \exp(e^x - 1) \times n!$
- 応用: 有向グラフの巡回置換数え上げ（Burnside 補題 + EGF）