One may instantly come up with a naive \(\mathrm{O}(N^2)\) DP (Dynamic Programming) solution and try to optimize it, but it seems difficult. (This approach is effective together with a divide-and-conquer trick, but we do not mention it here.) Instead, we try to rephrase the problem.

Specifically, we rephrase the problem as follows. (From now on, we consider this version.)

• There is an \(N \times N\) grid.
• \((a_1, b_1), \dots, (a_M, b_M)\) are wall squares.
• Put new wall squares on \((1, 3), (2, 3), (3, 5), (4, 5), \dots, (n, \left\lceil \frac{n}{2} \right \rceil \times 2 + 1), \dots, (N-2, N-1)\).
• How many shortest paths from \((1, 1)\) to \((N, N)\) are there, without passing through wall squares?

Once interpreted like this, one can derive an \(\mathrm{O}((N + M)^2)\) solution using inclusion-exclusion principle, which is also famous in EDPC Y: Grid 2.
We briefly describe this solution. First, we forget that stepping on a wall square is prohibited. Let \(S\) be the set of wall squares. For a set of wall squares \(S\), we define \(f(S)\) as follows:

• \(f(S)\) \(:=\) (the number of shortest paths from \((1, 1)\) to \((N, N)\) that passes through at least the wall squares in \(S\)).

Then by inclusion-exclusion principle, the sought count \(X\) is represented as

\[X = \sum_{T \subseteq S} (-1)^{|T|} f(T),\]

which can be evaluated using DP. Let \(w_1, w_2, \dots, w_{|S|}\) be the wall squares sorted in topological order. Also, define \(f_i(S), \mathrm{dp}_i\), and \(g(a, b)\) as follows:

• \(f_i(S)\) \(:=\) (the number of shortest paths from \((1, 1)\) to \(w_i\) that passes through at least the wall squares in \(\lbrace w_1, w_2, \dots, w_{i-1} \rbrace\) that are contained in in \(S\))
• \(\mathrm{dp}_i\) \(:=\) \(\displaystyle \sum_{T \subseteq \lbrace w_1, w_2, \dots, w_{i-1} \rbrace} f_i(T) (-1)^{|T| + 1}\)
• \(g(a, b)\) \(:=\) : the number of shortest paths from \(a\) to \(b\)

Then, considering the last wall square to step on, \(\mathrm{dp}_i\) can be represented by \(\mathrm{dp}_j\) as follows:

\[\mathrm{dp}_i = - g((1,1), w_i) - \sum_{j=1}^{i-1} g(w_j, w_i) \times \mathrm{dp}_j.\]

By the same observation, the sought count \(X\) can be represented as follows:

\[X = g((1,1),(N,N)) + \sum_{i=1}^{|S|} g(w_i, (N,N)) \times \mathrm{dp}_j\]

For simplicity, we define \(w_0 = (1, 1)\) and \(w_{|S| + 1} = (N, N)\) to extend the DP to the range \(0 \leq i \leq |S| + 1\) in order to simplify the transition:

\[\mathrm{dp}_0 = 1,\]

\[\mathrm{dp}_i = -\sum_{j=0}^{i-1} g(w_j, w_i) \times \mathrm{dp}_j,\]

\[X = -\mathrm{dp}_{|S| + 1}.\]

By the DP above, the problem can be solved in a total of \(\mathrm{O}(|S|^2 + N) = \mathrm{O}((N+M)^2)\) time.

Now we try to optimize this DP.
There are two kinds of wall square: the original ones and the newly added ones, which we will distinguish. There are at most \(M\) \((\leq 50)\) original wall squares, whose contribution to the complexity is no more than \(\mathrm{O}(M(N+M))\), allowing naively calculating the transitions arising from the original wall squares. On the other hand, transitions from a new wall square to an original one costs a total of \(\mathrm{O}(N^2)\) time, which we want to optimize.

Among the new wall squares, let

• \(w_{n, 1}\) denote the wall square added at \((2n - 1, 2n + 1)\), and
• \(w_{n, 2}\) denote the wall square added at \((2n, 2n + 1)\).

The new wall squares in topological order are \(w_{1,1}, w_{1,2}, \dots, w_{N/2-1, 1}, w_{N/2-1,2}\). Then \(w_{i,\ast}\) and \(w_{j,\ast}\) \((i \gt j)\) satisfy

\[ \begin{aligned} g(w_{j,2}, w_{i,1}) &= \binom{4(i-j)-1}{2(i-j)},\\ g(w_{j,1}, w_{i,1}) = g(w_{j,2}, w_{i,2}) &= \binom{4(i-j)}{2(i-j)},\\ g(w_{j,1}, w_{w_2}) &= \binom{4(i-j)+1}{2(i-j)}, \end{aligned} \]

whose right hand sides can all be represented as an expression of \((i - j)\).

Denoting by \(\mathrm{dp}_{i,\ast}\) the DP table regarding \(w_{i,\ast}\), the contributions of \(\mathrm{dp}_{j, \ast}\) onto \(\mathrm{dp}_{i,\ast}\) \((i \gt j)\) are

\[\mathrm{dp}_{i,1} \gets \mathrm{dp}_{i,1} -\sum_{j \lt i} \left(\mathrm{dp}_{j,1} \times g(w_{j,1}, w_{i, 1}) + \mathrm{dp}_{j, 2} \times g(w_{j,2}, w_{i,1})\right),\]

\[\mathrm{dp}_{i,2} \gets\mathrm{dp}_{i,2}- \sum_{j \lt i} \left(\mathrm{dp}_{j,1} \times g(w_{j,1}, w_{i, 2}) + \mathrm{dp}_{j, 2} \times g(w_{j,2}, w_{i,2})\right),\]

where \(g(w_{j,\ast}, w_{i, \ast})\) are all a function of \((i-j)\), so the right hand sides are in the form of convolution. This allows the divide-and-conquer FFT (Fast Fourier Transform). (For the divide-and-conquer FFT, please refer to the editorial of ABC213 Ex.)

Therefore, the transitions between newly added wall squares can be processed in a total of \(\mathrm{O}(N \log^2 N)\) time using the divide-and-conquer FFT. Hence the problem has been solved in a total of \(\mathrm{O}(N \log^2 N + M(N + M))\) time, which is fast enough.

• Sample code, C++

Bonus: the intended solution uses the property that the grid is stair-shaped, but in fact the grid can be in any form (even an oval or a star), the problem can be solved with the same complexity \(\mathrm{O}(N \log^2 N + M(N + M))\) as long as the grid has no hole. (We assume that the grid can be represented by about \(\mathrm{O}(N)\) information.) Think of it if you are interested. (Reference blog (Japanese))