We must tile a row of length 50 using grey unit squares together with red tiles of length 2, green tiles of length 3, and blue tiles of length 4. Every arrangement has to cover the row exactly, with no overlap and no overhang, so the question is how many distinct complete tilings exist.
The all-grey arrangement is included, because grey squares are valid pieces. What makes this problem different from the earlier single-colour variants is that red, green, and blue tiles may be mixed freely in the same row. That turns the task into a counting problem on compositions of 50 with allowed part sizes \(1,2,3,4\), where the size-1 part represents one grey square.
Let \(T(n)\) denote the number of legal tilings of a row of length \(n\). The required answer is therefore \(T(50)\). The useful state is just the remaining length, because once that length is known, the earlier part of the row no longer affects the number of ways to finish it.
A tiling of length \(n\) can be read as a sequence of piece lengths whose sum is \(n\). Since the available lengths are exactly \(1,2,3,4\), each valid arrangement corresponds to a composition of \(n\) with parts in \(\{1,2,3,4\}\). No extra colour factor is needed: there is exactly one tile type of each non-grey length.
The natural base case is \(T(0)=1\): there is exactly one way to tile a row of length 0, namely to place nothing. This is not an extra visible tiling of the 50-cell row; it is the neutral base case that makes the recurrence work cleanly. For convenience we also set \(T(n)=0\) for all \(n<0\).
Take any complete tiling of length \(n\). Its last piece must be exactly one of four possibilities: a grey square of length 1, a red tile of length 2, a green tile of length 3, or a blue tile of length 4. If we remove that last piece, what remains is a unique tiling of length \(n-1\), \(n-2\), \(n-3\), or \(n-4\), respectively.
These four cases are disjoint and exhaustive, so no arrangement is missed and none is counted twice. Therefore, for \(n \ge 1\),
$$T(n)=T(n-1)+T(n-2)+T(n-3)+T(n-4).$$
This four-term linear recurrence is the whole mathematical core of the problem.
Starting from \(T(0)=1\), the first values follow immediately: \(T(1)=1\), \(T(2)=2\), \(T(3)=4\), \(T(4)=8\). The sequence therefore begins
$$1,\,1,\,2,\,4,\,8,\,15,\,29,\dots$$
Each term is the sum of the previous four terms, with any negative-index term treated as 0. The all-grey tiling is already included automatically through repeated use of the \(T(n-1)\) branch.
The small example used as a checkpoint in the implementations is length 5. Applying the recurrence gives
$$T(5)=T(4)+T(3)+T(2)+T(1)=8+4+2+1=15.$$
This has a direct combinatorial meaning. There are 8 tilings ending in a grey square, 4 ending in a red tile, 2 ending in a green tile, and 1 ending in a blue tile. Adding those disjoint families yields exactly 15 tilings.
If we define \(F(x)=\sum_{n \ge 0} T(n)x^n\), the same recurrence can be written as
$$F(x)=1+xF(x)+x^2F(x)+x^3F(x)+x^4F(x),$$
which rearranges to
$$F(x)=\frac{1}{1-x-x^2-x^3-x^4}.$$
The implementations do not need this formula, but it packages the same counting rule into a single algebraic identity and confirms that the sequence is determined entirely by the four allowed tile lengths.
The C++, Python, and Java implementations all use the same bottom-up dynamic program. They allocate a one-dimensional table indexed by row length, store \(1\) at length \(0\), and then fill lengths \(1\) through \(50\) in increasing order. For the current length \(n\), the implementation starts from the count for \(n-1\) and then adds the counts for \(n-2\), \(n-3\), and \(n-4\) whenever those indices are valid.
The key invariant is that after the entry for length \(n\) has been written, every table entry up to \(n\) already equals the exact number of tilings for that length. Because each new state depends only on smaller states, one left-to-right pass is enough. The final answer is the entry at length \(50\). The C++ implementation also includes a small sanity check at length \(5\), confirming the known value \(15\).
For a general row length \(N\), the algorithm performs one constant-size update for each \(n=1,2,\dots,N\). That gives \(O(N)\) time. With \(N=50\), the running time is tiny.
As written, the implementations store all values from \(T(0)\) through \(T(N)\), so the space usage is \(O(N)\). Mathematically only the previous four values are needed, so the recurrence could be compressed to \(O(1)\) extra space, but the full table keeps the code straightforward. The value for \(N=50\) also fits comfortably inside a signed 64-bit integer, which is why the compiled implementations can use ordinary integer arithmetic.
Gesucht ist die Anzahl aller vollständigen Pflasterungen einer Reihe der Länge 50 mit grauen Einheitsquadraten sowie roten Steinen der Länge 2, grünen Steinen der Länge 3 und blauen Steinen der Länge 4. Jede Anordnung muss die Reihe exakt bedecken, also ohne Überlappung und ohne Überstand.
Die vollständig graue Pflasterung zählt mit, weil graue Einheitsquadrate erlaubte Bausteine sind. Der entscheidende Unterschied zu den einfacheren Varianten ist, dass rote, grüne und blaue Steine beliebig gemischt werden dürfen. Damit wird das Problem zu einer Zählung von Zerlegungen der Zahl 50 in Teile aus \(\{1,2,3,4\}\), wobei der Teil 1 einem grauen Quadrat entspricht.
Bezeichne mit \(T(n)\) die Anzahl legaler Pflasterungen einer Reihe der Länge \(n\). Gesucht ist also \(T(50)\). Die richtige Zustandsgröße ist nur die verbleibende Länge, denn sobald diese feststeht, spielt der bereits gelegte Teil der Reihe für die Anzahl der Fortsetzungen keine Rolle mehr.
Jede Pflasterung der Länge \(n\) kann als Folge von Bausteinlängen gelesen werden, deren Summe \(n\) ist. Weil genau die Längen \(1,2,3,4\) erlaubt sind, entspricht jede gültige Anordnung einer Komposition von \(n\) mit Teilen aus \(\{1,2,3,4\}\). Ein zusätzlicher Farb-Faktor ist nicht nötig, da es zu jeder nicht-grauen Länge genau einen Stein gibt.
Der natürliche Anfangswert ist \(T(0)=1\): Eine Reihe der Länge 0 kann genau auf eine Weise gepflastert werden, nämlich durch Nichtstun. Das ist keine zusätzliche sichtbare Pflasterung der 50er-Reihe, sondern der neutrale Basisfall der Rekursion. Bequem setzt man außerdem \(T(n)=0\) für alle \(n<0\).
Betrachte eine vollständige Pflasterung der Länge \(n\). Der letzte Baustein ist zwingend genau einer von vier Fällen: ein graues Quadrat der Länge 1, ein roter Stein der Länge 2, ein grüner Stein der Länge 3 oder ein blauer Stein der Länge 4. Entfernt man diesen letzten Baustein, bleibt eindeutig eine Pflasterung der Länge \(n-1\), \(n-2\), \(n-3\) oder \(n-4\) übrig.
Diese vier Fälle sind disjunkt und vollständig, also wird nichts vergessen und nichts doppelt gezählt. Für \(n \ge 1\) gilt daher
$$T(n)=T(n-1)+T(n-2)+T(n-3)+T(n-4).$$
Diese lineare Vier-Term-Rekursion ist der eigentliche mathematische Kern der Aufgabe.
Ausgehend von \(T(0)=1\) erhält man sofort \(T(1)=1\), \(T(2)=2\), \(T(3)=4\), \(T(4)=8\). Die Folge beginnt also mit
$$1,\,1,\,2,\,4,\,8,\,15,\,29,\dots$$
Jedes neue Glied ist die Summe der vier vorherigen, wobei negative Indizes als 0 behandelt werden. Die vollständig graue Pflasterung steckt automatisch in den wiederholten Beiträgen des Zweigs \(T(n-1)\).
Das kleine Beispiel, das auch als Kontrolle in den Implementierungen dient, ist die Länge 5. Mit der Rekursion folgt
$$T(5)=T(4)+T(3)+T(2)+T(1)=8+4+2+1=15.$$
Das hat eine direkte kombinatorische Bedeutung. Es gibt 8 Pflasterungen mit grauem Schlussstein, 4 mit rotem Schlussstein, 2 mit grünem Schlussstein und 1 mit blauem Schlussstein. Die Summe dieser disjunkten Familien ergibt genau 15.
Definiert man \(F(x)=\sum_{n \ge 0} T(n)x^n\), dann lässt sich dieselbe Rekursion schreiben als
$$F(x)=1+xF(x)+x^2F(x)+x^3F(x)+x^4F(x),$$
also
$$F(x)=\frac{1}{1-x-x^2-x^3-x^4}.$$
Die Programme brauchen diese Formel nicht, aber sie bündelt dieselbe Zählregel in einer einzigen algebraischen Identität und zeigt, dass die gesamte Folge vollständig durch die vier erlaubten Steinlängen bestimmt ist.
Die Implementierungen in C++, Python und Java verwenden alle dieselbe Bottom-up-Dynamik. Sie legen eine eindimensionale Tabelle über der Reihenlänge an, setzen bei Länge \(0\) den Wert \(1\) und berechnen anschließend die Werte für \(1\) bis \(50\) in aufsteigender Reihenfolge. Für die aktuelle Länge \(n\) wird vom Wert für \(n-1\) ausgegangen; danach werden die Werte für \(n-2\), \(n-3\) und \(n-4\) addiert, sofern diese Indizes existieren.
Die zentrale Invariante lautet: Sobald der Eintrag für Länge \(n\) geschrieben wurde, enthält jede Tabellenposition bis \(n\) bereits die exakte Anzahl der Pflasterungen dieser Länge. Weil jeder neue Zustand nur von kleineren Zuständen abhängt, genügt ein einziger Durchlauf von links nach rechts. Die gesuchte Antwort ist der Eintrag bei Länge \(50\). Die C++-Version enthält zusätzlich eine kleine Plausibilitätsprüfung für Länge \(5\) mit dem bekannten Wert \(15\).
Für eine allgemeine Reihenlänge \(N\) wird für jedes \(n=1,2,\dots,N\) genau ein Update mit konstantem Aufwand ausgeführt. Daraus ergibt sich eine Laufzeit von \(O(N)\). Für \(N=50\) ist die Rechnung praktisch sofort erledigt.
In der vorliegenden Form speichern die Implementierungen alle Werte von \(T(0)\) bis \(T(N)\), daher beträgt der Speicherbedarf \(O(N)\). Rein mathematisch würden die letzten vier Werte genügen, also wäre auch \(O(1)\) Zusatzspeicher möglich; die vollständige Tabelle hält den Code jedoch besonders klar. Außerdem passt der Wert für \(N=50\) bequem in ein vorzeichenbehaftetes 64-Bit-Integer, weshalb die kompilierten Implementierungen ohne Mehrpräzisionsarithmetik auskommen.
Uzunluğu 50 olan bir sırayı, uzunluğu 1 olan gri karelerle birlikte uzunluğu 2 olan kırmızı, uzunluğu 3 olan yeşil ve uzunluğu 4 olan mavi parçalar kullanarak tam olarak döşememiz isteniyor. Her yerleşim satırı eksiksiz kaplamalı; üst üste binme veya taşma yok.
Tamamı gri olan düzenleme de sayıya dahildir, çünkü gri kareler de geçerli parçalardır. Bu soruyu önceki daha dar varyantlardan ayıran nokta, kırmızı, yeşil ve mavi parçaların aynı satırda serbestçe karıştırılabilmesidir. Böylece problem, 50 sayısını \(\{1,2,3,4\}\) kümesinden parçalarla yazmanın kaç farklı yolu olduğuna indirgenir; burada 1 uzunluğu bir gri kareyi temsil eder.
\(T(n)\) ile uzunluğu \(n\) olan bir satırın geçerli döşeme sayısını gösterelim. O zaman aranan değer \(T(50)\) olur. En doğru durum değişkeni yalnızca kalan uzunluktur; çünkü kalan uzunluk bilindiğinde, satırın daha önce nasıl doldurulduğu devam sayısını değiştirmez.
Uzunluğu \(n\) olan her döşeme, toplamı \(n\) yapan bir parça uzunlukları dizisi olarak okunabilir. İzin verilen uzunluklar tam olarak \(1,2,3,4\) olduğu için her geçerli yerleşim, parçaları \(\{1,2,3,4\}\) kümesinden gelen bir bileşime karşılık gelir. Ek bir renk katsayısı yoktur; gri olmayan her uzunluk için tam bir parça türü vardır.
Doğal taban durum \(T(0)=1\)'dir: uzunluğu 0 olan bir satırı döşemenin tek yolu hiçbir şey yerleştirmemektir. Bu, 50 hücreli satıra eklenmiş ayrı bir görünür düzenleme değildir; yinelemenin temiz kapanmasını sağlayan nötr başlangıç durumudur. Ayrıca tek biçimli yazım için \(n<0\) olduğunda \(T(n)=0\) kabul edilir.
Uzunluğu \(n\) olan herhangi bir tam döşemeyi alın. Son parça mutlaka dört olasılıktan biridir: uzunluğu 1 olan gri kare, uzunluğu 2 olan kırmızı parça, uzunluğu 3 olan yeşil parça veya uzunluğu 4 olan mavi parça. Bu son parçayı kaldırınca geride sırasıyla uzunluğu \(n-1\), \(n-2\), \(n-3\) ya da \(n-4\) olan benzersiz bir döşeme kalır.
Bu dört durum hem ayrık hem de kapsamlıdır; yani hiçbir düzenleme kaçmaz ve hiçbirisi iki kez sayılmaz. Dolayısıyla \(n \ge 1\) için
$$T(n)=T(n-1)+T(n-2)+T(n-3)+T(n-4)$$
elde edilir. Sorunun bütün matematiksel özü bu dört terimli lineer yinelemedir.
\(T(0)=1\)'den başlayınca ilk değerler hemen çıkar: \(T(1)=1\), \(T(2)=2\), \(T(3)=4\), \(T(4)=8\). Böylece dizi
$$1,\,1,\,2,\,4,\,8,\,15,\,29,\dots$$
şeklinde başlar. Her yeni terim, önceki dört terimin toplamıdır; negatif indeksli terimler 0 kabul edilir. Tamamı gri olan döşeme de \(T(n-1)\) dalının tekrarlı kullanımı içinde otomatik olarak sayılmış olur.
Uygulamalarda kontrol noktası olarak kullanılan küçük örnek uzunluk 5'tir. Yineleme doğrudan
$$T(5)=T(4)+T(3)+T(2)+T(1)=8+4+2+1=15$$
verir. Bunun net bir kombinatorik yorumu vardır: sonu gri kare ile biten 8, kırmızı ile biten 4, yeşil ile biten 2 ve mavi ile biten 1 döşeme vardır. Bu ayrık ailelerin toplamı tam olarak 15 eder.
\(F(x)=\sum_{n \ge 0} T(n)x^n\) tanımı yapılırsa aynı yineleme
$$F(x)=1+xF(x)+x^2F(x)+x^3F(x)+x^4F(x)$$
biçiminde yazılır ve buradan
$$F(x)=\frac{1}{1-x-x^2-x^3-x^4}$$
sonucu çıkar. Kod bu formülü kullanmaz; ancak bu ifade, aynı sayma kuralını tek bir cebirsel kimlikte toplar ve dizinin yalnızca izin verilen dört parça uzunluğu tarafından belirlendiğini gösterir.
C++, Python ve Java uygulamalarının üçü de aynı aşağıdan yukarı dinamik programı kullanır. Satır uzunluğuna göre indekslenen tek boyutlu bir tablo kurulur, uzunluk \(0\) için değer \(1\) yazılır ve sonra \(1\)'den \(50\)'ye kadar bütün uzunluklar artan sırayla doldurulur. O andaki uzunluk \(n\) için önce \(n-1\)'in sayısı alınır; ardından indeks geçerliyse \(n-2\), \(n-3\) ve \(n-4\) katkıları eklenir.
Temel değişmez şudur: uzunluk \(n\) için tablo girişi yazıldığında, \(n\)'e kadar olan bütün girişler artık o uzunlukların tam döşeme sayılarını içerir. Her yeni durum yalnızca daha küçük durumlardan beslendiği için soldan sağa tek bir geçiş yeterlidir. Sonuç, uzunluk \(50\) girişidir. C++ uygulaması ayrıca uzunluk \(5\) için bilinen \(15\) değerini doğrulayan küçük bir sağlamlık kontrolü de içerir.
Genel uzunluğu \(N\) olan bir satır için algoritma, \(n=1,2,\dots,N\) değerlerinin her biri için sabit maliyetli tek bir güncelleme yapar. Bu nedenle zaman karmaşıklığı \(O(N)\)'dir. \(N=50\) için çalışma süresi son derece küçüktür.
Mevcut haliyle uygulamalar \(T(0)\) ile \(T(N)\) arasındaki tüm değerleri sakladığı için bellek kullanımı \(O(N)\)'dir. Matematiksel olarak yalnızca son dört değere ihtiyaç vardır; dolayısıyla \(O(1)\) ek bellekle de yapılabilir. Yine de tam tablo çözümü kodu daha okunur kılar. Ayrıca \(N=50\) için elde edilen değer işaretli 64 bit tamsayı sınırları içinde rahatça kaldığından, derlenen dillerde sıradan tamsayı aritmetiği yeterlidir.
Debemos recubrir una fila de longitud 50 usando cuadrados grises de longitud 1 junto con fichas rojas de longitud 2, verdes de longitud 3 y azules de longitud 4. Cada disposición tiene que cubrir la fila exactamente, sin solapamientos ni sobrantes, y se pide contar cuántos recubrimientos completos distintos existen.
La disposición formada solo por cuadrados grises también cuenta, porque las piezas grises son válidas. La diferencia importante con variantes más restringidas es que aquí las fichas rojas, verdes y azules pueden mezclarse libremente. Por eso el problema puede verse como una cuenta de composiciones de 50 con partes permitidas en \(\{1,2,3,4\}\), donde la parte 1 representa un cuadrado gris.
Sea \(T(n)\) el número de recubrimientos legales de una fila de longitud \(n\). Entonces la respuesta buscada es \(T(50)\). El estado correcto depende solo de la longitud restante, porque una vez fijada esa longitud, la forma exacta en que se rellenó el prefijo ya no altera el número de continuaciones posibles.
Cada recubrimiento de longitud \(n\) puede leerse como una secuencia de longitudes de piezas cuya suma es \(n\). Como las longitudes permitidas son exactamente \(1,2,3,4\), cada disposición válida corresponde a una composición de \(n\) con partes en \(\{1,2,3,4\}\). No hace falta introducir un factor adicional por color: para cada longitud no gris hay exactamente un tipo de ficha.
El caso base natural es \(T(0)=1\): una fila de longitud 0 se recubre de una única manera, que es no poner nada. Eso no añade una disposición visible extra para la fila de longitud 50; es simplemente el caso neutro que cierra bien la recurrencia. Por comodidad también se toma \(T(n)=0\) cuando \(n<0\).
Tómese cualquier recubrimiento completo de longitud \(n\). Su última pieza debe ser exactamente una de cuatro posibilidades: un cuadrado gris de longitud 1, una ficha roja de longitud 2, una verde de longitud 3 o una azul de longitud 4. Si retiramos esa última pieza, queda de manera única un recubrimiento de longitud \(n-1\), \(n-2\), \(n-3\) o \(n-4\), respectivamente.
Estos cuatro casos son disjuntos y exhaustivos, así que no se pierde ninguna disposición ni se cuenta dos veces la misma. Por tanto, para \(n \ge 1\),
$$T(n)=T(n-1)+T(n-2)+T(n-3)+T(n-4).$$
Esta recurrencia lineal de cuatro términos es el núcleo matemático completo del problema.
Partiendo de \(T(0)=1\), se obtiene enseguida \(T(1)=1\), \(T(2)=2\), \(T(3)=4\), \(T(4)=8\). Por tanto, la sucesión empieza como
$$1,\,1,\,2,\,4,\,8,\,15,\,29,\dots$$
Cada nuevo término es la suma de los cuatro anteriores, tratando como 0 cualquier índice negativo. La configuración completamente gris queda incluida automáticamente mediante usos repetidos de la rama \(T(n-1)\).
El ejemplo pequeño utilizado como verificación en las implementaciones es la longitud 5. Aplicando la recurrencia,
$$T(5)=T(4)+T(3)+T(2)+T(1)=8+4+2+1=15.$$
La interpretación combinatoria es muy clara. Hay 8 recubrimientos que terminan en un cuadrado gris, 4 que terminan en una ficha roja, 2 que terminan en una verde y 1 que termina en una azul. La suma de esas familias disjuntas da exactamente 15.
Si definimos \(F(x)=\sum_{n \ge 0} T(n)x^n\), la misma recurrencia se puede escribir como
$$F(x)=1+xF(x)+x^2F(x)+x^3F(x)+x^4F(x),$$
de donde se obtiene
$$F(x)=\frac{1}{1-x-x^2-x^3-x^4}.$$
Las implementaciones no necesitan esta fórmula, pero resume la misma regla de conteo en una sola identidad algebraica y deja claro que la sucesión está determinada por las cuatro longitudes permitidas.
Las implementaciones en C++, Python y Java usan el mismo programa dinámico de abajo hacia arriba. Reservan una tabla unidimensional indexada por la longitud de la fila, guardan \(1\) en la posición correspondiente a la longitud \(0\) y después rellenan las longitudes \(1\) hasta \(50\) en orden creciente. Para una longitud actual \(n\), el programa parte del conteo de \(n-1\) y luego añade los de \(n-2\), \(n-3\) y \(n-4\) siempre que esos índices existan.
La invariante clave es la siguiente: cuando ya se escribió la entrada para la longitud \(n\), todas las entradas hasta \(n\) contienen exactamente el número correcto de recubrimientos para esa longitud. Como cada nuevo estado depende solo de estados más pequeños, basta una sola pasada de izquierda a derecha. La respuesta final es la entrada de longitud \(50\). La implementación en C++ además incluye una comprobación pequeña en longitud \(5\), verificando el valor conocido \(15\).
Para una longitud general \(N\), el algoritmo realiza una actualización de tamaño constante para cada \(n=1,2,\dots,N\). Por lo tanto, el tiempo total es \(O(N)\). Con \(N=50\), la ejecución es mínima.
Tal como están escritas, las implementaciones almacenan todos los valores desde \(T(0)\) hasta \(T(N)\), así que el espacio usado es \(O(N)\). Matemáticamente solo hacen falta los cuatro valores anteriores, por lo que podría reducirse a \(O(1)\) espacio extra, pero la tabla completa hace que el código sea más claro. El valor para \(N=50\) también cabe con holgura en un entero con signo de 64 bits, razón por la cual las versiones compiladas no necesitan aritmética de precisión arbitraria.
题目要求把一条长度为 50 的直线完全铺满。可用的砖块有四种：长度为 1 的灰色方砖、长度为 2 的红色长砖、长度为 3 的绿色长砖，以及长度为 4 的蓝色长砖。每一种铺法都必须恰好覆盖整条长度，不能重叠，也不能越界。
全部用灰色方砖的铺法也要计入答案，因为灰色方砖本身就是合法部件。这个问题的关键点在于三种彩色长砖可以自由混用，所以它不是分别计数再相加，而是一个统一的计数问题。换句话说，我们在数的是把 50 拆成若干个 \(1,2,3,4\) 之和的有序方式，其中长度 1 对应一块灰色方砖。
设 \(T(n)\) 表示铺满长度为 \(n\) 的一行的合法铺法总数，那么题目要求的就是 \(T(50)\)。这里最合适的状态只有一个量：剩余长度。因为一旦剩余长度确定，前面已经怎样铺并不会改变后面还能有多少种完成方式。
任何长度为 \(n\) 的铺法，都可以看成若干块砖长度组成的一个有序序列，其总和等于 \(n\)。由于允许的长度恰好是 \(1,2,3,4\)，所以每一种合法铺法都对应于 \(n\) 的一个组合分拆，且每一部分都来自集合 \(\{1,2,3,4\}\)。这里不需要再乘一个“颜色数”的系数，因为每一个非灰色长度只对应一种砖：2 只对应红砖，3 只对应绿砖，4 只对应蓝砖。
最自然的初值是 \(T(0)=1\)。长度为 0 的行只有一种铺法，那就是什么都不放。这个值不是在长度 50 的实际铺法之外又额外多算了一种，而是递推中必须存在的中性起点。为了让公式统一，还可以约定当 \(n<0\) 时 \(T(n)=0\)。
取任意一个长度为 \(n\) 的完整铺法，最后一块砖一定属于四种情况之一：长度 1 的灰砖、长度 2 的红砖、长度 3 的绿砖，或长度 4 的蓝砖。如果把最后这一块拿掉，前面剩下的部分就唯一地变成一个长度分别为 \(n-1\)、\(n-2\)、\(n-3\)、\(n-4\) 的合法铺法。
这四类情况既互不重叠，又覆盖了全部可能，所以不会漏数，也不会重数。因此，对所有 \(n \ge 1\)，都有
$$T(n)=T(n-1)+T(n-2)+T(n-3)+T(n-4).$$
这条四项线性递推式就是本题最核心的数学结构。
从 \(T(0)=1\) 出发，可以立刻得到 \(T(1)=1\), \(T(2)=2\), \(T(3)=4\), \(T(4)=8\)。 因而数列开头是
$$1,\,1,\,2,\,4,\,8,\,15,\,29,\dots$$
每一项都是前四项之和，不足的负下标项按 0 处理。全灰铺法自然包含在不断使用 \(T(n-1)\) 这一分支的过程中，并不需要额外单独讨论。
实现里专门用长度 5 作为一个小型校验点。根据递推式，
$$T(5)=T(4)+T(3)+T(2)+T(1)=8+4+2+1=15.$$
这个 15 也有非常直观的含义。以灰砖结尾的铺法有 8 种，以红砖结尾的有 4 种，以绿砖结尾的有 2 种，以蓝砖结尾的有 1 种。把这四个互不相交的集合相加，正好得到 15。
如果定义生成函数 \(F(x)=\sum_{n \ge 0} T(n)x^n\)，那么同样的递推关系可以写成
$$F(x)=1+xF(x)+x^2F(x)+x^3F(x)+x^4F(x),$$
整理后得到
$$F(x)=\frac{1}{1-x-x^2-x^3-x^4}.$$
代码本身并不需要直接用到这个公式，但它把同一个计数规律压缩成一个代数对象，也说明整个数列完全由允许使用的四种砖长决定。
C++、Python 和 Java 三个实现都采用相同的自底向上动态规划。它们先建立一个按行长索引的一维表，把长度 0 的位置设为 \(1\)，然后按从小到大的顺序计算长度 \(1\) 到 \(50\) 的答案。处理当前长度 \(n\) 时，程序先取长度 \(n-1\) 的计数，再在下标合法的前提下加入 \(n-2\)、\(n-3\)、\(n-4\) 的计数。
这里的核心不变量是：当长度 \(n\) 的表项被写好之后，从 \(0\) 到 \(n\) 的所有表项都已经是对应长度的精确铺法数。因为每个新状态只依赖更小的状态，所以从左到右扫一遍就足够了。最终输出的就是长度 50 对应的表项。C++ 实现还额外带有一个长度 5 的小检查，用来确认已知值 15。
对于一般长度 \(N\)，算法会对每个 \(n=1,2,\dots,N\) 做一次常数规模的更新，因此总时间复杂度是 \(O(N)\)。这里 \(N=50\)，所以运行代价非常小。
按照当前写法，程序保存了从 \(T(0)\) 到 \(T(N)\) 的全部结果，因此空间复杂度是 \(O(N)\)。从数学上说，其实只需要最近四个值就能继续递推，所以额外空间也可以压缩到 \(O(1)\)；不过完整表更直接，也更容易核对。对于 \(N=50\)，最终结果也远在有符号 64 位整数范围之内，因此编译型实现不需要使用大整数库。
Нужно полностью замостить ряд длины 50, используя серые квадраты длины 1, а также красные плитки длины 2, зелёные длины 3 и синие длины 4. Каждое допустимое размещение должно покрывать весь ряд ровно целиком, без перекрытий и без выхода за границы.
Полностью серое замощение тоже учитывается, потому что серые клетки являются разрешёнными элементами. Важное отличие этой задачи от более узких вариантов состоит в том, что красные, зелёные и синие плитки можно свободно смешивать. Поэтому задача сводится к подсчёту упорядоченных разложений числа 50 на слагаемые из множества \(\{1,2,3,4\}\), где единица означает одну серую клетку.
Обозначим через \(T(n)\) число корректных замощений ряда длины \(n\). Тогда искомая величина равна \(T(50)\). Удобное состояние здесь зависит только от оставшейся длины: как только она зафиксирована, конкретный вид уже уложенной части больше не влияет на количество способов закончить ряд.
Любое замощение длины \(n\) можно рассматривать как последовательность длин плиток, сумма которых равна \(n\). Поскольку разрешены ровно длины \(1,2,3,4\), каждое допустимое расположение соответствует композиции числа \(n\) с частями из \(\{1,2,3,4\}\). Дополнительный множитель на цвет не нужен: для каждой ненулевой длины больше 1 существует ровно один тип цветной плитки.
Естественный базовый случай таков: \(T(0)=1\). Ряд длины 0 можно замостить ровно одним способом, а именно ничего не положить. Это не лишнее видимое замощение ряда длины 50, а нейтральный старт, необходимый для корректной рекуррентной формулы. Кроме того, удобно положить \(T(n)=0\) при \(n<0\).
Возьмём любое полное замощение длины \(n\). Его последняя плитка обязана быть одной из четырёх: серый квадрат длины 1, красная плитка длины 2, зелёная длины 3 или синяя длины 4. Если убрать последнюю плитку, то останется единственное замощение длины \(n-1\), \(n-2\), \(n-3\) или \(n-4\) соответственно.
Эти четыре случая попарно не пересекаются и вместе покрывают все варианты, так что ничего не теряется и ничего не считается дважды. Следовательно, для \(n \ge 1\) имеем
$$T(n)=T(n-1)+T(n-2)+T(n-3)+T(n-4).$$
Именно эта линейная рекуррентная формула из четырёх членов и составляет математическое ядро задачи.
Начиная с \(T(0)=1\), сразу получаем \(T(1)=1\), \(T(2)=2\), \(T(3)=4\), \(T(4)=8\). Поэтому последовательность начинается так:
$$1,\,1,\,2,\,4,\,8,\,15,\,29,\dots$$
Каждый следующий член равен сумме четырёх предыдущих, а члены с отрицательными индексами считаются равными нулю. Полностью серое замощение автоматически входит в подсчёт через многократное применение ветви \(T(n-1)\).
В реализациях встроена маленькая проверка на длине 5. По рекуррентной формуле
$$T(5)=T(4)+T(3)+T(2)+T(1)=8+4+2+1=15.$$
У этого числа есть прямой комбинаторный смысл. Существует 8 замощений, оканчивающихся серой клеткой, 4 оканчивающихся красной плиткой, 2 оканчивающихся зелёной и 1 оканчивающееся синей. Сумма этих непересекающихся семейств даёт ровно 15.
Если ввести производящую функцию \(F(x)=\sum_{n \ge 0} T(n)x^n\), то ту же рекурсию можно записать как
$$F(x)=1+xF(x)+x^2F(x)+x^3F(x)+x^4F(x),$$
откуда следует
$$F(x)=\frac{1}{1-x-x^2-x^3-x^4}.$$
Программа не использует эту формулу напрямую, но она упаковывает то же правило подсчёта в одно алгебраическое тождество и показывает, что вся последовательность определяется именно четырьмя разрешёнными длинами плиток.
Реализации на C++, Python и Java используют один и тот же динамический алгоритм снизу вверх. Они создают одномерную таблицу, индексируемую длиной ряда, записывают \(1\) для длины \(0\), а затем последовательно вычисляют значения для длин от \(1\) до \(50\). Для текущей длины \(n\) алгоритм сначала берёт значение для \(n-1\), а затем прибавляет значения для \(n-2\), \(n-3\) и \(n-4\), если такие индексы существуют.
Главный инвариант состоит в том, что после записи ячейки для длины \(n\) все ячейки от \(0\) до \(n\) уже содержат точное число замощений соответствующей длины. Поскольку новое состояние зависит только от меньших состояний, достаточно одного прохода слева направо. Итоговый ответ находится в ячейке для длины \(50\). В версии на C++ дополнительно есть небольшая проверка для длины \(5\), подтверждающая известное значение \(15\).
Для произвольной длины \(N\) алгоритм выполняет одно обновление постоянной стоимости для каждого \(n=1,2,\dots,N\). Следовательно, время работы равно \(O(N)\). При \(N=50\) вычисление получается совсем небольшим.
В текущем виде реализации хранят все значения от \(T(0)\) до \(T(N)\), поэтому расход памяти равен \(O(N)\). С математической точки зрения достаточно помнить только четыре предыдущих значения, так что дополнительную память можно было бы сжать до \(O(1)\), но полная таблица делает код проще и прозрачнее. Значение для \(N=50\) также уверенно помещается в знаковое 64-битное целое, поэтому компилируемые версии обходятся без длинной арифметики.
المطلوب هو تبليط صف طوله 50 بالكامل باستخدام مربعات رمادية طولها 1، مع قطع حمراء طولها 2، وقطع خضراء طولها 3، وقطع زرقاء طولها 4. كل ترتيب صالح يجب أن يغطي الصف تغطية تامة من دون تداخل ومن دون تجاوز للنهاية.
الحالة التي يكون فيها الصف كله رماديا داخلة في العد، لأن المربعات الرمادية نفسها قطع مسموح بها. النقطة المهمة هنا أن القطع الحمراء والخضراء والزرقاء يمكن خلطها بحرية في الصف نفسه، ولذلك تتحول المسألة إلى عد جميع الطرق المرتبة لكتابة العدد 50 كمجموع لأجزاء من المجموعة \(\{1,2,3,4\}\)، حيث تمثل القيمة 1 مربعا رماديا واحدا.
لنرمز بـ \(T(n)\) إلى عدد التبليطات القانونية لصف طوله \(n\). عندئذ تكون القيمة المطلوبة هي \(T(50)\). الحالة المناسبة هنا تعتمد فقط على الطول المتبقي، لأن معرفة هذا الطول تكفي وحدها لتحديد عدد طرق الإكمال الممكنة، أما شكل الجزء الذي سبق تبليطه فلا يؤثر بعد ذلك.
كل تبليط لطول \(n\) يمكن قراءته على أنه تسلسل مرتب من أطوال قطع مجموعها \(n\). وبما أن الأطوال المسموح بها هي بالضبط \(1,2,3,4\)، فإن كل ترتيب صالح يقابل تركيبا للعدد \(n\) بأجزاء من \(\{1,2,3,4\}\). ولا نحتاج إلى معامل إضافي للألوان، لأن كل طول غير رمادي يقابله نوع واحد فقط من القطع.
الحالة الابتدائية الطبيعية هي \(T(0)=1\): فهناك طريقة واحدة فقط لتبليط صف طوله 0، وهي ألا نضع شيئا. هذه ليست ترتيبا مرئيا إضافيا لصف الطول 50، بل هي نقطة البداية المحايدة التي تجعل العلاقة العودية تعمل بصورة نظيفة. ولتوحيد الصياغة نأخذ أيضا \(T(n)=0\) عندما يكون \(n<0\).
خذ أي تبليط كامل لطول \(n\). القطعة الأخيرة فيه لا بد أن تكون واحدة من أربع حالات فقط: مربع رمادي طوله 1، أو قطعة حمراء طولها 2، أو قطعة خضراء طولها 3، أو قطعة زرقاء طولها 4. إذا حذفنا هذه القطعة الأخيرة، بقي تبليط وحيد لطول \(n-1\) أو \(n-2\) أو \(n-3\) أو \(n-4\) على الترتيب.
هذه الحالات الأربع منفصلة وتغطي جميع الاحتمالات، لذلك لا يوجد عد مكرر ولا حالة مفقودة. ومن ثم، لكل \(n \ge 1\)، نحصل على
$$T(n)=T(n-1)+T(n-2)+T(n-3)+T(n-4).$$
وهذه العلاقة الخطية ذات الحدود الأربعة هي الجوهر الرياضي الكامل للمسألة.
انطلاقا من \(T(0)=1\) نحصل مباشرة على \(T(1)=1\)، \(T(2)=2\)، \(T(3)=4\)، \(T(4)=8\). ولذلك تبدأ المتتالية بالشكل
$$1,\,1,\,2,\,4,\,8,\,15,\,29,\dots$$
كل حد جديد يساوي مجموع الحدود الأربعة السابقة، مع اعتبار أي فهرس سالب مساويا للصفر. أما التبليط الرمادي بالكامل فيدخل تلقائيا عبر التكرار المتواصل لفرع \(T(n-1)\).
المثال الصغير المستخدم كاختبار في التنفيذات هو الصف ذو الطول 5. بتطبيق العلاقة العودية نحصل على
$$T(5)=T(4)+T(3)+T(2)+T(1)=8+4+2+1=15.$$
ولهذا العدد معنى تركيبي مباشر. توجد 8 تبليطات تنتهي بمربع رمادي، و4 تنتهي بقطعة حمراء، و2 تنتهي بقطعة خضراء، و1 تنتهي بقطعة زرقاء. مجموع هذه العائلات المنفصلة يعطينا 15 بالضبط.
إذا عرفنا الدالة المولدة \(F(x)=\sum_{n \ge 0} T(n)x^n\)، فإن العلاقة نفسها يمكن كتابتها على الصورة
$$F(x)=1+xF(x)+x^2F(x)+x^3F(x)+x^4F(x),$$
ومنها ينتج
$$F(x)=\frac{1}{1-x-x^2-x^3-x^4}.$$
التنفيذات لا تستعمل هذه الصيغة مباشرة، لكنها تجمع قاعدة العد نفسها في هوية جبرية واحدة، وتوضح أن المتتالية تتحدد بالكامل من أطوال القطع الأربعة المسموح بها.
تنفيذات C++ وPython وJava كلها تعتمد البرمجة الديناميكية التصاعدية نفسها. فهي تنشئ جدولا أحادي البعد مفهرسا بطول الصف، وتضع القيمة \(1\) عند الطول \(0\)، ثم تحسب القيم للأطوال من \(1\) إلى \(50\) بترتيب تصاعدي. وعند معالجة طول حالي \(n\)، يبدأ التنفيذ بعدد طرق الطول \(n-1\)، ثم يضيف مساهمات \(n-2\) و\(n-3\) و\(n-4\) كلما كانت هذه الفهارس صالحة.
الثابت الأساسي هنا هو أنه بعد كتابة الخانة الخاصة بالطول \(n\)، تكون كل الخانات من \(0\) حتى \(n\) قد أصبحت تمثل الأعداد الصحيحة الدقيقة لتبليطات تلك الأطوال. ولأن كل حالة جديدة تعتمد فقط على حالات أصغر، فإن المرور مرة واحدة من اليسار إلى اليمين يكفي. النتيجة النهائية هي الخانة الخاصة بالطول 50. كما أن تنفيذ C++ يحتوي على تحقق صغير عند الطول 5 لتأكيد القيمة المعروفة 15.
لطول عام \(N\)، ينفذ الخوارزم تحديثا ذا كلفة ثابتة لكل \(n=1,2,\dots,N\)، ولذلك يكون زمن التنفيذ \(O(N)\). وعندما يكون \(N=50\) فإن الكلفة العملية صغيرة جدا.
في الصيغة الحالية تحتفظ التنفيذات بجميع القيم من \(T(0)\) حتى \(T(N)\)، ولذلك يكون استهلاك الذاكرة \(O(N)\). ومن الناحية الرياضية يكفي الاحتفاظ بآخر أربع قيم فقط، أي إن الضغط إلى \(O(1)\) ذاكرة إضافية ممكن، لكن الجدول الكامل يجعل الشيفرة أبسط وأوضح. كما أن قيمة \(N=50\) تقع بسهولة داخل مجال الأعداد الصحيحة الموقعة ذات 64 بت، ولهذا لا تحتاج النسخ المترجمة إلى مكتبات أعداد كبيرة.