立方体の各面に対し、サイコロと同様に以下のように番号をつけ、面1などと呼ぶことにします。

立方体を回転させる方法は、面1をどこに移すか6通り×面2をどこに移すか4通りの24通りあります。

解法1 ポリアの数え上げ定理

ポリアの数え上げ定理は、「『回転一致を同一とみなすような書き込み方の数』は、各回転に対する『その回転で不変であるような書き込み方の数』の平均をとることで求まる」という定理です。(証明はここでは行いません)

したがって、24通りの各回転に対し、「その回転で不変であるような書き込み方の数」を求めることができれば元の問題を解くことができます。

例えば、面1,6の中心を通る軸で90度右に回転させる場合を考えてみます。この回転で不変であるには、面2,3,4,5に全て同じ数が書かれていれば良いです。面1に書かれた数を\(x\) 、面6に書かれた数を \(y\)、面2に書かれた数を \(z\) とおくと、そのような書き込み方は \(x+y+4z=S\) を満たす正整数の組 \((x,y,z)\) の個数だけあることがわかります（\(x,y,z\) が等しいかどうかは気にしていないことに注意してください）。この個数は桁DPや行列累乗などにより求めることができます。(後述)
他の回転についても同様です。

以上により、ある回転で不変であるような書き込み方の数が求められることがわかったので、ポリアの数え上げ定理により問題が解けました。

解法2 場合分け

まず、立方体に書き込む \(6\) つの整数を決めた後、立方体への数の書き込み方が何通りあるかを考えます。これは、\(6\) つの面に適当な順序をつけ順列とみなしたものから、立方体の回転により一致するものを取り除いていくことで求めることができます。

\(6\) つの整数を決めた後の書き込み方は、\(6\) つの数の中に同じ数が何個ずつ含まれているかのみによって決まります。例えば、\((1,1,1,2,2,3)\) を書き込む方法と \((1,2,2,2,3,3)\) を書き込む方法の場合の数は等しいです。したがって、そのような タイプ 別に、和が \(S\) となるような正整数の \(6\) つ組の個数を求めることができればよいです。

立方体に書き込む \(6\) つの整数を \(x_1\leq x_2 \leq x_3\leq x_4 \leq x_5 \leq x_6\) とします。これら \(5\) つの不等号について、等号が成立するかどうかで、\(32\) 通りの場合をそれぞれ考えます。

例として \(x_1=x_2 < x_3=x_4=x_5 <x_6\) かつ \(x_1+x_2+x_3+x_4+x_5+x_6=S\) となるような正整数の組の個数を考えます。

便宜上 \(x_0=0\) とし、 \(y_i=x_i-x_{i-1}\) と変数変換することでそのような組の個数は \(6y_1 +4y_3+y_6=S\) を満たす正整数の組 \((y_1,y_3,y_6)\) の個数に等しくなります。この方程式の解の個数は桁DPや行列累乗などにより求めることができます。(後述)
他の場合でも同様です。

タイプ 毎の組の個数が求められたため、これに立方体への書き込み方の場合の数をそれぞれ掛けて和を取ることで元の問題が解けました。

この解法は evima さんによるものです。

解法3 OEIS

\(S=6,7\) に対する答えが \(1\) であることは明らかであり、\(S=8,9\) に対する答えはサンプルに載っています。The On-Line Encyclopedia of Integer Sequences で “1,1,3,5 cube” と検索すると A54473 を見つけることができます。数列の母関数が載っているため、これを用いて \(O(\log S)\) で答えを求めることができます。

桁DP/行列累乗パートについて

例として \(x+y+4z=S\) を満たす正整数の組の個数を求める場合を考えます(他の場合も同様に求めることができます)。\(x,y,z\) からそれぞれ \(1\) を引き、\(S-6\) を改めて \(S\) と置くことで、「\(x+y+4z=S\) を満たす非負整数の組の個数を求めよ」という問題に変換できます。これを考えます。

桁DPの場合

dp[ \(i\) ][ \(j\) ]= \(i\) 桁以下の非負整数の組 \((x,y,z)\) であって、\(x+y+4z\) の下 \(i\) 桁が \(S\) と一致していて、上の桁に \(j\) 繰り上がるような組の個数

というDPを考えます。今回のケースでは、下の桁からの繰り上がりは高々 \(5\) なので、\(0\leq j\leq 5\) の範囲のみ考えれば良いです。あらかじめ、各 \(X\) に対して \(a+b+4c=X\) となる \(0\) 以上 \(9\) 以下の数からなる組 \((a,b,c)\) がいくつ存在するかを求めておけば遷移を高速に計算することができます。

行列累乗の場合

\(x+y+4z=S\) を満たす非負整数の組の個数を \(a_S\) と置きます。包除原理を用いることで、\(a_S=a_{S-1}+a_{S-1}+a_{S-4}-a_{S-1-1}-a_{S-1-4}-a_{S-1-4}+a_{S-1-1-4}\) という漸化式を満たすことがわかります。適切に行列累乗を用いることで、この漸化式を満たす数列の第 \(S\) 項は \(O(\log S)\) で求めることができます。