問題
$N$ マスを円環状に並べ各マスを $K$ 色で塗る。回転 $N$ 種＋反転 $N$ 種（二面体群 $D_n$, $|G|=2N$）で同一視するとき、相異なる塗り方を $10^9+7$ で。
制約
$1 \le N \le 10^9$
$1 \le K \le 10^9$
$\sigma_0(N) \le 1344$（HCN 上限）
時間制限: 2sec
入出力例
入力例 1
4 2出力例 1
6入力例 2
6 3出力例 2
92概念図: 二面体群 $D_4$ の作用
4 頂点正方形での回転（4 種）と反転（4 種）。それぞれの固定点数を Burnside で平均化。
ヒント (段階的開示)
ヒント1: 方向性
Burnside: $\#\text{Orbits} = \frac{1}{|G|} \sum_{g} |\text{Fix}(g)|$。$|G| = 2N$（$N$ 回転 + $N$ 反転）。
ヒント2: 回転の固定点
$r^k$ で不変な塗り方は周期 $\gcd(N, k)$。よって $\sum_k K^{\gcd(N,k)} = \sum_{d \mid N} \phi(N/d) K^d$。
ヒント3: 反転の固定点
$N$ 奇数: すべて「1 頂点軸」、固定点 $K^{(N+1)/2}$、$N$ 個。
$N$ 偶数: 「2 頂点軸」$N/2$ 個 ($K^{N/2+1}$) + 「2 辺中点軸」$N/2$ 個 ($K^{N/2}$)。
$N$ 偶数: 「2 頂点軸」$N/2$ 個 ($K^{N/2+1}$) + 「2 辺中点軸」$N/2$ 個 ($K^{N/2}$)。
模範解答 (Python)
import sys
input = sys.stdin.readline
MOD = 10**9 + 7
def divisors(n):
res = []; i = 1
while i*i <= n:
if n % i == 0:
res.append(i)
if i != n//i: res.append(n//i)
i += 1
return res
def prime_factors(n):
res = []; p = 2
while p*p <= n:
if n % p == 0:
res.append(p)
while n % p == 0: n //= p
p += 1
if n > 1: res.append(n)
return res
def phi(n):
res = n
for p in prime_factors(n):
res = res // p * (p - 1)
return res
def solve():
N, K = map(int, input().split())
inv2N = pow(2*N, MOD-2, MOD)
rot = 0
for d in divisors(N):
rot = (rot + phi(N // d) * pow(K, d, MOD)) % MOD
if N % 2:
refl = N * pow(K, (N+1)//2, MOD) % MOD
else:
half = N // 2
refl = (half * pow(K, half+1, MOD) + half * pow(K, half, MOD)) % MOD
ans = (rot + refl) % MOD * inv2N % MOD
print(ans)
solve()
Step-by-Step 解説
1群の同定
円環＋反転 → 二面体群 $D_n$、位数 $2N$。
円環＋反転 → 二面体群 $D_n$、位数 $2N$。
2回転の集約
$\sum_{k=0}^{N-1} K^{\gcd(N,k)} = \sum_{d \mid N} \phi(N/d) K^d$。約数列挙 $O(\sqrt{N})$。
$\sum_{k=0}^{N-1} K^{\gcd(N,k)} = \sum_{d \mid N} \phi(N/d) K^d$。約数列挙 $O(\sqrt{N})$。
3反転の場合分け
奇数 $N$: 1 種類のみ、固定点 $K^{(N+1)/2}$、$N$ 個。
偶数 $N$: 2 種類、$K^{N/2+1}$ と $K^{N/2}$、各 $N/2$ 個。
奇数 $N$: 1 種類のみ、固定点 $K^{(N+1)/2}$、$N$ 個。
偶数 $N$: 2 種類、$K^{N/2+1}$ と $K^{N/2}$、各 $N/2$ 個。
4Burnside で平均
$\frac{1}{2N}(\text{rot} + \text{refl})$、逆元はフェルマー。
$\frac{1}{2N}(\text{rot} + \text{refl})$、逆元はフェルマー。
計算量
約数列挙: $O(\sqrt{N})$
各約数で $\phi$ 計算: $O(\sqrt{N})$
合計: $O(\sigma_0(N) \sqrt{N}) \approx 1344 \times 31623 \approx 4 \times 10^7$
各約数で $\phi$ 計算: $O(\sqrt{N})$
合計: $O(\sigma_0(N) \sqrt{N}) \approx 1344 \times 31623 \approx 4 \times 10^7$
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 奇偶の場合分け忘れ | $N$ 偶数の 2 種類軸を見落とす | $N \bmod 2$ で必ず分岐 |
| 逆元計算ミス | $2N$ を $\bmod$ する忘れ | pow(2*N, MOD-2, MOD) |
| $\phi$ を毎回再計算 | 素因数列を使い回さない | $N$ の素因数列を 1 度求めても良い |
| 約数列挙の重複 | $i = N/i$ で 2 度カウント | if i != n//i ガード |
次のステップ
- 発展: 立方体・正多面体の彩色（より複雑な群）
- 応用: ネックレス・ブレスレット、グラフ同型クラス数え
- 関連: Pólya のサイクル指数 $Z_G(x_1, x_2, \ldots)$ による色重み付き拡張