ABC 198 F - Cube

• 問題
• AC

サイコロが手元にあったので、回しながら考えた。まずはバーンサイドの補題を思い出す:

• 群$G$が集合$X$に作用するとする。この時、作用に関する同値類の総数は次の数に等しい:

$$\frac{1}{|G|}\sum _{g\in G}|F_g|$$

• ただし、$F_g$は$g$のfix、つまり$F_g=\{x\in X|g(x)=x\}$。

したがって、正六面体に対する回転操作で回転前と回転後が重なるものを列挙して、各回転に関するfixの大きさを求めればよい。正六面体に対する回転を分類すると以下の通り:

• $\mathrm{id}$: 恒等変換、つまり何もしない。1通り。
• $\alpha$: ある面の中心$A$と向かいにある面の中心$B$を結ぶ直線を軸に$90\mathrm{°}$回転する。どちら向きに回転するか述べていないが、ベクトルとみなして反時計回りに回転するとすると、$AB$と$BA$で別の回転になって$3\times 2=6$通りある。
• ${\alpha }^2$: ある面の中心$A$と向かいにある面の中心$B$を結ぶ直線を軸に$180\mathrm{°}$回転する。3通り。
• $\beta$: ある辺の中心$A$と向かいにある辺の中心$B$を結ぶ直線を軸に$180\mathrm{°}$回転する。辺対が6ペアあるので6通り。
• $\gamma$: ある頂点$A$と向かいにある頂点$B$を結ぶ直線を軸に$120\mathrm{°}$回転する。頂点対が$4$ペアあって、やはり回転する方向が2通りあるので$4\times 2=8$通り。

合わせて24通りあるので、fixの大きさを求めて全部足して24で割ればよいことになる。上の回転によってどの面とどの面が重なるかを調べると、以下の数え上げをすればよいことがわかる:

• $\mathrm{id}$: $x_1+x_2+x_3+x_4+x_5+x_6=S$の正整数解の総数を求めることに等しい。
• $\alpha$: $x_1+x_2+4x_3=S$の正整数解の総数を求めることに等しい。
• ${\alpha }^2$: $x_1+x_2+2x_3+2x_4=S$の正整数解の総数を求めることに等しい。
• $\beta$: $2x_1+2x_2+2x_3=S$の正整数解の総数を求めることに等しい。
• $\gamma$: $3x_1+3x_2=S$の正整数解の総数を求めることに等しい。

$\mathrm{id},\beta ,\gamma$は単純な重複組み合わせに帰着するが、$\alpha ,{\alpha }^2$がやや面倒に見える。

たとえば$\alpha$に関しては$1/(1-z{)}^2(1-z^4)$の$z^{S-6}$の係数を求めることに等しく、$1/(1-z{)}^2=\sum (\genfrac{}{}{0ex}{}{i+1}{i})z^i$（負の二項定理）を利用して$1+z^4+z^8+...$と掛けたときにどうなるか考えればよい。（自分は計算をバグらせてWolframAlphaに頼った） → $x_3$を決め打つと$x_1+x_2=S-4x_3$の正整数解が$S-4x_3-1$個だから、$\sum _{x=1}(S-4x-1)$を非負の範囲で計算すればいいのか。難しく考えてしまった。

---

見て何をすればよいかはわかったが、WolframAlphaがなければコンテスト中にはACできていなかった。結局は計算力なんだよな。

$mod6$で多項式になりそうなのでラグランジュ補間、というのを見てなるほどと思った。とはいえ小さいケースをちゃんと求めるのにもある程度の考察は必要か。

https://q.c.titech.ac.jp/docs/progs/polynomial_division.html
そもそも母関数が書けた時点で貼るだけになるらしい。というか、これを知らなくても漸化式に直して行列累乗はできるのでそれは考えるべきだった。