Simple Counting Problem, but Circular

元ネタ

日能研 電車広告 2026年9月掲載（麻布中学校、算数）

解説

まず、回転による同一視を行わずに塗り分けを数えることを考えます。 色どうしの隣接条件を表す $K \times K$ 行列 $A$ を、次のように定義します。

• 色 $i$ と色 $j$ が隣り合ってよいなら $A_{i,j}=1$
• 隣り合ってはならないなら $A_{i,j}=0$

条件 $(x_i,y_i)$ に対しては、$A_{x_i,y_i}$ と $A_{y_i,x_i}$ の両方を $0$ にします。 $x_i=y_i$ の条件は対角成分を $0$ にすることに対応します。

行列の積の定義より、$(A^d)_{i,j}$ は、色 $i$ から始めて $d$ 回隣接する色を選び、最後に色 $j$ に到達する方法の個数です。 したがって、長さ $d$ の塗り分けで末尾と先頭の隣接条件も満たすものの個数は、

$$\operatorname{tr}(A^d)=\sum_{i=1}^{K}(A^d)_{i,i}$$

となります。ここでは円周上の点を区別して数えています。 $d=1$ の場合も、同じ色を繰り返して条件を満たす色の個数として、$\operatorname{tr}(A)$ で数えられます。

回転による同一視にはバーンサイドの補題を使います。 点を時計回りに $r$ 個分ずらす回転で不変な塗り分けは、$d=\gcd(N,r)$ とすると、長さ $d$ のパターンを繰り返すことで得られます。 このパターンも末尾と先頭の隣接条件を満たす必要があるので、不変な塗り分けの個数は $\operatorname{tr}(A^d)$ です。

$d$ として現れる値は $N$ の約数です。 $0\leq r<N$ のうち $\gcd(N,r)=d$ を満たすものは、トーシェント関数を用いて $\varphi(N/d)$ 個と数えられます。 よって、求める答えは

$$\frac{1}{N}\sum_{d\mid N}\varphi(N/d)\operatorname{tr}(A^d)$$

です。

$N$ を素因数分解して約数を列挙し、各約数について $\varphi(N/d)$ と $A^d$ を計算します。 行列累乗を繰り返し二乗法で行えば、1つの約数あたり $O(K^3\log N)$ で計算できます。 素因数分解を試し割りで行う場合、全体の計算量は $O(\sqrt N+\tau(N)K^3\log N)$ です。 ここで $\tau(N)$ は $N$ の約数の個数です。

（今回は $N$ の制約が小さめなので、 $O(\tau^2 (N))$ の約数包除などでも答えを求めることができます、実際には $N$ がもうちょっと大きめでも解けますが、普通に出すとポラードローを要求することになったり $\frac1N$ を求めるパートで逆元が存在しなかったり色々不都合が生じるので今の形に…）

計算はすべて $1000000007$ を法として行います。 $N\leq 10^9<1000000007$ なので、最後の $N$ による除算は $N$ の逆元を掛けることで行えます。

ちなみに

元の設定は「円周上の点を白黒に塗り分け、黒い点どうしの隣接を禁止し、回転で一致するものを1通りと数える」というものでした。 今回の問題では $K=2$ とし、黒どうしの1ペアだけを禁止した場合に相当します。

この場合、回転による同一視を行わない塗り分けの個数は、フィボナッチ数列 $F_0=0, F_1=1$ を使って $F_{d-1}+F_{d+1}$ と書けます。 実験すると OEIS の A000358 が出てくるので没に…かなしい。