問題
長さ $n$ のネックレス（回転で同一視）、ブレスレット（回転+反転で同一視）、Lyndon 語の数を $k$ 文字アルファベット上で求めよ。答えは $10^9 + 7$ で割った余りを出力。
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $n$ | $1 \le n \le 10^6$ | 文字列長 |
| $k$ | $2 \le k \le 10^9$ | アルファベットサイズ |
入出力例
入力例1
6 2入力例2
4 3出力例1
14 14 9ネックレス14, ブレスレット14, Lyndon語9
出力例2
24 21 18概念図: Burnside の補題と Lyndon 語の関係
ヒント
ヒント1（方向性）
ネックレス数え上げには Burnside の補題を使う。回転群 $\mathbb{Z}_n$ の各元 $r^j$（$j=0,\ldots,n-1$）について、$r^j$ で不動な文字列の数は $k^{\gcd(n, j)}$ 個。
ヒント2（アプローチ）
$$N(n,k) = \frac{1}{n} \sum_{d|n} \phi(n/d) \cdot k^d$$
Lyndon 語数: $L(n,k) = \frac{1}{n} \sum_{d|n} \mu(n/d) k^d$（Möbius 反転）
ブレスレット: 二面体群 $D_n$（$|D_n|=2n$）での Burnside。反転の不動点数は $n$ の偶奇で異なる。
ヒント3（誘導）
def euler_phi(m):
result = m; x = m; p = 2
while p * p <= x:
if x % p == 0:
while x % p == 0: x //= p
result = result // p * (p - 1)
p += 1
if x > 1: result = result // x * (x - 1)
return result
def mobius(m):
result = 1; x = m; p = 2
while p * p <= x:
if x % p == 0:
x //= p
if x % p == 0: return 0 # p^2 | m
result = -result
p += 1
if x > 1: result = -result
return result模範解答
import sys
input = sys.stdin.readline
def solve():
n, k = map(int, input().split())
MOD = 10**9 + 7
divs = []
i = 1
while i * i <= n:
if n % i == 0:
divs.append(i)
if i != n // i: divs.append(n // i)
i += 1
def euler_phi(m):
result = m; x = m; p = 2
while p * p <= x:
if x % p == 0:
while x % p == 0: x //= p
result = result // p * (p - 1)
p += 1
if x > 1: result = result // x * (x - 1)
return result
def mobius(m):
result = 1; x = m; p = 2
while p * p <= x:
if x % p == 0:
x //= p
if x % p == 0: return 0
result = -result
p += 1
if x > 1: result = -result
return result
modinv = lambda a: pow(a, MOD-2, MOD)
inv_n = modinv(n)
necklace = 0
for d in divs:
necklace = (necklace + euler_phi(d) * pow(k, n//d, MOD)) % MOD
necklace = necklace * inv_n % MOD
lyndon = 0
for d in divs:
mu = mobius(n // d)
if mu != 0:
lyndon = (lyndon + mu * pow(k, d, MOD)) % MOD
lyndon = lyndon * inv_n % MOD
bracelet_rot = 0
for d in divs:
bracelet_rot = (bracelet_rot + euler_phi(d) * pow(k, n//d, MOD)) % MOD
if n % 2 == 1:
bracelet_ref = n * pow(k, (n+1)//2, MOD) % MOD
else:
bracelet_ref = (n//2 * pow(k, n//2+1, MOD) + n//2 * pow(k, n//2, MOD)) % MOD
bracelet = (bracelet_rot + bracelet_ref) % MOD * modinv(2*n % MOD) % MOD
print(necklace, bracelet, lyndon)
solve()Step-by-Step 解説
Step 1: Burnside の補題の適用
群 $G$ が集合 $X$ に作用するとき、軌道数（同値類の数）は：$$|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|$$
Step 2: ネックレス（回転群 $\mathbb{Z}_n$）
回転 $r^j$ で不動な文字列の数は $k^{\gcd(n,j)}$。
$$N(n,k) = \frac{1}{n} \sum_{j=0}^{n-1} k^{\gcd(n,j)} = \frac{1}{n} \sum_{d|n} \phi(d) \cdot k^{n/d}$$Step 3: Lyndon 語の数え上げ
Lyndon 語は最小回転が自分自身である文字列。Möbius 反転公式から：
$$L(n,k) = \frac{1}{n} \sum_{d|n} \mu(n/d) \cdot k^d$$Step 4: ブレスレット（二面体群 $D_n$）
$|D_n| = 2n$（$n$ 回転 + $n$ 反転）。反転の不動点数は $n$ の偶奇で異なる：
- $n$ 奇数: $n \cdot k^{(n+1)/2}$
- $n$ 偶数: $\frac{n}{2} k^{n/2+1} + \frac{n}{2} k^{n/2}$
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| phi(0) を呼ぶ | 約数に 0 は含まれない | divs に 0 を入れない |
| Möbius関数で $p^2|m$ の判定漏れ | 非正則整数で 0 を返す必要 | 二乗因子があれば 0 を返す |
| inv_n が 0 になる | $n$ が MOD の倍数 | $n \le 10^6$, MOD=$10^9+7$ なので安全 |
| bracelet の反転部分の場合分け漏れ | $n$ 偶奇で式が変わる | if n % 2 == 0 と 1 で分岐 |
次のステップ
- 発展問題: $k$ 色 $n$ ビーズのネックレスで「隣接同色禁止」条件（色環問題）
- 参考: Pólya 計数定理・Donald Knuth TAOCP Vol.4A
自己評価
理解度: / /
自分の回答:
気づき・メモ: