Mogu Mogu 2 Returns

解説

$(1,1)$ から $(H,W)$ までの経路は $\displaystyle \frac{(H+W)!}{H!W!}$ 通りより、これらを全探索するのは現実的ではありません。また、今回は $HW \leq 10^{12}$ より、DPを考えるのも難しそうです。

では、どうすれば良いのでしょうか?おにぎりに注目してみます。 ここで、全経路におけるおにぎりの数の総和は、すべてのおにぎりにおけるそのおにぎりを通るような経路の数の総和と言い換えることができます。

では、おにぎり $i(1 \leq i \leq N)$ について、このおにぎりを通るような経路の数はどうなるでしょうか。これは、$(1,1)$ から $(r_i,c_i)$ までの経路の通り数と、$(r_i,c_i)$ から $(H,W)$ までの経路の通り数の積に等しく、

$\displaystyle \frac{(r_i-1+c_i-1)!}{(r_i-1)!(c_i-1)!} \times \frac{(H-r_i+W-c_i)!}{(H-r_i)!(W-c_i)!}$ です。(右矢印と下矢印の並べ方の総数)

よって、$X!(0 \leq X \leq H+W)$ の値を $mod 998244353$ で前計算しておくことで各おにぎりについてそのおにぎりを通るような経路の数を求めることができ、これらの総和を求めて出力すれば良いです。時間計算量は適切な逆元計算のもと $O(H+W+N)$ となり、実行時間制限に間に合います。