重複数珠順列 - suisen のブログ

ほぼ自分用のメモなので色々雑かも．

問題

問題文

円周上に $N$ 個の玉が等間隔で並んでおり，それぞれの玉に色を塗ることを考える．色は $1,\dots,M$ の $M$ 色があり，複数の玉を同じ色で塗ってもよいし，使われない色があってもよい．玉に色を塗る方法の数を $\bmod 10 ^ 9+7$ で求めよ．ただし，回転や裏返しによって一致する塗り方は $1$ 通りとして数えるものとする．

制約

$1\leq N\leq 10 ^ 9$

$1\leq M\leq 10 ^ 9$

解法

コーシー・フロベニウスの定理 (バーンサイドの補題とも) が適用できる (バーンサイドの補題 - Wikipedia)．

以下，適当な玉を起点として反時計回りに玉 $0,\dots,N-1$ と名前を付ける．また，玉 $i$ に塗る色を $C_i\in\{1,\dots,M\}$ とする．回転および裏返しに対応する群は二面体群 $D_N$ であり，いま $D_N$ は集合

$X=\{(C_0,\dots,C_{N-1})\mid C_i\in\{1,\dots,M\}\;\text{for$\;i=0,\dots, N-1$}\}$

に作用している．

円を反時計回りに $\dfrac{2\pi}{N}$ 回転する作用素を $\sigma\in D_N$ とおく． $k=0,\dots,N-1$ に対して $\sigma ^ k$ の作用前後で一致する条件を考えると，

$C_i=C_{i+\gcd(k,N)\bmod N},\quad i=0,\dots,N-1$

が成り立つことが必要十分条件であると分かる．従って，

$|X ^ {\sigma ^ k}|=M ^ {\gcd(k,N)},\quad k=0,\dots,N-1$

である．

続いて，円を玉 $0$ と円の中心を通る軸 $L$ で折り返す作用素を $\tau\in D_N$ とおく． $D_N$ は， $\sigma$ と $\tau$ を用いて次のように表示できる．

$\begin{aligned} D_N &=\langle \sigma,\tau \mid \sigma ^ N=\tau ^ 2=\sigma\tau\sigma\tau=e \rangle\\ &=\{e,\sigma,\dots,\sigma ^ {N-1},\tau,\tau\sigma,\dots,\tau\sigma ^ {N-1}\}. \end{aligned}$

$\tau\sigma ^ k\in D_N$ は，円の中心を中心として軸 $L$ を $\dfrac{k\pi}{N}$ だけ回転した対称軸に対応する．

$N$ が奇数であれば，対称軸は必ずある頂点とその向かいの辺の中点を通る直線となるので，

$|X ^ {\tau\sigma ^ k}|=M ^ {\frac{N+1}{2}},\quad k=0,\dots,N-1$

である．

一方， $N$ が偶数であれば，対称軸が向かい合う二頂点を通るケースと向かい合う二辺の中点を通るケースが交互に現れる．従って，

$|X ^ {\tau\sigma ^ k}|= \begin{cases} M ^ {\frac{N}{2}+1} & k=0,2,\dots,N-2\\ M ^ {\frac{N}{2}} & k=1,3,\dots,N-1 \end{cases}$

である．

以上の結果から，問題の答えを $f(N,M)$ するとこれは以下のように表せる．

$f(N,M)= \begin{cases} \displaystyle\frac{1}{2N}\left(\sum_{i=1}^NM^{\gcd(N,i)}+NM^{\frac{N+1}{2}}\right) & \text{$N$ が奇数のとき}\\ \displaystyle\frac{1}{2N}\left(\sum_{i=1}^NM^{\gcd(N,i)}+\frac{NM^{\frac{N}{2}}}{2}+\frac{NM^{\frac{N}{2}+1}}{2} \right) & \text{$N$ が偶数のとき} \end{cases}$

しかし，このまま計算すると $O(N\log N)$ となってしまうので工夫する必要がある．

注目すべきは， $\gcd(N,i)$ の値が取り得る値は $N$ の約数に限られるという点である．そこで， $g=\gcd(N,i)$ の値ごとに $M ^ g$ をまとめて足し上げることを考える．つまり，

$\displaystyle \sum_{i=1}^NM^{\gcd(N,i)}=\sum_{g\mid N}\#\{i\in\{1,\dots,N\}\mid \gcd(N,i)=g\}\cdot M ^ g$

という式変形を行う．以下， $d=N/g$ とする ( $g\mid N$ より， $d$ は整数であることに注意)．

ここで， $\gcd(i,N)=g$ となるためには $g\mid i$ が必要であり，また， $g\mid N$ なので

$\displaystyle\begin{aligned} &\#\{i\in\{1,\dots,N\}\mid \gcd(N,i)=g\}\\ =&\#\{k\in\{1,\dots,d\}\mid \gcd(N,kg)=g\}\\ =&\#\{k\in\{1,\dots,d\}\mid \gcd(d,k)=1\}\\ =&\phi(d) \end{aligned}$

である．ただし， $\phi$ はオイラーのトーシェント関数である．以上より，次が成り立つ．

$\displaystyle \sum _ {i=1} ^ NM ^ {\gcd(N,i)}=\sum_{g\mid N} \phi(d)\cdot M ^ g .$

あとは， $\phi(d)$ を求めればよい． $\mathrm{PF}(d)$ を $d$ の素因数全体の集合とすると

$\displaystyle\begin{aligned} \phi(d)=d\prod_{p\in \mathrm{PF}(d)}\left(1-\dfrac{1}{p}\right) \end{aligned}$

であり， $\mathrm{PF}(d)$ は約数列挙の要領で $O(\sqrt{d})$ で求められるので，結局 $\phi(d)$ も $O(\sqrt{d})$ で求められる．

$N\leq 10 ^ 9$ の制約の下で $N$ の約数は最大でも $1344$ 個なので，和の計算は十分高速に行うことができ，この問題を解くことが出来た．

結論

$f(N,M)= \begin{cases} \displaystyle\frac{1}{2N}\left(\sum_{g\mid N} \phi(N/g)\cdot M^{g}+NM^{\frac{N+1}{2}}\right) & \text{$N$ が奇数のとき}\\ \displaystyle\frac{1}{2N}\left(\sum_{g\mid N} \phi(N/g)\cdot M^{g}+\frac{NM^{\frac{N}{2}}}{2}+\frac{NM^{\frac{N}{2}+1}}{2} \right) & \text{$N$ が偶数のとき} \end{cases}$

なお，裏返しを考慮しない場合の答え $g(N,M)$ は，そのまま裏返し部分を消せばよく，次のように求められる．

$\displaystyle g(N,M)=\frac{1}{N}\sum_{g\mid N} \phi(N/g)\cdot M^{g}$