We want to tile a \(3\times 3\times n\) tower with \(2\times 1\times 1\) blocks, allowing all axis-aligned orientations, and count the number of valid towers modulo
$$M=100000007.$$
Let \(f(n)\) be that count. The challenge is that the requested index is not merely large: it is
$$N=10^{10000}.$$
So even a fast layer-by-layer dynamic program is still hopeless unless we compress the sequence very aggressively.
1) A parity observation.
The tower volume is \(9n\). Each block covers 2 unit cubes. Therefore \(f(n)=0\) whenever \(9n\) is odd, i.e. whenever \(n\) is odd. This is not enough to solve the problem, but it is a good first sanity check on the sequence.
2) Slice the tower by layers.
Process the tower one \(3\times 3\) layer at a time. A single layer has 9 cells, so we encode a layer state by a 9-bit mask
$$s\in[0,2^9).$$
A bit of \(s\) is 1 if that cell is already occupied by a domino that started in the previous layer and sticks into the current one. Since there are 9 cells, the total number of masks is
$$2^9=512.$$
3) What one transition means.
Fix an incoming mask \(s\). We must finish filling the current \(3\times 3\) layer completely. While doing that, a domino can be placed in exactly three ways:
1) entirely inside the current layer, horizontally along columns,
2) entirely inside the current layer, vertically along rows,
3) across the layer boundary, meaning one cube is in the current layer and the other cube will occupy the same cell in the next layer.
The third type creates a 1 in the outgoing mask \(t\).
4) DFS generates the transfer counts.
The code uses a depth-first search on the current layer. At each step it picks the first free cell and branches over the legal placements listed above. When the layer becomes fully covered, we have produced exactly one transition
$$s\to t.$$
Let \(T_{s,t}\) be the number of ways this can happen.
Because the layer is only \(3\times 3\), this DFS is finite and can be done once for all 512 incoming masks.
5) Transfer-matrix dynamic programming.
Let \(v_k[s]\) be the number of ways to build the first \(k\) layers and finish with outgoing mask \(s\). Then
$$v_{k+1}[t]=\sum_{s=0}^{511} v_k[s]\,T_{s,t}\pmod M.$$
The initial condition is
$$v_0[0]=1,\qquad v_0[s]=0\ \text{for }s\ne 0,$$
because before building anything there is no pending occupancy from a previous layer.
The quantity we actually want is the fully closed tower count
$$f(k)=v_k[0],$$
since at the top of a valid tower no domino may stick out into an imaginary next layer.
6) Why a linear recurrence must exist.
The vector \(v_k\) lives in a 512-dimensional vector space over \(\mathbb Z_M\), and it evolves by multiplication with the same fixed \(512\times 512\) matrix \(T\). Therefore the scalar sequence \(f(k)=v_k[0]\) is automatically a linear recurrence sequence. In principle its recurrence length is at most 512, although the minimal recurrence can be smaller.
7) Recover the minimal recurrence with Berlekamp-Massey.
The program generates the first 1301 terms
$$f(0),f(1),\dots,f(1300)$$
using the 512-state DP. Then Berlekamp-Massey reconstructs the shortest recurrence
$$f(n)=\sum_{j=1}^{L} c_j f(n-j)\pmod M.$$
This is the crucial compression step: after that, we never need the 512-state DP again.
8) Small checkpoints.
The C++ code validates the recovered recurrence against known terms:
$$f(2)=229,\qquad f(4)=117805,\qquad f(10)=96149360,$$
and also much later values
$$f(10^3)=24806056,\qquad f(10^6)=30808124.$$
These checkpoints are important: they verify both the transfer-DP part and the recurrence-evaluation part.
9) Why giant matrix exponentiation is replaced by Kitamasa-style polynomial arithmetic.
Once we know the recurrence, computing \(f(N)\) is equivalent to reducing the monomial \(x^N\) modulo the characteristic polynomial
$$P(x)=x^L-\sum_{j=1}^{L} c_j x^{L-j}.$$
If
$$x^N \equiv a_0+a_1x+\cdots+a_{L-1}x^{L-1}\pmod{P(x)},$$
then
$$f(N)=a_0f(0)+a_1f(1)+\cdots+a_{L-1}f(L-1)\pmod M.$$
The code computes these coefficients by repeated squaring and polynomial combination, which is the standard Kitamasa viewpoint.
10) Handling \(N=10^{10000}\).
The exponent does not fit into any machine integer type. So the code stores it as the decimal string
$$1000\ldots 0$$
with 10000 zeros, repeatedly divides that string by 2, and records the remainders. This produces the bits of \(N\) in least-significant-bit-first order, which is exactly what binary exponentiation needs.
1) Precompute all layer transitions \(T_{s,t}\) by DFS over a \(3\times 3\) slice.
2) Run the 512-state DP long enough to obtain a prefix of \(f(n)\).
3) Apply Berlekamp-Massey to extract the minimal linear recurrence.
4) Validate the recurrence on additional known terms.
5) Convert \(N=10^{10000}\) from decimal to binary bits.
6) Evaluate \(f(N)\) modulo \(M\) using Kitamasa-style polynomial squaring.
The transition precomputation is finite and bounded by the 512 masks. The prefix DP is also small. If the minimal recurrence length is \(L\), the final evaluation costs roughly
$$O(L^2\log N)$$
modular operations and
$$O(L)$$
memory. That is what makes the astronomical index \(10^{10000}\) manageable.
The code checks
$$f(2)=229,\quad f(4)=117805,\quad f(10)=96149360,\quad f(10^3)=24806056,\quad f(10^6)=30808124.$$
For the required exponent
$$N=10^{10000},$$
the final answer is
$$f(N)=96972774.$$
Ein \(3\times3\times n\)-Turm soll mit \(2\times1\times1\)-Bloecken in beliebiger achsenparalleler Orientierung gepflastert werden. Die Anzahl der Moeglichkeiten sei \(f(n)\), gerechnet modulo
$$100000007.$$
Gesucht ist nicht ein moderates \(n\), sondern
$$N=10^{10000}.$$
1) Paritaet.
Das Volumen des Turms ist \(9n\), jeder Block bedeckt 2 Einheitswuerfel. Also ist \(f(n)=0\) fuer ungerades \(n\). Das ist nur eine erste Kontrolle, aber eine nuetzliche.
2) Schichtweise Beschreibung.
Eine Schicht ist \(3\times3\) und besitzt 9 Felder. Ein Zustand ist daher eine 9-Bit-Maske
$$s\in[0,2^9),$$
deren Einsen die Felder markieren, die bereits von Dominosteinen aus der vorherigen Schicht belegt sind.
3) Uebergaenge zwischen Masken.
Bei festem Eingangs-Zustand \(s\) muss die aktuelle Schicht vollstaendig gefuellt werden. Ein Stein kann dabei
1) innerhalb der Schicht entlang der Spalten liegen,
2) innerhalb der Schicht entlang der Zeilen liegen,
3) ueber die Schichtgrenze in die naechste Ebene ragen.
Der dritte Fall setzt das entsprechende Bit in der Ausgangsmaske \(t\).
4) DFS liefert die Transferzahlen.
Der Code nimmt immer das erste freie Feld und probiert rekursiv alle legalen Placements. Ist die Schicht komplett belegt, wurde genau ein Uebergang
$$s\to t$$
erzeugt. Dessen Anzahl heisst \(T_{s,t}\).
5) Transfer-DP.
Mit \(v_k[s]\) als Anzahl der Bauten nach \(k\) Schichten mit Ausgabemaske \(s\) gilt
$$v_{k+1}[t]=\sum_{s=0}^{511} v_k[s]\,T_{s,t}\pmod M.$$
Anfangs ist
$$v_0[0]=1,$$
alle anderen Komponenten sind 0. Die gesuchte Folge ist
$$f(k)=v_k[0],$$
denn ein gueltiger Turm darf oben nicht in eine fiktive naechste Schicht hineinragen.
6) Warum eine lineare Rekurrenz existiert.
Der Vektor \(v_k\) lebt in einem 512-dimensionalen Raum und wird immer mit derselben Matrix multipliziert. Daher ist jede feste Komponente, insbesondere \(f(k)\), eine lineare Rekurrenzfolge. Die minimale Rekurrenz hat Laenge hoechstens 512.
7) Berlekamp-Massey.
Der Code erzeugt die ersten 1301 Werte von \(f(n)\) und rekonstruiert daraus mit Berlekamp-Massey die kuerzeste Rekurrenz
$$f(n)=\sum_{j=1}^{L} c_j f(n-j)\pmod M.$$
8) Checkpoints.
Geprueft werden
$$f(2)=229,\qquad f(4)=117805,\qquad f(10)=96149360,$$
sowie
$$f(10^3)=24806056,\qquad f(10^6)=30808124.$$
9) Kitamasa-Sichtweise.
Kennt man die Rekurrenz, so entspricht die Berechnung von \(f(N)\) der Reduktion von
$$x^N$$
modulo des charakteristischen Polynoms
$$x^L-\sum_{j=1}^{L}c_jx^{L-j}.$$
Die restlichen Koeffizienten kombinieren dann die Startwerte \(f(0),\dots,f(L-1)\).
10) Der Exponent \(10^{10000}\).
Da \(N\) in keinen Integer passt, wird seine Dezimaldarstellung wiederholt durch 2 geteilt. Die Reste liefern direkt die Bitsaetze fuer binaeres Potenzieren.
1) Alle Uebergaenge \(T_{s,t}\) per DFS vorrechnen.
2) Genug Anfangsglieder von \(f(n)\) mit der 512-Zustands-DP erzeugen.
3) Berlekamp-Massey anwenden.
4) Die Rekurrenz mit Checkpoints validieren.
5) \(N=10^{10000}\) als Dezimalstring in Bits zerlegen.
6) \(f(N)\) mit Kitamasa-artiger Polynomkombination berechnen.
Der Zustandsraum ist fest auf 512 Masken begrenzt. Die Endauswertung kostet etwa
$$O(L^2\log N)$$
Zeit und
$$O(L)$$
Speicher.
Die validierten Werte sind
$$f(2)=229,\quad f(4)=117805,\quad f(10)=96149360,\quad f(10^3)=24806056,\quad f(10^6)=30808124.$$
Fuer
$$N=10^{10000}$$
erhaelt man
$$f(N)=96972774.$$
\(3\times3\times n\) boyutlu bir kuleyi, eksenlere paralel her yonde durabilen \(2\times1\times1\) bloklarla doseme sayisini ariyoruz. Bu sayi \(f(n)\) olsun ve her sey
$$100000007$$
modunda hesaplansin. Sorun, istenen indeksin
$$N=10^{10000}$$
olmasi; yani katman katman DP bile tek basina yetmiyor.
1) Parite gozlemi.
Kulenin hacmi \(9n\)'dir. Her blok 2 hucre kaplar. Bu yuzden \(n\) tek ise doseme imkansizdir ve
$$f(n)=0$$
olur. Bu yalnizca ilk kontrol noktasi ama dizinin mantigini dogrulamak icin faydalidir.
2) Katmanlara ayir.
Kuleyi birer \(3\times3\) katman olarak isliyoruz. Bir katmanda 9 hucre vardir; dolayisiyla durumu 9 bitlik bir maske ile tutabiliriz:
$$s\in[0,2^9).$$
Bu maskede 1 olan bitler, onceki katmandan tasan bir blok tarafindan zaten doldurulmus hucreleri gosterir.
3) Tek katmandaki uc yerlestirme tipi.
Sabit bir giris maskesi \(s\) verildiginde mevcut katmani tamamen doldurmamiz gerekir. Bir blok
1) katman icinde yatay,
2) katman icinde dikey,
3) ya da bir hucreyi su anki katmanda, diger hucreyi bir sonraki katmanda olacak sekilde katmanlar arasinda
yerlestirilebilir. Ucuncu tur yerlestirme, cikis maskesi \(t\)'de ilgili biti 1 yapar.
4) DFS ile transfer sayilari.
Kod, o anki katmanda ilk bos hucreyi bulur ve butun yasal yerlestirmeleri dener. Katman tamamen doldugunda tek bir
$$s\to t$$
gecisi uretmis oluruz. Bunun kac farkli sekilde olduguna
$$T_{s,t}$$
diyoruz.
5) Transfer matrisi DP'si.
\(v_k[s]\), ilk \(k\) katmani insa ettikten sonra cikis maskesi \(s\) ile biten yol sayisi olsun. O halde
$$v_{k+1}[t]=\sum_{s=0}^{511} v_k[s]\,T_{s,t}\pmod M.$$
Baslangicta hic tasma olmadigi icin
$$v_0[0]=1,\qquad v_0[s]=0\ (s\ne0).$$
Aradigimiz dizi ise
$$f(k)=v_k[0]$$
cunku gecerli bir kulenin tepesinde bir sonraki katmana sarkan blok kalamaz.
6) Neden lineer rekürans kesin var?
\(v_k\) vektoru 512 boyutlu sabit bir uzayda yasiyor ve her adimda ayni matrisle carpilıyor. Bu nedenle herhangi bir sabit koordinat, ozellikle \(f(k)\), zorunlu olarak lineer rekürans saglar. Minimal rekürans uzunlugu en fazla 512'dir.
7) Berlekamp-Massey ile minimal reküransi cikar.
Kod once
$$f(0),f(1),\dots,f(1300)$$
terimlerini uretir. Sonra Berlekamp-Massey ile en kisa
$$f(n)=\sum_{j=1}^{L} c_j f(n-j)\pmod M$$
reküransi bulur.
8) Checkpoint'ler.
Kod su degerleri dogrular:
$$f(2)=229,\qquad f(4)=117805,\qquad f(10)=96149360,$$
ve daha ileride
$$f(10^3)=24806056,\qquad f(10^6)=30808124.$$
Bunlar hem transfer-DP'nin hem de rekürans degerlemesinin dogru oldugunu test eder.
9) Dev indekste neden Kitamasa kullaniliyor?
Rekürans bulunduktan sonra \(f(N)\) hesaplamak,
$$x^N$$
monomunu karakteristik polinoma gore azaltmaya esdegerdir:
$$x^L-\sum_{j=1}^{L}c_jx^{L-j}.$$
Eger
$$x^N\equiv a_0+a_1x+\cdots+a_{L-1}x^{L-1}$$
ise
$$f(N)=a_0f(0)+a_1f(1)+\cdots+a_{L-1}f(L-1)\pmod M.$$
Kod bunu polinom birlestirme ve karesini alma ile, yani Kitamasa bakis acisiyla yapiyor.
10) \(10^{10000}\) sayisinin bitlerini nasil aliyoruz?
Bu sayi hicbir makine tamsayisina sigmaz. Bu nedenle kod onu ondalik string olarak tutup tekrar tekrar 2'ye boluyor. Her bolmede kalan bit, ikilik gosterimin siradaki bitini verir. Boylece binary exponentiation dogrudan string uzerinden yapilabiliyor.
1) DFS ile tum \(T_{s,t}\) gecislerini onhesapla.
2) 512 durumlu DP ile yeterince uzun bir \(f(n)\) on eki uret.
3) Berlekamp-Massey uygula.
4) Reküransi checkpoint'lerle dogrula.
5) \(N=10^{10000}\) ondalik stringini bitlerine ayir.
6) Kitamasa tarzı polinom degerleme ile \(f(N)\)'i hesapla.
Durum uzayi sabit olarak 512 maskeyle sinirlidir. Son degerleme asamasi yaklasik
$$O(L^2\log N)$$
moduler islem ve
$$O(L)$$
ek bellek ister. Asil dev tasarruf burada gelir.
Kod su degerleri kontrol eder:
$$f(2)=229,\quad f(4)=117805,\quad f(10)=96149360,\quad f(10^3)=24806056,\quad f(10^6)=30808124.$$
Ve
$$N=10^{10000}$$
icin nihai cevap
$$f(N)=96972774$$
olur.
Queremos contar los recubrimientos de una torre \(3\times3\times n\) con bloques \(2\times1\times1\), permitiendo todas las orientaciones paralelas a los ejes. Denotemos por \(f(n)\) ese numero, calculado modulo
$$100000007.$$
El indice pedido es gigantesco:
$$N=10^{10000}.$$
1) Paridad.
El volumen total es \(9n\) y cada bloque cubre 2 cubos. Luego si \(n\) es impar no puede existir recubrimiento completo, asi que \(f(n)=0\) para \(n\) impar.
2) Cortar por capas.
Procesamos la torre una capa \(3\times3\) cada vez. Una capa tiene 9 celdas, asi que un estado se codifica con una mascara de 9 bits
$$s\in[0,2^9).$$
Un bit vale 1 si esa celda ya esta ocupada por una pieza que viene de la capa anterior.
3) Que representa una transicion.
Fijado un estado de entrada \(s\), debemos completar la capa actual. Un bloque puede colocarse
1) dentro de la capa en horizontal,
2) dentro de la capa en vertical,
3) cruzando hacia la siguiente capa.
El tercer caso activa el bit correspondiente en la mascara de salida \(t\).
4) DFS para construir \(T_{s,t}\).
El codigo toma siempre la primera celda libre y explora recursivamente todas las colocaciones legales. Cuando la capa queda completamente llena, hemos producido una transicion
$$s\to t.$$
El numero de maneras de hacerlo se denota por \(T_{s,t}\).
5) DP con matriz de transferencia.
Si \(v_k[s]\) es el numero de construcciones de las primeras \(k\) capas que terminan con mascara saliente \(s\), entonces
$$v_{k+1}[t]=\sum_{s=0}^{511} v_k[s]\,T_{s,t}\pmod M.$$
La condicion inicial es
$$v_0[0]=1,$$
y la sucesion buscada es
$$f(k)=v_k[0],$$
porque una torre terminada no puede sobresalir a una capa ficticia superior.
6) Existencia de una recurrencia lineal.
El vector \(v_k\) vive en un espacio de dimension 512 y evoluciona siempre con la misma matriz. Por ello cualquier componente fija, en particular \(f(k)\), satisface una recurrencia lineal. La longitud minima es como mucho 512.
7) Berlekamp-Massey.
El programa genera los primeros 1301 terminos de \(f\) y reconstruye la recurrencia minima
$$f(n)=\sum_{j=1}^{L} c_j f(n-j)\pmod M.$$
8) Checkpoints.
Se verifican
$$f(2)=229,\qquad f(4)=117805,\qquad f(10)=96149360,$$
y tambien
$$f(10^3)=24806056,\qquad f(10^6)=30808124.$$
9) Evaluacion tipo Kitamasa.
Conocida la recurrencia, calcular \(f(N)\) equivale a reducir
$$x^N$$
modulo el polinomio caracteristico
$$x^L-\sum_{j=1}^{L}c_jx^{L-j}.$$
Los coeficientes restantes combinan los valores iniciales \(f(0),\dots,f(L-1)\).
10) Como se maneja \(10^{10000}\).
Ese exponente no cabe en ningun entero normal. El codigo lo guarda como cadena decimal y la va dividiendo entre 2 para extraer sus bits, que luego usa en la exponenciacion binaria de polinomios.
1) Precalcular todas las transiciones \(T_{s,t}\) con DFS.
2) Generar un prefijo de \(f(n)\) con la DP de 512 estados.
3) Aplicar Berlekamp-Massey.
4) Validar la recurrencia.
5) Convertir \(10^{10000}\) de decimal a bits.
6) Calcular \(f(N)\) con combinacion polinomial tipo Kitamasa.
El espacio de estados es fijo: 512 mascaras. La fase final cuesta aproximadamente
$$O(L^2\log N)$$
operaciones modulares y
$$O(L)$$
memoria.
El codigo comprueba
$$f(2)=229,\quad f(4)=117805,\quad f(10)=96149360,\quad f(10^3)=24806056,\quad f(10^6)=30808124.$$
Para
$$N=10^{10000}$$
el resultado final es
$$f(N)=96972774.$$
我们要计算用 \(2\times1\times1\) 小块铺满 \(3\times3\times n\) 塔的方案数，允许所有与坐标轴平行的摆放方向。记该方案数为 \(f(n)\)，并且结果按
$$100000007$$
取模。难点在于题目要的不是普通的 \(n\)，而是
$$N=10^{10000}.$$
1) 体积奇偶性。
塔的体积是 \(9n\)，每块覆盖 2 个单位立方体。所以当 \(n\) 为奇数时，体积是奇数，不可能完全铺满，于是
$$f(n)=0$$
对所有奇数 \(n\) 成立。
2) 按层切开。
每次处理一个 \(3\times3\) 截面。单层有 9 个格子，因此可以用 9 位掩码表示状态：
$$s\in[0,2^9).$$
若第 \(j\) 位为 1，表示这一格已经被上一层伸下来的骨牌占据。
3) 单层里的三种放法。
给定入边状态 \(s\) 后，需要把当前层彻底填满。一个块可以
1) 在当前层内沿列方向放置，
2) 在当前层内沿行方向放置，
3) 跨越层边界，另一半延伸到下一层。
第三种放法会在出边掩码 \(t\) 中把对应位置标记为 1。
4) 用 DFS 生成转移数。
代码总是找到当前层里第一个空格，然后递归尝试所有合法放法。若当前层完全填满，就得到一个转移
$$s\to t.$$
其方案数记为
$$T_{s,t}.$$
5) 转移矩阵 DP。
令 \(v_k[s]\) 表示建好前 \(k\) 层后，留下出边掩码 \(s\) 的方案数，则
$$v_{k+1}[t]=\sum_{s=0}^{511} v_k[s]\,T_{s,t}\pmod M.$$
初值为
$$v_0[0]=1,$$
因为还没开始建塔时不存在“从前一层伸下来”的占据。真正要的序列是
$$f(k)=v_k[0],$$
因为合法塔顶不能再向虚构的下一层伸出骨牌。
6) 为什么一定存在线性递推。
\(v_k\) 始终生活在 512 维向量空间里，并且每一步都乘同一个固定矩阵。因此任何固定坐标，特别是 \(f(k)\)，都必定满足线性递推。最短递推长度最多是 512。
7) Berlekamp-Massey 压缩。
程序先用 512 状态 DP 生成
$$f(0),f(1),\dots,f(1300),$$
再用 Berlekamp-Massey 恢复最短递推
$$f(n)=\sum_{j=1}^{L} c_j f(n-j)\pmod M.$$
8) 校验点。
代码验证
$$f(2)=229,\qquad f(4)=117805,\qquad f(10)=96149360,$$
以及更远处的
$$f(10^3)=24806056,\qquad f(10^6)=30808124.$$
9) 为什么后半段改用 Kitamasa。
得到递推后，计算 \(f(N)\) 等价于把
$$x^N$$
对特征多项式
$$x^L-\sum_{j=1}^{L}c_jx^{L-j}$$
取模。若余式为
$$a_0+a_1x+\cdots+a_{L-1}x^{L-1},$$
那么
$$f(N)=a_0f(0)+a_1f(1)+\cdots+a_{L-1}f(L-1)\pmod M.$$
代码正是用多项式平方与合并来完成这一步，这就是常见的 Kitamasa 思路。
10) \(10^{10000}\) 的处理。
这个指数根本放不进普通整数类型。于是程序把它保存成十进制字符串，不断除以 2，并记录余数，从而直接得到它的二进制位序列。
1) 对 512 个入边掩码全部用 DFS 预计算 \(T_{s,t}\)。
2) 用 512 状态 DP 生成足够长的前缀序列。
3) 运行 Berlekamp-Massey 提取最短递推。
4) 用若干 checkpoint 验证递推。
5) 把 \(10^{10000}\) 从十进制字符串转换成二进制位。
6) 用 Kitamasa 风格的多项式运算求出 \(f(N)\)。
状态空间固定为 512。若最短递推长度为 \(L\)，最终求值大约需要
$$O(L^2\log N)$$
次模运算，以及
$$O(L)$$
额外空间。
代码检查
$$f(2)=229,\quad f(4)=117805,\quad f(10)=96149360,\quad f(10^3)=24806056,\quad f(10^6)=30808124.$$
对于
$$N=10^{10000},$$
最终得到
$$f(N)=96972774.$$
Нужно посчитать число замощений башни \(3\times3\times n\) блоками \(2\times1\times1\), разрешая все ориентации вдоль осей, по модулю
$$100000007.$$
Эта последовательность обозначается \(f(n)\). Требуется значение не для обычного \(n\), а для
$$N=10^{10000}.$$
1) Проверка на чётность.
Объём башни равен \(9n\), а один блок покрывает 2 кубика. Поэтому при нечётном \(n\) замощение невозможно и
$$f(n)=0.$$
2) Послойная модель.
Рассматриваем башню по слоям \(3\times3\). В одном слое 9 клеток, значит состояние кодируется 9-битной маской
$$s\in[0,2^9).$$
Единицы в маске показывают клетки, уже занятые блоками, пришедшими из предыдущего слоя.
3) Три типа размещения блока.
При фиксированной входной маске \(s\) нужно полностью добить текущий слой. Блок может лежать
1) внутри слоя вдоль столбца,
2) внутри слоя вдоль строки,
3) через границу слоёв, то есть одна половина в текущем слое, а вторая - в следующем.
Третий вариант устанавливает соответствующий бит в выходной маске \(t\).
4) DFS строит числа переходов.
Код берёт первую свободную клетку и рекурсивно перебирает все допустимые размещения. Когда слой заполнен полностью, получен один переход
$$s\to t.$$
Число таких способов обозначается
$$T_{s,t}.$$
5) Векторная динамика.
Пусть \(v_k[s]\) - число способов построить первые \(k\) слоёв и закончить с выходной маской \(s\). Тогда
$$v_{k+1}[t]=\sum_{s=0}^{511} v_k[s]\,T_{s,t}\pmod M.$$
Начальное состояние:
$$v_0[0]=1,$$
все остальные компоненты нулевые. Искомая последовательность - это
$$f(k)=v_k[0],$$
потому что над готовой башней ничего не должно торчать в несуществующий следующий слой.
6) Почему возникает линейная рекуррентность.
Вектор \(v_k\) живёт в 512-мерном пространстве и каждый раз умножается на одну и ту же матрицу. Значит, любая фиксированная координата, в частности \(f(k)\), обязана удовлетворять линейной рекуррентности. Минимальная длина не превосходит 512.
7) Восстановление минимальной рекуррентности.
Программа генерирует первые 1301 значения последовательности и применяет алгоритм Берлекэмпа-Мэсси, получая
$$f(n)=\sum_{j=1}^{L} c_j f(n-j)\pmod M.$$
8) Контрольные значения.
Код проверяет
$$f(2)=229,\qquad f(4)=117805,\qquad f(10)=96149360,$$
а также
$$f(10^3)=24806056,\qquad f(10^6)=30808124.$$
9) Почему используется подход Китамасы.
После нахождения рекуррентности вычисление \(f(N)\) сводится к редукции монома
$$x^N$$
по характеристическому полиному
$$x^L-\sum_{j=1}^{L}c_jx^{L-j}.$$
Оставшиеся коэффициенты линейно комбинируют \(f(0),\dots,f(L-1)\).
10) Как обрабатывается \(10^{10000}\).
Такой показатель не помещается ни в какой стандартный тип. Поэтому код хранит его как десятичную строку, много раз делит её на 2 и записывает остатки. Тем самым получаются двоичные биты показателя.
1) Предвычислить все переходы \(T_{s,t}\) с помощью DFS.
2) Построить достаточно длинный префикс последовательности при помощи 512-состояний DP.
3) Применить Берлекэмпа-Мэсси.
4) Проверить рекуррентность на контрольных значениях.
5) Превратить \(10^{10000}\) из десятичной строки в биты.
6) Вычислить \(f(N)\) через полиномиальное двоичное возведение.
Пространство состояний фиксировано и равно 512 маскам. Финальная стадия требует примерно
$$O(L^2\log N)$$
операций по модулю и
$$O(L)$$
памяти.
Проверяются значения
$$f(2)=229,\quad f(4)=117805,\quad f(10)=96149360,\quad f(10^3)=24806056,\quad f(10^6)=30808124.$$
Для
$$N=10^{10000}$$
получаем
$$f(N)=96972774.$$
نريد عدّ طرق تبليط برج أبعاده \(3\times3\times n\) باستخدام قطع \(2\times1\times1\) مع السماح بكل الاتجاهات الموازية للمحاور. نرمز لعدد هذه الطرق بـ \(f(n)\)، والحساب يتم بترديد
$$100000007.$$
الصعوبة الحقيقية أن الفهرس المطلوب ليس صغيرًا، بل هو
$$N=10^{10000}.$$
1) ملاحظة الزوجية.
حجم البرج هو \(9n\)، وكل قطعة تغطي خليتين. لذلك إذا كان \(n\) فرديًا فلا يمكن التبليط الكامل، أي
$$f(n)=0$$
لكل \(n\) فردي.
2) العمل طبقة بطبقة.
نقسم البرج إلى طبقات \(3\times3\). في كل طبقة 9 خلايا، لذا نمثل الحالة بقناع من 9 بتات
$$s\in[0,2^9).$$
البت التي تساوي 1 تعني أن هذه الخلية مشغولة أصلًا بقطعة بدأت في الطبقة السابقة وامتدت إلى الطبقة الحالية.
3) الأنواع الثلاثة للتموضع.
عند تثبيت قناع الدخول \(s\)، يجب إكمال ملء الطبقة الحالية بالكامل. يمكن وضع القطعة
1) داخل الطبقة نفسها في اتجاه أفقي،
2) داخل الطبقة نفسها في اتجاه عمودي،
3) عبر الحد الفاصل بين الطبقتين بحيث يمتد نصفها إلى الطبقة التالية.
الحالة الثالثة تجعل البت الموافقة تساوي 1 في قناع الخروج \(t\).
4) استخدام DFS لتوليد الانتقالات.
يأخذ الكود أول خلية فارغة في الطبقة ويجرّب جميع التموضعات القانونية بصورة递ية. وعندما تمتلئ الطبقة بالكامل نكون قد حصلنا على انتقال واحد
$$s\to t.$$
عدد الطرق المؤدية إلى هذا الانتقال نرمز له بـ
$$T_{s,t}.$$
5) البرمجة الديناميكية بمتجه حالات.
ليكن \(v_k[s]\) عدد الطرق لبناء أول \(k\) طبقات بحيث ينتهي البناء بقناع خروج \(s\). عندئذ
$$v_{k+1}[t]=\sum_{s=0}^{511} v_k[s]\,T_{s,t}\pmod M.$$
شرط البداية هو
$$v_0[0]=1,$$
لأنه قبل بناء أي طبقة لا توجد خلايا محجوزة من طبقة سابقة. والمتتالية المطلوبة هي
$$f(k)=v_k[0],$$
لأن البرج الصحيح يجب أن ينتهي من دون أي قطعة بارزة إلى طبقة وهمية أعلى.
6) لماذا تظهر علاقة خطية حتمًا.
المتجه \(v_k\) يعيش في فضاء بعده 512، ويتطور دائمًا بضربه في المصفوفة نفسها. لذلك أي مركبة ثابتة منه، وبخاصة \(f(k)\)، لا بد أن تحقق علاقة خطية. طول العلاقة الدنيا لا يتجاوز 512.
7) استخراج العلاقة الدنيا بخوارزمية Berlekamp-Massey.
يولد البرنامج القيم
$$f(0),f(1),\dots,f(1300),$$
ثم يستخرج أقصر علاقة من الشكل
$$f(n)=\sum_{j=1}^{L} c_j f(n-j)\pmod M.$$
8) نقاط الفحص.
يتحقق الكود من أن
$$f(2)=229,\qquad f(4)=117805,\qquad f(10)=96149360,$$
وكذلك
$$f(10^3)=24806056,\qquad f(10^6)=30808124.$$
9) لماذا ننتقل إلى Kitamasa.
بعد معرفة العلاقة الخطية، يصبح حساب \(f(N)\) مكافئًا لاختزال
$$x^N$$
بترديد كثير الحدود المميز
$$x^L-\sum_{j=1}^{L}c_jx^{L-j}.$$
ثم تُستخدم معاملات الباقي لدمج القيم الابتدائية \(f(0),\dots,f(L-1)\).
10) التعامل مع \(10^{10000}\).
هذا الأس غير قابل للتخزين في نوع عددي عادي. لذلك يخزنه البرنامج كسلسلة عشرية، ويقسمها مرارًا على 2، ويسجل البواقي. بهذه الطريقة يحصل على التمثيل الثنائي المطلوب لأسلوب التربيع المتكرر.
1) نحسب مسبقًا جميع الانتقالات \(T_{s,t}\) باستخدام DFS.
2) نولد بادئة كافية من المتتالية \(f(n)\) عبر DP من 512 حالة.
3) نطبق Berlekamp-Massey.
4) نتحقق من العلاقة على نقاط فحص معروفة.
5) نحول \(10^{10000}\) من سلسلة عشرية إلى بتات.
6) نحسب \(f(N)\) بدمج كثيرات الحدود على طريقة Kitamasa.
فضاء الحالات ثابت وعدده 512. أما مرحلة التقييم النهائية فتحتاج تقريبًا إلى
$$O(L^2\log N)$$
عملية معيارية و
$$O(L)$$
ذاكرة إضافية.
يتحقق البرنامج من القيم
$$f(2)=229,\quad f(4)=117805,\quad f(10)=96149360,\quad f(10^3)=24806056,\quad f(10^6)=30808124.$$
ولأجل
$$N=10^{10000}$$
تكون النتيجة النهائية
$$f(N)=96972774.$$