グーを R 、パーを P 、チョキを S に対応させます。

\(1\) 回のじゃんけんであいこになるために Alice と Bob と Chris が出せる手の組み合わせは RRR PPP SSS RPS PSR SRP RSP PRS SPR の \(9\) 通りです。\(N\) 回のじゃんけんでこれらの手の組み合わせをそれぞれ \(X_1,X_2,\dots ,X_9\) 回出すとします。\(X_1,X_2,\dots ,X_9\) を決めたときの \(N\) 回のじゃんけんの手の出し方は

\[\frac{N!}{X_1!X_2!\dots X_9!}\]

通りあります。では \(X_1,X_2,\dots ,X_9\) が満たす条件について考えましょう。各々が出す手の種類ごとの合計を考えると次が従うことが分かります。

\[ \begin{cases} X_1+X_4+X_7=A_R\\ X_2+X_5+X_8=A_P\\ X_3+X_6+X_9=A_S\\ X_1+X_6+X_8=B_R\\ X_2+X_4+X_9=B_P\\ X_3+X_5+X_7=B_S\\ X_1+X_5+X_9=C_R\\ X_2+X_6+X_7=C_P\\ X_3+X_4+X_8=C_S\\ \end{cases} \leftrightarrow \begin{pmatrix} 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ \end{pmatrix} \begin{pmatrix} X_1\\ X_2\\ X_3\\ X_4\\ X_5\\ X_6\\ X_7\\ X_8\\ X_9\\ \end{pmatrix} = \begin{pmatrix} A_R\\ A_P\\ A_S\\ B_R\\ B_P\\ B_S\\ C_R\\ C_P\\ C_S\\ \end{pmatrix} \]

この \(9\times 9\) の行列のランクは \(7\) であり、\(X_1,\dots,X_9\) は一意に定まりません。 ここで \(Y_2=X_2-X_1,Y_3=X_3-X_1,Y_5=X_5-X_4,Y_6=X_6-X_4,Y_8=X_8-X_7,Y_9=X_9-X_7\) とすると

\[ \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & -1 & -1 & 1 \\ 0 & 1 & 1 & -1 & -1 & 0 \\ 1 & 0 & -1 & 1 & 0 & -1 \\ 0 & 1 & -1 & 0 & 1 & -1 \\ \end{pmatrix} \begin{pmatrix} Y_2\\ Y_3\\ Y_5\\ Y_6\\ Y_8\\ Y_9\\ \end{pmatrix} = \begin{pmatrix} A_P-A_R\\ A_S-A_R\\ B_P-B_R\\ B_S-B_R\\ C_P-C_R\\ C_S-C_R\\ \end{pmatrix} \]

が成り立ち、この \(6\times 6\) 行列はフルランクであることから \(Y_2,Y_3,Y_5,Y_6,Y_8,Y_9\) は一意に定まることがわかります。これらが整数であることが必要です。

以上から \((X_1,X_2,X_3,X_4,X_5,X_6,X_7,X_8,X_9)\) は \(3\) つの非負整数変数 \(x_1,x_4,x_7\) と \(6\) 個の整数定数 \(Y_2,Y_3,Y_5,Y_6,Y_8,Y_9\) によって \((x_1,x_1+Y_2,x_1+Y_3,x_4,x_4+Y_5,x_4+Y_6,x_7,x_7+Y_8,x_7+Y_9)\) と表せることが分かりました。これらすべてが非負であって和が \(N\) であることから、ある非負整数定数 \(C,l_1,l_4,l_7\) が存在して

\[ \begin{cases} x_1+x_4+x_7=C\\ x_1\ge l_1\\ x_4\ge l_4\\ x_7\ge l_7 \end{cases} \]

という条件のもとで \(x_1,x_4,x_7\) は自由に動くことができます。\(x_1,x_4,x_7\) が上記の条件を満たしながら動くときの

\[ \frac{N!}{x_1!(x_1+Y_2)!(x_1+Y_3)!x_4!(x_4+Y_5)!(x_4+Y_6)!x_7!(x_7+Y_8)!(x_7+Y_9)!} \]

の和を求めればよく、FFT によって高速に計算することができます。計算量は \(\mathrm{O}(N\log N)\) 時間です。

実装例(C++)