愚直な DP を考えてみる \(dp[i][j][k]=i\) 以上の値を処理した段階で，黒板に書かれた値の偶奇が \(j\) で，確定しているスコアが \(k\) になる方法の数．

\(dp[i][j](x)=\sum_{k} dp[i][j][k] x^k\) とおいて，遷移を考えると，以下の行列の掛け算がしたいことになる．

\[ \frac{1}{v+1} \begin{bmatrix} v & 1 \\ x & vx \end{bmatrix} \]

これを \(v=R,\cdots,L\) の順にかけて得られる行列 \(M_{R,L}\) を考える． なんとこれがきれいな形になる．

\(M_{R,L}\) の各成分 \((i,j)\) は，定数次数の多項式 \(a_{i,j}(x),b_{i,j}(x)\) を用いて，\(M_{R,L}[i][j]=(a_{i,j}(x)+x^{R-L}b_{i,j}(x))/(1-x)^2\) と書くことができる．

TODO: 閉じた式をちゃんと書いておく

これは気合で帰納法を回して証明することも可能だが，別の理解もある．

数直線上の座標 \(0,\cdots,L-1\) に旗を立てている状態を考える． あなたは今，座標 \(0\) or \(L-1\) からスタートし，以下の操作を繰り返す．

• 確率 \(1/2\) で座標 \(+1\) し，確率 \(1/2\) で座標 \(-1\) する． 旗の立っていない座標に到達したら，そこに新しく旗を立てる．

旗が合計で \(R+1\) 個立った瞬間に操作を終了する． 新しく立てた旗の本数は \(R-L+1\) 本だが，この内何本を右で立てたかを考える． この本数 \(k\) に \(x^k\) を対応させて，確率を計算する DP を考えると，上述の行列が登場する．

そして，この問題を行列DPを経由せずに直接解くことで，\(k\) の値が \(0\) や \(R-L+1\) でないときは値が \(k\) に対して線型であることがわかる．

\(M_{R,L}\) がいい感じに書けた． あとはこれを利用して全体のDPを行えばよい． DPの値を \(f(x) \times x^s / (1-x)^r\) という形で持って計算すれば良い．

計算量は全体で \(O(4^K\mathrm{poly}(K))\)

回答例(C++)