Hints → https://atcoder.jp/contests/arc190/editorial/11918

In the problem statement, a “path” is defined specifically as one starting at \((1,1)\) and ending at \((H,W)\). However, in this editorial we use the term “path” and the notation \(f(P)\) in the same way for any pair of endpoints.

[1] Approach

We will prepare two DP tables:

• \(\mathrm{dp}_1[h][w]\): the sum of \(f(P)\) over all paths \(P\) from \((1,1)\) to \((h,w)\).
• \(\mathrm{dp}_2[h][w]\): the sum of \(f(P)\) over all paths \(P\) from \((h,w)\) to \((H,W)\).

We keep the state where the following values are correctly computed when Takahashi is at cell \((a,b)\):

• \(\mathrm{dp}_1[h][w]\) for \(1 \le h \le a\)
• \(\mathrm{dp}_2[h][w]\) for \(a \le h \le H\)

This can be achieved by redoing the calculation for row \(a\) in each query, which takes \(O(W)\) time per query.

If these DP tables are maintained, then the difference needed for the answer can be obtained in \(O(1)\) time. Alternatively, one could do a recalculation in \(O(W)\) time using, for example, \(\mathrm{ANS}=\sum_{w} \mathrm{dp}_1[a][w] \mathrm{dp}_2[a+1][w]\) when moving from row \(a\) to row \(a+1\).

Hence, this problem can be solved in \(O(HW + WQ)\) time. If \(H \le W\), one can swap rows and columns and apply the same reasoning, achieving \(O(HW + \min(H,W) Q)\).

• Sample Solution: https://atcoder.jp/contests/arc190/submissions/61518720