概要
障害物がない場合、形式的べき級数であっという間に立式、漸化式の導出ができます。あとは障害物の補正をするだけです。
無限個の項の計算全体を、有理式の形（有限個の数の組）で持てることを活かして更新していきます。
以下の記事が前提となります。
解法
印が存在しない場合の計算
ちょうど $n$ マスに正方形を置く場合の美しさの総和を $a_n$ として、その母関数を $A$ とします。$F = x + 4x^2 + 9x^3 + 16x^4 + \cdots$ として、 $A = \sum_{i=0}^{\infty} F^i$ が成り立つのでした（記事（１））。等比数列の和の計算より、$A = \frac{1}{1-F}$ です。
これは有理式です。まず、$F$ は数列 $\{n^2\}$ の母関数ですから、分母 $(1-x)^3$ を持つ有理式 $\frac{p+qx+rx^2}{(1-x)^3}$ と等しいです（記事（３））。$(1-x)^3F = (1-3x+3x^2-\cdots)(x+4x^2+\cdots)$ を$2$次の項まで計算することで、 $F=\frac{x+x^2}{(1-x)^3}$ が分かります。
あるいは、$\frac{1}{1-x} = 1 + x + x^2 + x^3 + \cdots$ から始めて、「微分して $x$ 倍」を $2$ 回繰り返してもよいでしょう。
$F$ が有理式なので、$A = \frac{1}{1-F}$ も有理式です。$F$ の表示を代入すると、\[ A = 1 + \frac{x + x^2}{1-4x+2x^2-x^3}\] が得られます。
余分な $1$ は、定数項だけ規則から外れていることを示しています。便宜上 $a_0 = 0$ と定義することにして、以下では $A = \frac{x + x^2}{1-4x+2x^2-x^3}$ と書きます（あまり本質的ではないです）。
唯一の印がある場合
禁止地点の影響を除外していきましょう。部分集合の個数が多くて包除原理もつらそうなので、ある地点に対して、そこが最初の反例となるようなものを除外していきます。
簡単のため、$n$ に唯一の印がある場合を考えましょう。$n$ を通る場合の数値を $A$ から引きます。ちょうど $n$ を通る場合の数列全体への寄与は、$a_nx^nA$ と表すことができます。よって、$n$ に唯一の印がある場合の母関数は、$A – a_nx^nA$ となります。
これだと係数の規則が途中から切り替わるのが邪魔いので、切り替わった後の規則だけ持つことにします。 禁止地点の影響も加味した上で、「ちょうど $n+m$ マスを埋める場合の美しさの総和」を $x^m$ に持つように、新しい母関数 $B$ を求めます。次の手順をとればよいです。
（１）数列 $b_m = a_{n+m}$ の母関数 $B$ を求める（$n$ マス目以降の情報だけ抜き出す）。
（２）$B\leftarrow B – b_0A$ とする（$n$ マス目を通る場合を除外）。
（１）は、$A = \frac{P_A}{Q}$ としたとき、$x^{-n}P\pmod{Q}$ の計算と等価で（記事（３）の、線形漸化式の高速計算の項）、$O(\log n)$ 解の多項式計算により $B$ を有理式 $\frac{P_B}{Q}$ の形で計算できます。（２）も $A$ の有理式表示を使えば簡単です。
解法まとめ
便宜上、唯一の印があるとしましたが、たくさんあるときも同じです。左から順番に処理します。
- $A = \frac{x+x^2}{1-4x+2x^2-x^3} = \frac{P}{Q}$ とおく。
- $B_i = \frac{P_i}{Q}$ が、座標 $x_i$ の印まで考慮したときの、$x_i$ 以降の母関数とする。つまり、座標 $x_i+n$ ちょうどまで埋めるときの美しさの総和が $[x^n]B_i$ になるようにする。
- 便宜上、$P_0 = P$, $x_0 = 0$, $B_0 = A$ から始める。
- $P_i$ から $P_{i+1}$ を計算する。まず、$n = x_{i+1} – x_i$ として、$P_{i+1} = x^{-n}P_i\pmod{Q}$ を計算する。これは、数列のシフトに相当する。
- $P_{i+1}$ の定数項を $c$ として、$P_{i+1} \leftarrow P_{i+1} – cP = P_{i+1} – c(x+x^2)$ とする。これで、$x_i$ ちょうどを通るパターンを除外している。
常に $3$ 次多項式 $P_i$ だけを更新していくことで、計算結果全体を管理して、取得・更新を行っています。多項式がデータ構造のようにも見えてきますね（特定の線形漸化式を満たす数列を管理するデータ構造？）。
参考
計算の最も重い部分は、$x^{-n}\pmod{Q}$ を何度も計算するところです。
同じ値のべき乗 $a^n$ を何度も計算する場合には、事前計算と平方分割が利用できます。つまり、$0\leq n< m$ に対する $a^n$ と $a^{nm}$ を事前計算（$1$ 件あたり 1 回の乗算）しておけば、クエリ 1件あたり1回の乗算で、$a^n$ を取得できます（$n< m^2$）。$\sqrt{n}$ に対してクエリの回数が大きい場合には、計算量の改善が期待できます。
感想
ほら簡単でしょ！というつもり解説を書いたのだが、説明が微妙に下手で難しく見える気がする。
