OUPC2020 B. グリコ on Line - もちもちの記

座標Xの正負は関係ないので $X=|X|$ として考えます。

チョキに勝つと $3$ 回操作できて、チョキ以外に勝つと $6$ 回操作できるので、チョキに勝った場合とチョキ以外に勝った場合に分けて考えることにします。

文字列に含まれるチョキの数を $C$ 、チョキに勝った回数を $p$ 、チョキ以外に勝った回数を $q$ と置きます。このとき、操作の合計回数は $3p+6q$ となります。

チョキに $p$ 回、チョキ以外に $q$ 回勝つような手の出し方を $f(p, q)$ を考えます。チョキの数 $C$ から $p$ 個選びそれらに勝ち，残り $C-p$ 個に対してはあいこもしくは負けになるように手を出せばチョキに $p$ 回勝つことが出来ます。チョキ以外に対しても同様に考えると、 $f(p, q)$ は以下のようになります。

$f(p,q) = \begin{eqnarray*} && {}_C C _p2^{C-p}\times{}_{N-C} C _q2^{N-C-q} \end{eqnarray*}$

座標 $X$ に移動するための条件は次のとおりです。

$3 p + 6 q \geq X$
$(3p + 6q) \bmod 2 = X \bmod 2$

２つめの条件について、 $q$ は影響を及ぼさないので、 $p$ を決め打ちします。このとき、１つめの条件より、 $q\geq (X - 3 * p) / 6$ を満たすような $q$ について、 $f(p, q)$ を足し合わせれば各 $p$ について、 $X$ まで移動する手の出し方が何通りあるかを求められます。

事前に $f(p,q)$ の累積和を計算しておけば、充分高速に計算可能です。