それぞれの書き込み方に対してロボットが \((1,1)\) から \((H,W)\) へ移動する経路の個数を求め、その総和を取った値というのは、ロボットが \((1,1)\) から \((H,W)\) へ移動するような経路それぞれに対してそのような移動が可能な書き込み方の個数を求め、その総和を取った値と等しいです。

前者の代わりに後者を求めることを考えます。 空白マスは X と書かれたマスと同様に右、下のどちらにも移動可能ということにします。

\(\mathrm{dp}(h,w,k)\) をロボットが \((1,1)\) から出発して空白マスを \(k\) 箇所通って \((h,w)\) に到達するような経路の個数、とします。通った空白マスは X か(R か D の移動方向と対応する文字)を書き込む必要があり、その他のマスにはどの文字を書いても構いません。よって、\(\sum_{1 \leq k \leq H+W} \mathrm{dp}(H,W,k) 2^{k}3^{HW-K-k}\) が求める答えで、これは \(O(HW(H+W))\) で求められます。

ここで、\(k\) を状態に持つ代わりに遷移の際に \(\frac{2}{3}\) をかけることにして最後に \(3^{HW-K}\) をかけることにすれば \(O(HW)\) で求めることができ \(H,W \leq 5000\) より十分高速です。