問題: atcoder.jp
解説やユーザー解説と考察過程が違ったので簡単にメモ書きを残しておきます．
$f_k(n,r,c)$ を $n \times n$ のマス目の分割であって，マス $(r,c)$ がレベル $k$ の L 型に含まれるようなものの個数とします（範囲外の部分は $0$ としておきます）．$k \lt n$ のときはレベル $n$ の L 型の置き方を場合分けすることで
$$f_k(n,a,b) = f_k(n-1,a,b)+f_k(n-1,a-1,b)+f_k(n-1,a,b-1)+f_k(n-1,a-1,b-1)$$
が成り立ちます．これを配る DP の遷移のように表現すると
$$f_k(n+1,r,c) += f_k(n,r,c)$$ $$f_k(n+1,r+1,c) += f_k(n,r,c)$$ $$f_k(n+1,r,c+1) += f_k(n,r,c)$$ $$f_k(n+1,r+1,c+1) += f_k(n,r,c)$$
となります．また，base-case の $f_k(k,r,c)$ は次のようになります．ただし $C_k = \lbrace (1,1),(1,k),(k,1),(k,k) \rbrace$ です．
$$ f_k(k,r,c) = \begin{cases} 1 & (k=1) \\ 3\cdot 4^{k-2} & (k > 1 \land (r,c) \in C_k) \\ 2\cdot 4^{k-2} & (k > 1 \land (r \in \lbrace 1,k \rbrace \lor c \in \lbrace 1,k \rbrace) \land (r,c) \notin C_k) \\ 0 & (otherwise) \end{cases} $$
さらに，遷移が線形なので $g(n,r,c) = f_{1}(n + 1, r + 1, c + 1)$ として $$\begin{align} f_k(n,r,c) &= \displaystyle\sum_{1 \leq i,j \leq k}g(n - k, r-i,c-j)f_k(k,i,j) \\ &= \displaystyle\sum_{(i,j) \in C_k}g(n - k, r - i, c - j) \cdot 3\cdot 4^{k - 2} \\ &+ \displaystyle\sum_{i=2}^{k - 1}g(n - k, r - i, c - 1) \cdot 2\cdot 4^{k - 2} \\ &+ \displaystyle\sum_{i=2}^{k - 1}g(n - k, r - i, c - k) \cdot 2\cdot 4^{k - 2} \\ &+ \displaystyle\sum_{j=2}^{k - 1}g(n - k, r - 1, c - j) \cdot 2\cdot 4^{k - 2} \\ &+ \displaystyle\sum_{j=2}^{k - 1}g(n - k, r - k, c - j) \cdot 2\cdot 4^{k - 2} \end{align}$$
が成り立ちます（各 base-case がマス $(r,c)$ に与える寄与に注目しています）．よって $g(n,r,c)$ がある程度閉じた式になって欲しさがあります．
結論から述べると $g(n,r,c)=\displaystyle\binom{n}{r}\binom{n}{c}$ です（これは実験により容易にエスパーできますし，私もコンテスト中はそうしました）．証明は
$$\begin{align} & \displaystyle\binom{n}{r}\binom{n}{c}+\binom{n}{r+1}\binom{n}{c}+\binom{n}{r}\binom{n}{c+1}+\binom{n}{r+1}\binom{n}{c+1} \\ &= \displaystyle\left(\binom{n}{r} + \binom{n}{r+1}\right)\left(\binom{n}{c} + \binom{n}{c+1}\right) \\ &= \displaystyle\binom{n+1}{r+1}\binom{n+1}{c+1} \end{align}$$
から帰納法が回ります． これを先ほどの式に代入して整理すると
$$\begin{align} f_k(n,r,c) &= \displaystyle\sum_{(i,j) \in C_k}f_1(n - k,r - i,c - j) \cdot 3\cdot 4^{k - 2} \\ &+ 2 \cdot 4^{k - 2} \displaystyle\binom{n -k}{c - 1}\sum_{i=2}^{k - 1}\binom{n - k}{r - i} \\ &+ 2 \cdot 4^{k - 2} \displaystyle\binom{n -k}{c - k}\sum_{i=2}^{k - 1}\binom{n - k}{r - i} \\ &+ 2 \cdot 4^{k - 2} \displaystyle\binom{n -k}{r - 1}\sum_{j=2}^{k - 1}\binom{n - k}{c - j} \\ &+ 2 \cdot 4^{k - 2} \displaystyle\binom{n -k}{r - k}\sum_{j=2}^{k - 1}\binom{n - k}{c - j} \end{align}$$
を得ます．結局 $\displaystyle\sum_{i=2}^{k - 1}\binom{n-k}{a-i}$ が $k=2,3,\dots,N$ に対して列挙できれば良く，これは $A_{k} = \displaystyle\sum_{i=2}^{k - 1}\binom{n-k}{a-i}$ とおけば
$$\begin{align} A_{k} &= \displaystyle\sum_{i=2}^{k - 1}\binom{n - k}{a - i} \\ &= \displaystyle\sum_{i=2}^{k - 1}\left(\binom{n - k - 1}{a - i}+\binom{n - k - 1}{a - i - 1}\right) \\ &= \left(A_{k+1} - \binom{n - k - 1}{a - 2}\right) + \left(A_{k+1} - \binom{n - k - 1}{a - k}\right) \end{align}$$
なので $A_{k+1}$ から $A_{k}$ が $O(1)$ で計算できます．以上を適切に実装すれば $O(N + Q)$ で解くことができます．
実装例 ($O(N+Q\log N)$): https://atcoder.jp/contests/arc190/submissions/61684007
