ABC198 F - Cube - かんプリンの学習記録

そもそも回転の列挙が難しい．

以下，厳密性を欠くので注意．

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

正六面体の ${6}$ つの面に正整数を書き込んだとき，正整数の和が ${S}$ となるような物の数を求めよ．ただし，正六面体を回転して一致する書き込み方は区別しない．

${6\leq S \leq 10^{18}}$

解説

和が ${S}$ となるようなものはまだしも，回転一致を区別しないのは難しそう．回転一致を除去した数え上げは蟻本とかに書いてあったように「ポリアの数え上げ定理」とか言うのを用いればよさそう．

以下の資料がわかりやすかったので参考にしました．

http://dopal.cs.uec.ac.jp/okamotoy/lect/2014/dme/lect07.pdf

回転して一致するものを区別しない場合の書き込み方の数は「回転の仕方」それぞれの「その回転で変化しないような書き込み方の数」の総和を「回転の仕方」の数で割ったものとなる(コーシー・フロベニウスの定理[バーンサイドの補題])．

「回転の仕方」をすべて見つける必要がある．まず適当に思いつく回転を列挙してみて，それらの回転を何回か行ったものすべて「回転の仕方」の一つとなっている．

例として正六面体(立方体)の回転を考える．

f:id:kanpurin:20210414232421p:plain:w150

例えば， ${1}$ の方向と ${2}$ の方向の回転のみで ${3}$ の方向の回転が行える．このようにして正六面体の回転は ${1}$ の方向と ${2}$ の方向の回転ですべての回転を表せる．( ${+}$ 恒等変換も回転と考える)

結局，「回転の仕方」が分からない場合は次のようにする．
①思いつく回転を列挙する．
②列挙した回転から他の回転を求める．「回転の仕方」の数は有限なのでちゃんと止まる(有限じゃないならそもそもこの方針じゃ解けない)．

これが面倒な時は「回転の仕方」の数は上の資料の ${14}$ 枚目のスライドに書かれてるようなやり方で求められるので，地道に見つけていけばいい．

「回転の仕方」が見つけられた後は，「その回転で変化しないような書き込み方の数」を見つける必要がある．
例えば，上の図の ${1}$ の方向への ${90}$ 度回転では ${4}$ つの面に書き込まれた数が同じで他2つはなんでもいいので ${a+b+4c=S}$ となる非負整数 ${a,b,c}$ の組の数を求める必要がある．

形式的冪級数で解く

${[x^S] (x+x^2+x^3+\cdots)(x+x^2+x^3+\cdots)(x^4+x^8+x^{12}+\cdots)\\ \displaystyle=[x^S] \frac{x}{1-x}\cdot\frac{x}{1-x}\cdot\frac{x^4}{1-x^4}=[x^{S-6}] \frac{1}{(1-x)^2(1-x^4)}}$