ABC198 F - Cube
本番中にACはできなかったがかなりいいところまで行ったのでメモ。
問題はこちら↓
問題概要
立方体の各面に対して正の整数を定めたとき、その和がちょうど $S$ であるような決め方は何通りあるか、$998244353$ で割った余りを答えよ。ただし、回転して一致するようなもの同士は区別しない。
制約
- $6\leq S\leq 10^{18}$
バーンサイドの補題を使った解法
バーンサイドの補題（Burnside's lemma）という有名な群論の定理を使うと $O(1)$ で答えを求めることができる。
定理のステートメントは次の通り。
$G$ を位数 $n$ の群とする。要素数 $n$ の有限集合 $V$ の元に整数を割り当てる方法の個数は、$G$ の元による数の入れ替えによって一致するものを同一視すれば
$$ \frac{1}{|G|}\sum_{g\in G} |V^g| $$
に等しい。ここで $|V^g|$ は $g$ による入れ替えによって不変となるような整数の割り当て方の総数を表す。
※本当はもっと一般化できるのだが、問題を解くのに最低限必要な形で紹介した。証明は例えば http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/2016-16.pdf などに詳しい。
※競プロの文脈でよく登場する「ポリアの数え上げ定理」は、バーンサイドの補題を $G$ が対称群であるような場合に限定し拡張したものである。
定理の主張は堅苦しいが、要するに
- 回転などの操作によって一致するものを重複なく数える数え上げ問題は、その回転全体がなす群が既知の場合には楽に計算ができる
ということである。
今回の例で言えば、$G$ に相当するのは立方体の回転全体がなす群（正六面体群）である（実は $G\cong S_4$）。$G$ は $4!=24$ 個の元からなる。
バーンサイドの補題によれば、$G$ の $24$ 個の元 $g$ それぞれに対して、回転 $g$ を作用させたときに数の割り当てが変化しないような割り当て方の総数を求めればよい。
実際には、$24$ 通りを個別に考える必要はなく、性質の同じ元ごとにまとめて計算すればよい。実際、$24$ 種類の回転は性質の異なる以下 $5$ パターンに分類できる。
- （恒等変換…$1$ 通り）恒等変換によって不変となるような数の書き込み方を数えるには、立方体の $6$ 個の面に書き込む数をすべて独立に決めてよい。
- （面の中心を通る回転軸周りの $1/4$ 回転…$6$ 通り）この回転を行っても不変になるためには、独立に決めてよい数は $3$ 個だけで、同じ数を $1, 1, 4$ 個ずつ書き込む必要がある。
- （面の中心を通る回転軸周りの $1/2$ 回転…$3$ 通り）この回転を行っても不変になるためには、独立に決めてよい数は $4$ 個だけで、同じ数を $1, 1, 2, 2$ 個ずつ書き込む必要がある。
- （立方体の中心を通る対角線周りの $1/3$ 回転）独立に決めてよい数は $2$ 個だけで、同じ数を $3, 3$ 個ずつ書き込む必要がある。
- （辺の中点を通る回転軸周りの $1/2$ 回転…$6$ 通り）独立に決めてよい数は $3$ 個だけで、同じ数を $2, 2$ 個ずつ書き込む必要がある。
ここから先は高校数学だけで求めることができる。結局、
- $a_1+\cdots+a_6=S$ の自然数解の個数を $A$
- $a_1+a_2+4a_3=S$ の自然数解の個数を $B$
- $a_1+a_2+2a_3+2a_4=S$ の自然数解の個数を $C$
- $3a_1+3a_2=S$ の自然数解の個数を $D$
- $2a_1+2a_2+2a_3=S$ の自然数解の個数を $E$
としたとき
$$ \frac{1}{24}(A+6B+3C+8D+6E) $$
が答えになることがわかる。あとは $A,B,C,D,E$ が求まればよい。
$a_1+\cdots+a_6=S$ の自然数解の個数
これは数学Aでおなじみの典型問題で、その答えは$S-6$ 個のマルと $5$ 個の仕切り棒を並べる順列の総数に等しい。よって
$$ A={}_{S-1}{\rm C}_5=\frac{1}{5!}(S-1)(S-2)(S-3)(S-4)(S-5). $$
$a_1+a_2+4a_3=S$ の自然数解の個数
$a_3$ を固定すれば、その答えは$S-4a_3-2$ 個のマルと $1$ 個の仕切り棒を並べる順列の総数に等しい。よって
$$ B=\sum_{k=1}^{\lfloor \frac{S-2}{4} \rfloor} (S-4k-1)=T(S-2T-3) $$
である（$T=\lfloor (S-2)/4\rfloor$ とおいた）。
$a_1+a_2+2a_3+2a_4=S$ の自然数解の個数
$a_3, a_4$ を固定すれば、その答えは$S-2a_3-2a_4-2$ 個のマルと $1$ 個の仕切り棒を並べる順列の総数に等しい。よって
$$ \begin{align} C&=\sum_{i, j}^{4\leq 2i+2j\leq S-2} (S-2i-2j-1)\\ &=\sum_{k=2}^{\lfloor \frac{S-2}{2} \rfloor}(S-2k-1)(k - 1)\\ &=\frac{1}{6}U(U-1)(3S-4U-7) \end{align} $$
である（$U=\lfloor (S-2)/2\rfloor$ とおいた）。
$3a_1+3a_2=S$ の自然数解の個数
これは簡単で、$S$ が $3$ の倍数でないなら答えは $0$、そうでなければ
$$ D=\frac{S}{3}-1 $$
である。
$2a_1+2a_2+2a_3=S$ の自然数解の個数
これも簡単で、$S$ が $2$ の倍数でないなら答えは $0$、そうでなければ
$$ E={}_{S/2-1}{\rm C}_2=\frac{1}{2}(S/2-1)(S/2-2) $$
である。
結論
以上より、$A, B, C, D, E$ が $O(1)$ で計算できるので、全体として $O(1)$ で答えを求めることができる。
自分の提出
ごちゃごちゃしていますが悪しからず…。
