[AtCoder] E – Placing Squares(AGC 013)

スポンサーリンク

概要

問題文 →
自分の提出 →
公式解説 →

障害物がない場合、形式的べき級数であっという間に立式、漸化式の導出ができます。あとは障害物の補正をするだけです。

無限個の項の計算全体を、有理式の形(有限個の数の組)で持てることを活かして更新していきます。

以下の記事が前提となります。

解法

印が存在しない場合の計算

ちょうど $n$ マスに正方形を置く場合の美しさの総和を $a_n$ として、その母関数を $A$ とします。$F = x + 4x^2 + 9x^3 + 16x^4 + \cdots$ として、 $A = \sum_{i=0}^{\infty} F^i$ が成り立つのでした(記事(1))。等比数列の和の計算より、$A = \frac{1}{1-F}$ です。

これは有理式です。まず、$F$ は数列 $\{n^2\}$ の母関数ですから、分母 $(1-x)^3$ を持つ有理式 $\frac{p+qx+rx^2}{(1-x)^3}$ と等しいです(記事(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$ を求めます。次の手順をとればよいです。

(1)数列 $b_m = a_{n+m}$ の母関数 $B$ を求める($n$ マス目以降の情報だけ抜き出す)。
(2)$B\leftarrow B – b_0A$ とする($n$ マス目を通る場合を除外)。

(1)は、$A = \frac{P_A}{Q}$ としたとき、$x^{-n}P\pmod{Q}$ の計算と等価で(記事(3)の、線形漸化式の高速計算の項)、$O(\log n)$ 解の多項式計算により $B$ を有理式 $\frac{P_B}{Q}$ の形で計算できます。(2)も $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}$ に対してクエリの回数が大きい場合には、計算量の改善が期待できます。

感想

ほら簡単でしょ!というつもり解説を書いたのだが、説明が微妙に下手で難しく見える気がする。

タイトルとURLをコピーしました