Day 063-Q3 | 文字列回転・共役類カウント（Lyndon語・ネックレス・ブレスレット）

問題

長さ $N$ の文字列で、アルファベット $\Sigma = \{0, 1, \ldots, K-1\}$ から構成されるものを考える。以下の 3種類の等価関係 の下での等価類の数を $\bmod 10^9+7$ で求めよ。

ネックレス数 $N(n, k)$：回転で等価な文字列の個数（巡回群 $C_n$ の作用）
ブレスレット数 $B(n, k)$：回転＋反転で等価な文字列の個数（二面体群 $D_n$ の作用）
Lyndon語の数 $L(n, k)$：長さ $n$ の Lyndon 語の個数（辞書順最小回転が自分自身）

制約

パラメータ	範囲
$T$	$1 \le T \le 1000$
$N$	$1 \le N \le 10^6$
$K$	$2 \le K \le 10^9$

入出力例

入力例 1

出力例 1

4 4 2
6 8 3
6 6 3

各行: ネックレス数、ブレスレット数、Lyndon語数の順。

概念図: N=3, K=2 の全 8 文字列の等価類

ヒント（段階的開示）

ヒント1: 方向性

Burnside の補題を使う。$|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|$（$X^g$ は $g$ で不動な元）。ネックレスは $G = C_n$（巡回群）、ブレスレットは $G = D_n$（二面体群）。Lyndon語はメビウス関数による公式 $L(n,k) = \frac{1}{n}\sum_{d|n} \mu(d) k^{n/d}$。

ヒント2: アプローチ

ネックレス: $N(n,k) = \frac{1}{n}\sum_{d|n} \phi(d) k^{n/d}$
ブレスレット: 二面体群の不動点を別計算。$n$ 奇数: $k^{(n+1)/2}$ 型反転 $n$ 個。$n$ 偶数: $n/2$ 個の頂点軸 + $n/2$ 個の辺軸
Lyndon語: $L(n,k) = \frac{1}{n}\sum_{d|n}\mu(d)k^{n/d}$

ヒント3: コード骨格

def euler_phi(n):
    result = n; temp = n; d = 2
    while d*d <= temp:
        if temp % d == 0:
            while temp % d == 0: temp //= d
            result = result // d * (d-1)
        d += 1
    if temp > 1: result = result // temp * (temp-1)
    return result

def mobius_val(n):
    factors = factorize(n)
    for p, e in factors.items():
        if e >= 2: return 0
    return (-1)**len(factors)

def necklace(n, k):
    return sum(euler_phi(d)*pow(k,n//d,MOD) for d in get_divisors(n)) * modinv(n) % MOD

def lyndon(n, k):
    return sum(mobius_val(d)*pow(k,n//d,MOD) for d in get_divisors(n)) * modinv(n) % MOD

模範解答 (Python)

import sys
input = sys.stdin.readline
MOD = 10**9 + 7

def modinv(a, m=MOD):
    return pow(a, m - 2, m)

def factorize(n):
    factors = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    return factors

def get_divisors(n):
    divs = []
    i = 1
    while i * i <= n:
        if n % i == 0:
            divs.append(i)
            if i != n // i:
                divs.append(n // i)
        i += 1
    return divs

def euler_phi(n):
    result = n; temp = n; d = 2
    while d * d <= temp:
        if temp % d == 0:
            while temp % d == 0: temp //= d
            result = result // d * (d - 1)
        d += 1
    if temp > 1:
        result = result // temp * (temp - 1)
    return result

def mobius_val(n):
    factors = factorize(n)
    for p, e in factors.items():
        if e >= 2:
            return 0
    return (-1) ** len(factors)

def necklace(n, k):
    divs = get_divisors(n)
    res = sum(euler_phi(d) * pow(k, n // d, MOD) for d in divs) % MOD
    return res * modinv(n) % MOD

def bracelet(n, k):
    neck = necklace(n, k)
    kmod = k % MOD
    if n % 2 == 1:
        ref_fixed = n * pow(kmod, (n + 1) // 2, MOD) % MOD
    else:
        ref_fixed = (n // 2 * pow(kmod, n // 2 + 1, MOD) +
                     n // 2 * pow(kmod, n // 2, MOD)) % MOD
    total = (neck * n % MOD + ref_fixed) % MOD
    return total * modinv(2 * n % MOD) % MOD

def lyndon(n, k):
    divs = get_divisors(n)
    res = 0
    for d in divs:
        mu = mobius_val(d)
        if mu != 0:
            res = (res + mu * pow(k, n // d, MOD)) % MOD
    return res * modinv(n) % MOD

def solve():
    T = int(input())
    out = []
    for _ in range(T):
        N, K = map(int, input().split())
        neck = necklace(N, K)
        brace = bracelet(N, K)
        lyn = lyndon(N, K)
        out.append(f"{neck} {brace} {lyn}")
    print('\n'.join(out))

solve()

Step-by-Step 解説

Step 1: Burnside の補題

群 $G$ が集合 $X$ に作用するとき、軌道（等価類）の数は $\frac{1}{|G|}\sum_{g\in G}|X^g|$。$X^g$ は $g$ で不動な元の集合。

Step 2: ネックレス（巡回群 $C_n$）

回転 $r^i$（$i=0,\ldots,n-1$）の不動点数：長さ $n$ の文字列が回転 $r^i$ で不動 ↔ 周期が $\gcd(n,i)$ を割り切る。不動点数は $k^{\gcd(n,i)}$。

$$N(n,k) = \frac{1}{n}\sum_{i=0}^{n-1}k^{\gcd(n,i)} = \frac{1}{n}\sum_{d|n}\phi(d)k^{n/d}$$

Step 3: ブレスレット（二面体群 $D_n$）

二面体群は回転 $n$ 個＋反転 $n$ 個の計 $2n$ 元。反転の不動点は $n$ の偶奇で場合分け：

$n$ 奇数: $n$ 個の反転軸、各軸で $k^{(n+1)/2}$ 文字が自由
$n$ 偶数: $n/2$ 個の頂点軸（$k^{n/2+1}$ 自由）+ $n/2$ 個の辺軸（$k^{n/2}$ 自由）

Step 4: Lyndon語（メビウス反転）

Lyndon 語は「辞書順最小回転が自分自身」な文字列。長さ $d \mid n$ の Lyndon 語は長さ $n/d$ 周期の文字列に対応。メビウス反転により：

$$L(n,k) = \frac{1}{n}\sum_{d|n}\mu(d)k^{n/d}$$

よくあるミス

ミス	原因	正しい書き方
ブレスレットを $N(n,k) + \text{反転}/2$ と間違える	群全体で Burnside を適用すべき	分子は回転不動点合計＋反転不動点合計、分母は $2n$
Möbius関数で二乗因子チェック漏れ	$e \ge 2$ の素因数を見落とす	`if e >= 2: return 0`
$\phi(d)$ と $\mu(d)$ を混同	ネックレスは $\phi$、Lyndon語は $\mu$	公式を丸暗記せず導出から確認

次のステップ

発展問題: $k$ 色 $n$ 頂点のグラフの彩色数え上げ（Pólya 計数定理の行列版）を実装せよ。

自己評価

完全理解おおむね理解要復習