We want the number of length-30 attendance records over \(\{O,A,L\}\), where \(O\) means on time, \(A\) absent, and \(L\) late. A record is prize-eligible if it uses at most one \(L\) in total and never contains three consecutive \(A\)'s.
The two restrictions have different flavors. The late condition is global, because a single \(L\) can be used only once anywhere in the string. The absence condition is local, because only the current trailing run of \(A\)'s matters when we decide whether another \(A\) is legal.
The implementations exploit exactly that structure. Instead of remembering the whole prefix, they remember only the pieces of information that affect the next day.
For \(n \ge 0\), let \(S_n^{\ell,a}\) denote the number of valid length-\(n\) prefixes such that \(\ell \in \{0,1\}\) records whether a late day has already appeared, and \(a \in \{0,1,2\}\) is the number of consecutive trailing absences.
These two quantities are sufficient. Any earlier part of the string becomes irrelevant once we know whether the unique \(L\) has already been spent and whether the current suffix ends with 0, 1, or 2 copies of \(A\). That gives exactly \(2 \times 3 = 6\) states.
The initial condition is
$$S_0^{0,0}=1,$$
with every other \(S_0^{\ell,a}\) equal to 0, because the empty record is valid, has used no late day, and has no trailing absences.
From a valid state, there are at most three legal extensions.
If we append \(O\), the absence streak resets, so for every \(\ell\) and \(a\),
$$S_{n+1}^{\ell,0}\leftarrow S_{n+1}^{\ell,0}+S_n^{\ell,a}.$$
If we append \(A\), then the current streak must be shorter than 2, hence
$$S_{n+1}^{\ell,a+1}\leftarrow S_{n+1}^{\ell,a+1}+S_n^{\ell,a}\qquad (a=0,1).$$
If we append \(L\), then we must not have used a late day before, and the trailing absence count resets because the last symbol is no longer \(A\):
$$S_{n+1}^{1,0}\leftarrow S_{n+1}^{1,0}+S_n^{0,a}\qquad (a=0,1,2).$$
After \(n\) days, the total number of prize strings is
$$T_n=\sum_{\ell=0}^{1}\sum_{a=0}^{2} S_n^{\ell,a}.$$
This is the complete recurrence used by the implementations. Every loop iteration is just a redistribution of six counters.
There is also a convenient closed counting interpretation. Let \(F_n\) be the number of valid length-\(n\) strings that contain no \(L\) at all. Then only the trailing run of absences matters, and one obtains the Tribonacci-type recurrence
$$F_n=F_{n-1}+F_{n-2}+F_{n-3}\qquad (n\ge 3),$$
with initial values
$$F_0=1,\qquad F_1=2,\qquad F_2=4.$$
Now consider a prize string of length \(n\) that contains exactly one \(L\). If that \(L\) sits in position \(r\), then the prefix of length \(r-1\) and the suffix of length \(n-r\) must both be \(L\)-free valid strings, and they are independent because the \(L\) breaks any absence streak. Therefore
$$T_n=F_n+\sum_{r=1}^{n} F_{r-1}F_{n-r}.$$
The first term counts strings with no \(L\); the sum counts strings with exactly one \(L\). The code does not iterate with this formula directly, but it is a clean proof that the six-state DP is counting the right objects.
The no-late sequence begins
$$F_0=1,\qquad F_1=2,\qquad F_2=4,\qquad F_3=7,\qquad F_4=13.$$
So the strings of length 4 with exactly one \(L\) contribute
$$F_0F_3+F_1F_2+F_2F_1+F_3F_0=1\cdot 7+2\cdot 4+4\cdot 2+7\cdot 1=30.$$
Adding the \(L\)-free strings gives
$$T_4=13+30=43.$$
This matches the standard checkpoint for the problem and shows both constraints in action: the lone \(L\) can be placed anywhere, but the two surrounding pieces must independently avoid the forbidden pattern \(AAA\).
The C++, Python, and Java implementations store the six state counts in a \(2\times 3\) table. One dimension records whether a late day has been used, and the other records the current trailing absence run.
For each day, the implementation creates a fresh \(2\times 3\) table for the next layer, scans the current six counts, and distributes each count through the legal transitions for \(O\), \(A\), and \(L\). Once that redistribution is complete, the new table becomes the current table and the process continues.
After 30 iterations, the implementation sums all six terminal states. The update rule can be checked against the smaller case \(T_4=43\). Because the number of states is fixed and the target length is only 30, the whole computation fits comfortably in ordinary 64-bit integer arithmetic.
There are always exactly 6 states, and each state performs only constant work per day. For a record length of \(D\), the running time is therefore \(O(D)\).
The memory usage is \(O(1)\), because the implementation keeps only the current and next \(2\times 3\) tables. It does not need to store all earlier layers of the dynamic program.
Gesucht ist die Anzahl der Anwesenheitsfolgen der Länge 30 über \(\{O,A,L\}\), wobei \(O\) für pünktlich, \(A\) für abwesend und \(L\) für verspätet steht. Preiswürdig ist eine Folge genau dann, wenn sie insgesamt höchstens ein \(L\) enthält und nirgends drei aufeinanderfolgende \(A\)'s besitzt.
Die beiden Bedingungen haben unterschiedliche Reichweite. Die \(L\)-Bedingung ist global, weil ein verspäteter Tag nur einmal im ganzen Wort vorkommen darf. Die \(A\)-Bedingung ist lokal, weil für den nächsten Schritt nur die aktuelle Endserie aus Abwesenheiten relevant ist.
Deshalb merkt sich die Dynamik nicht die gesamte bisherige Folge, sondern nur die minimale Information, die für eine korrekte Fortsetzung nötig ist.
Für \(n \ge 0\) sei \(S_n^{\ell,a}\) die Anzahl gültiger Präfixe der Länge \(n\), wobei \(\ell \in \{0,1\}\) angibt, ob bereits ein verspäteter Tag verwendet wurde, und \(a \in \{0,1,2\}\) die Länge des aktuellen Endblocks aus aufeinanderfolgenden \(A\)'s ist.
Mehr muss man nicht wissen. Sobald feststeht, ob das einzige \(L\) schon verbraucht wurde und ob das Präfix mit 0, 1 oder 2 Abwesenheiten endet, ist die frühere Geschichte für die nächste Entscheidung irrelevant. Genau daraus entstehen \(2 \times 3 = 6\) Zustände.
Die Anfangsbedingung lautet
$$S_0^{0,0}=1,$$
während alle übrigen \(S_0^{\ell,a}\) gleich 0 sind. Das leere Wort ist also gültig, enthält kein \(L\) und endet nicht mit einer Abwesenheit.
Von jedem gültigen Zustand aus gibt es höchstens drei zulässige Erweiterungen.
Wird \(O\) angehängt, dann wird die Abwesenheitsserie zurückgesetzt. Für alle \(\ell\) und \(a\) gilt daher
$$S_{n+1}^{\ell,0}\leftarrow S_{n+1}^{\ell,0}+S_n^{\ell,a}.$$
Wird \(A\) angehängt, dann darf die bisherige Endserie nicht schon Länge 2 haben. Also
$$S_{n+1}^{\ell,a+1}\leftarrow S_{n+1}^{\ell,a+1}+S_n^{\ell,a}\qquad (a=0,1).$$
Wird \(L\) angehängt, dann darf zuvor noch kein \(L\) benutzt worden sein, und der Endblock von \(A\)'s endet ebenfalls:
$$S_{n+1}^{1,0}\leftarrow S_{n+1}^{1,0}+S_n^{0,a}\qquad (a=0,1,2).$$
Die Gesamtzahl preiswürdiger Folgen der Länge \(n\) ist dann
$$T_n=\sum_{\ell=0}^{1}\sum_{a=0}^{2} S_n^{\ell,a}.$$
Genau diese Rekursion wird in den Implementierungen ausgeführt. Jeder Schleifendurchlauf verteilt lediglich sechs Zähler neu.
Es gibt außerdem eine nützliche zweite Sichtweise. Sei \(F_n\) die Anzahl gültiger Folgen der Länge \(n\), die gar kein \(L\) enthalten. Dann bleibt nur noch die Länge des aktuellen \(A\)-Endblocks als Gedächtnis, und man erhält die tribonacciartige Rekursion
$$F_n=F_{n-1}+F_{n-2}+F_{n-3}\qquad (n\ge 3),$$
mit Anfangswerten
$$F_0=1,\qquad F_1=2,\qquad F_2=4.$$
Enthält eine preiswürdige Folge der Länge \(n\) genau ein \(L\), so stehe dieses an Position \(r\). Dann sind der linke Teil der Länge \(r-1\) und der rechte Teil der Länge \(n-r\) jeweils gültige \(L\)-freie Folgen. Sie sind unabhängig, weil das \(L\) jede mögliche \(A\)-Serie unterbricht. Daher gilt
$$T_n=F_n+\sum_{r=1}^{n} F_{r-1}F_{n-r}.$$
Der erste Summand zählt die Fälle ohne \(L\), die Summe die Fälle mit genau einem \(L\). So rechnet der Code nicht direkt, aber die Formel ist eine saubere Plausibilitätskontrolle für das 6-Zustands-DP.
Die Folge ohne \(L\) beginnt mit
$$F_0=1,\qquad F_1=2,\qquad F_2=4,\qquad F_3=7,\qquad F_4=13.$$
Damit tragen die Wörter der Länge 4 mit genau einem \(L\) den Wert
$$F_0F_3+F_1F_2+F_2F_1+F_3F_0=1\cdot 7+2\cdot 4+4\cdot 2+7\cdot 1=30$$
bei. Insgesamt folgt also
$$T_4=13+30=43.$$
Dieses kleine Beispiel ist ein guter Kontrollpunkt: Das einzelne \(L\) kann an jeder Position stehen, aber die beiden Teilstücke links und rechts davon müssen jeweils selbstständig die Bedingung gegen \(AAA\) erfüllen.
Die C++-, Python- und Java-Implementierungen speichern die sechs Zustandszahlen in einer \(2\times 3\)-Tabelle. Eine Dimension beschreibt, ob bereits ein verspäteter Tag verbraucht wurde, die andere die aktuelle Länge des Endblocks aus Abwesenheiten.
Für jeden Tag wird eine neue \(2\times 3\)-Tabelle aufgebaut. Alle aktuellen Zähler werden gelesen und gemäß den erlaubten Übergängen für \(O\), \(A\) und \(L\) in die nächste Tabelle übertragen. Anschließend ersetzt diese neue Tabelle die alte.
Nach 30 Schritten werden alle sechs Endzustände aufsummiert. Die Übergangslogik lässt sich an dem kleineren Kontrollwert \(T_4=43\) prüfen. Wegen der winzigen Zustandszahl und der kurzen Länge 30 genügt ganz normale 64-Bit-Ganzzahlarithmetik.
Es gibt stets genau 6 Zustände, und jeder Zustand verursacht pro Tag nur konstanten Aufwand. Für eine Länge \(D\) ergibt das eine Laufzeit von \(O(D)\).
Der Speicherbedarf ist \(O(1)\), weil nur die aktuelle und die nächste \(2\times 3\)-Tabelle gehalten werden. Frühere DP-Schichten müssen nicht gespeichert werden.
Aranan şey, \(\{O,A,L\}\) alfabesiyle yazılmış uzunluğu 30 olan devam çizelgelerinin sayısıdır. Burada \(O\) zamanında gelmeyi, \(A\) devamsızlığı, \(L\) geç kalmayı temsil eder. Bir kayıt ancak toplamda en fazla bir kez \(L\) içeriyorsa ve hiçbir yerde art arda üç \(A\) bulundurmuyorsa ödül almaya uygundur.
Bu iki kısıt aynı türden değildir. \(L\) kısıtı küreseldir; çünkü geç kalma hakkı bütün dizi boyunca yalnızca bir kez kullanılabilir. \(A\) kısıtı ise yereldir; çünkü yeni bir \(A\)'nın yasak olup olmadığını belirlemek için yalnızca sondaki devamsızlık kuyruğunu bilmek yeterlidir.
Bu yüzden çözüm bütün geçmişi değil, bir sonraki güne geçerken gerçekten gerekli olan en küçük durumu tutar.
\(n \ge 0\) için \(S_n^{\ell,a}\), uzunluğu \(n\) olan geçerli ön eklerin sayısı olsun. Burada \(\ell \in \{0,1\}\), şimdiye kadar bir geç kalma günü kullanılıp kullanılmadığını; \(a \in \{0,1,2\}\) ise sonda bulunan ardışık devamsızlık sayısını göstersin.
Bundan daha fazla bilgiye ihtiyaç yoktur. Tek \(L\)'nin kullanılıp kullanılmadığını ve son kısmın 0, 1 ya da 2 tane ardışık \(A\) ile bitip bitmediğini biliyorsak, daha eski harflerin tamamı bir sonraki adım açısından önemsiz hale gelir. Böylece tam olarak \(2 \times 3 = 6\) durum elde edilir.
Başlangıç koşulu
$$S_0^{0,0}=1$$
şeklindedir; diğer tüm \(S_0^{\ell,a}\) değerleri 0'dır. Boş dizi geçerlidir, henüz \(L\) kullanılmamıştır ve ardışık \(A\) kuyruğu yoktur.
Geçerli bir durumdan en fazla üç yasal uzatma vardır.
Sonuna \(O\) eklenirse devamsızlık kuyruğu sıfırlanır. Dolayısıyla tüm \(\ell\) ve \(a\) için
$$S_{n+1}^{\ell,0}\leftarrow S_{n+1}^{\ell,0}+S_n^{\ell,a}.$$
Sonuna \(A\) eklenirse mevcut kuyruğun uzunluğu 2'den küçük olmalıdır. Bu nedenle
$$S_{n+1}^{\ell,a+1}\leftarrow S_{n+1}^{\ell,a+1}+S_n^{\ell,a}\qquad (a=0,1).$$
Sonuna \(L\) eklenirse daha önce hiç \(L\) kullanılmamış olmalıdır ve aynı anda ardışık \(A\) sayısı da sıfırlanır:
$$S_{n+1}^{1,0}\leftarrow S_{n+1}^{1,0}+S_n^{0,a}\qquad (a=0,1,2).$$
Böylece uzunluğu \(n\) olan ödül dizilerinin toplamı
$$T_n=\sum_{\ell=0}^{1}\sum_{a=0}^{2} S_n^{\ell,a}$$
olur. C++, Python ve Java uygulamalarının doğrudan yaptığı şey tam olarak bu altı sayacı güncellemekten ibarettir.
Aynı sayımın daha kapalı bir formu da vardır. \(F_n\), hiç \(L\) içermeyen geçerli uzunluk-\(n\) kayıtlarının sayısı olsun. Bu durumda yalnızca sondaki \(A\) kuyruğunu izleriz ve
$$F_n=F_{n-1}+F_{n-2}+F_{n-3}\qquad (n\ge 3)$$
reküransı elde edilir. Başlangıç değerleri
$$F_0=1,\qquad F_1=2,\qquad F_2=4$$
şeklindedir. Bu, altı durumlu DP'nin içinde saklı duran Tribonacci tipi dizidir.
Şimdi uzunluğu \(n\) olan ve tam bir tane \(L\) içeren ödül dizisini düşünelim. \(L\) harfi \(r\). konumdaysa, solda kalan \(r-1\) uzunluklu parça ile sağda kalan \(n-r\) uzunluklu parça birbirinden bağımsız iki geçerli \(L\)-siz dizi olmalıdır; çünkü aradaki \(L\), devamsızlık serisini keser. Bu yüzden
$$T_n=F_n+\sum_{r=1}^{n} F_{r-1}F_{n-r}.$$
İlk terim hiç \(L\) içermeyen kayıtları, toplam ise tam bir \(L\) içeren kayıtları sayar. Kod bu formülle iterasyon yapmaz, ama formül sayımın neden doğru olduğunu açıklayan güçlü bir kontrol eşitliğidir.
\(L\)-siz dizi sayıları şöyle başlar:
$$F_0=1,\qquad F_1=2,\qquad F_2=4,\qquad F_3=7,\qquad F_4=13.$$
Dolayısıyla uzunluğu 4 olan ve tam bir tane \(L\) içeren kayıtların katkısı
$$F_0F_3+F_1F_2+F_2F_1+F_3F_0=1\cdot 7+2\cdot 4+4\cdot 2+7\cdot 1=30$$
olur. Sonuçta
$$T_4=13+30=43.$$
Bu küçük örnek, problemde kullanılan doğrulama noktasıdır. Tek \(L\) farklı yerlere yerleştirilebilir; ancak sol ve sağ parçaların her biri kendi içinde \(AAA\) deseninden kaçınmak zorundadır.
C++, Python ve Java uygulamaları altı durumu bir \(2\times 3\) tabloda tutar. Bir eksen geç kalma hakkının kullanılıp kullanılmadığını, diğer eksen ise mevcut ardışık devamsızlık uzunluğunu gösterir.
Her gün için yeni bir \(2\times 3\) tablo oluşturulur. Mevcut altı hücre okunur ve her hücredeki sayı, izin verilen \(O\), \(A\) ve \(L\) geçişlerine dağıtılır. Bu dağıtım tamamlanınca yeni tablo, mevcut tabloyun yerine geçer.
30 gün sonunda tüm son durumlar toplanır. Geçiş mantığı, daha küçük olan \(T_4=43\) örneğiyle kontrol edilebilir. Durum sayısı sabit ve hedef uzunluk küçük olduğu için hesaplama rahatlıkla 64 bit tam sayılarla yapılır.
Her zaman tam 6 durum vardır ve her durum günde sabit sayıda işlem üretir. Uzunluk \(D\) için zaman karmaşıklığı bu nedenle \(O(D)\)'dir.
Bellek kullanımı \(O(1)\)'dir; çünkü sadece mevcut ve bir sonraki \(2\times 3\) tablo saklanır. Önceki bütün DP katmanlarını tutmaya gerek yoktur.
Buscamos el número de registros de asistencia de longitud 30 sobre \(\{O,A,L\}\), donde \(O\) significa puntual, \(A\) ausente y \(L\) tarde. Un registro recibe premio si contiene como máximo una \(L\) en total y nunca contiene tres \(A\) consecutivas.
Las dos restricciones no se controlan de la misma forma. La condición sobre \(L\) es global, porque solo puede aparecer una vez en toda la cadena. La condición sobre \(A\) es local, porque para decidir si una nueva ausencia es válida solo importa la racha final actual.
Por eso la solución no memoriza toda la historia, sino únicamente la información mínima que todavía puede afectar al día siguiente.
Para \(n \ge 0\), sea \(S_n^{\ell,a}\) el número de prefijos válidos de longitud \(n\), donde \(\ell \in \{0,1\}\) indica si ya se usó un día tarde, y \(a \in \{0,1,2\}\) es el número de ausencias consecutivas al final del prefijo.
Eso basta para describir el futuro. Una vez que sabemos si el único \(L\) ya apareció y si la cadena termina con 0, 1 o 2 ausencias seguidas, el resto del pasado ya no influye en ninguna extensión legal. De ahí salen exactamente \(2 \times 3 = 6\) estados.
La condición inicial es
$$S_0^{0,0}=1,$$
y todos los demás \(S_0^{\ell,a}\) valen 0, porque la cadena vacía es válida, no ha usado ningún \(L\) y no termina con ausencias.
Desde un estado válido existen como mucho tres extensiones legales.
Si añadimos \(O\), la racha de ausencias se reinicia. Entonces, para todo \(\ell\) y \(a\),
$$S_{n+1}^{\ell,0}\leftarrow S_{n+1}^{\ell,0}+S_n^{\ell,a}.$$
Si añadimos \(A\), la racha actual debe tener longitud menor que 2. Por tanto,
$$S_{n+1}^{\ell,a+1}\leftarrow S_{n+1}^{\ell,a+1}+S_n^{\ell,a}\qquad (a=0,1).$$
Si añadimos \(L\), entonces todavía no se puede haber usado ningún retraso, y la racha de \(A\)'s también se rompe:
$$S_{n+1}^{1,0}\leftarrow S_{n+1}^{1,0}+S_n^{0,a}\qquad (a=0,1,2).$$
El número total de cadenas premiadas de longitud \(n\) es
$$T_n=\sum_{\ell=0}^{1}\sum_{a=0}^{2} S_n^{\ell,a}.$$
Esta es exactamente la recurrencia que implementan los tres programas. Cada iteración del bucle solo redistribuye seis contadores.
También hay una descripción cerrada muy útil. Sea \(F_n\) el número de cadenas válidas de longitud \(n\) que no contienen ninguna \(L\). Entonces solo hace falta seguir la racha final de ausencias, y aparece la recurrencia de tipo Tribonacci
$$F_n=F_{n-1}+F_{n-2}+F_{n-3}\qquad (n\ge 3),$$
con valores iniciales
$$F_0=1,\qquad F_1=2,\qquad F_2=4.$$
Ahora tomemos una cadena premiada de longitud \(n\) con exactamente una \(L\). Si esa \(L\) está en la posición \(r\), la parte izquierda de longitud \(r-1\) y la parte derecha de longitud \(n-r\) deben ser dos cadenas válidas sin \(L\). Son independientes porque la \(L\) rompe cualquier racha de ausencias. Por eso
$$T_n=F_n+\sum_{r=1}^{n} F_{r-1}F_{n-r}.$$
El primer término cuenta las cadenas sin retrasos; la suma cuenta las cadenas con exactamente un retraso. El código no itera con esta fórmula, pero sí explica por qué el modelo de seis estados es completo.
La sucesión sin \(L\) empieza como
$$F_0=1,\qquad F_1=2,\qquad F_2=4,\qquad F_3=7,\qquad F_4=13.$$
Así, las cadenas de longitud 4 con exactamente una \(L\) aportan
$$F_0F_3+F_1F_2+F_2F_1+F_3F_0=1\cdot 7+2\cdot 4+4\cdot 2+7\cdot 1=30.$$
Al sumar las cadenas sin \(L\), obtenemos
$$T_4=13+30=43.$$
Este caso pequeño es un buen control: la \(L\) única puede colocarse en cualquier posición, pero las dos partes que deja a cada lado deben evitar por separado el patrón prohibido \(AAA\).
Las implementaciones en C++, Python y Java guardan los seis recuentos de estado en una tabla \(2\times 3\). Una dimensión indica si ya se usó el retraso, y la otra registra la longitud de la racha final de ausencias.
Para cada día se construye una nueva tabla \(2\times 3\). Después se recorren las seis celdas actuales y cada valor se distribuye entre las transiciones legales correspondientes a \(O\), \(A\) y \(L\). Al terminar, la tabla nueva reemplaza a la anterior.
Tras 30 iteraciones, basta con sumar los seis estados finales. La lógica de actualización puede verificarse con el valor menor \(T_4=43\). Dado que el número de estados es fijo y la longitud buscada es pequeña, el cálculo entra sin problemas en enteros con signo de 64 bits.
Siempre existen exactamente 6 estados, y cada uno produce solo trabajo constante por día. Para una longitud \(D\), el tiempo total es \(O(D)\).
La memoria es \(O(1)\), porque solo se conservan la tabla actual y la siguiente, ambas de tamaño \(2\times 3\). No hace falta almacenar todas las capas anteriores del DP.
题目要求统计长度为 30 的出勤记录数量，字符集为 \(\{O,A,L\}\)。其中 \(O\) 表示按时到场，\(A\) 表示缺席，\(L\) 表示迟到。一个记录要获得奖励，必须同时满足两个条件：整串中至多出现一次 \(L\)，并且任何位置都不能出现连续三个 \(A\)。
这两个限制的性质并不相同。关于 \(L\) 的限制是全局性的，因为整条记录里只允许用掉一次迟到名额；关于 \(A\) 的限制则是局部性的，因为判断下一天还能不能写 \(A\)，只需要知道当前结尾已经连续出现了多少个 \(A\)。
因此最自然的做法不是记住完整前缀，而是只保留那些会影响下一步合法性的最小状态信息。
对 \(n \ge 0\)，记 \(S_n^{\ell,a}\) 为长度为 \(n\) 的合法前缀数量，其中 \(\ell \in \{0,1\}\) 表示是否已经出现过一次迟到，\(a \in \{0,1,2\}\) 表示前缀末尾连续缺席的个数。
这已经是完整状态。只要知道唯一的一次 \(L\) 是否已经用过，以及当前后缀是否以 0 个、1 个或 2 个连续的 \(A\) 结尾，之前更早的历史就不会再影响下一天的选择。所以总状态数正好是 \(2 \times 3 = 6\)。
初始条件为
$$S_0^{0,0}=1,$$
其余所有 \(S_0^{\ell,a}\) 都等于 0。原因很简单：空串是合法的，没有使用过迟到，而且末尾也没有连续缺席。
从一个合法状态出发，最多只有三种合法扩展。
如果追加 \(O\)，那么连续缺席段被清空，因此对所有 \(\ell\) 和 \(a\)，都有
$$S_{n+1}^{\ell,0}\leftarrow S_{n+1}^{\ell,0}+S_n^{\ell,a}.$$
如果追加 \(A\)，那么当前连续缺席数必须小于 2，所以
$$S_{n+1}^{\ell,a+1}\leftarrow S_{n+1}^{\ell,a+1}+S_n^{\ell,a}\qquad (a=0,1).$$
如果追加 \(L\)，则此前不能已经用过迟到，并且因为末尾字符不再是 \(A\)，连续缺席数也会归零：
$$S_{n+1}^{1,0}\leftarrow S_{n+1}^{1,0}+S_n^{0,a}\qquad (a=0,1,2).$$
于是长度为 \(n\) 的全部奖励记录总数就是
$$T_n=\sum_{\ell=0}^{1}\sum_{a=0}^{2} S_n^{\ell,a}.$$
这正是三个实现真正执行的递推。每一天的更新，本质上只是把 6 个计数器重新分配到下一层。
同一个问题还有一个很有解释力的拆分。设 \(F_n\) 表示长度为 \(n\)、且完全不含 \(L\) 的合法记录数。此时状态里只剩下“末尾连续 \(A\) 的长度”这一件事，于是得到一个 Tribonacci 型递推：
$$F_n=F_{n-1}+F_{n-2}+F_{n-3}\qquad (n\ge 3),$$
初值为
$$F_0=1,\qquad F_1=2,\qquad F_2=4.$$
再看长度为 \(n\) 且恰好有一个 \(L\) 的奖励记录。如果这唯一的 \(L\) 出现在第 \(r\) 个位置，那么它左边长度为 \(r-1\) 的部分与右边长度为 \(n-r\) 的部分，都必须是合法的无 \(L\) 记录，而且二者彼此独立，因为中间这个 \(L\) 会把任何连续缺席段截断。于是有
$$T_n=F_n+\sum_{r=1}^{n} F_{r-1}F_{n-r}.$$
第一项统计没有 \(L\) 的情形，求和项统计恰好有一个 \(L\) 的情形。程序并不是按这个式子逐项计算的，但这个式子非常适合作为对六状态 DP 的数学校验。
无 \(L\) 记录数列开头是
$$F_0=1,\qquad F_1=2,\qquad F_2=4,\qquad F_3=7,\qquad F_4=13.$$
所以长度为 4 且恰好含一个 \(L\) 的记录总数为
$$F_0F_3+F_1F_2+F_2F_1+F_3F_0=1\cdot 7+2\cdot 4+4\cdot 2+7\cdot 1=30.$$
再加上不含 \(L\) 的 13 个记录，就得到
$$T_4=13+30=43.$$
这个小例子正好是常用校验值。它清楚展示了两条限制如何配合：唯一的 \(L\) 可以插在任何位置，但左右两段都必须各自避免出现 \(AAA\)。
C++、Python 和 Java 实现都把 6 个状态计数放在一个 \(2\times 3\) 的表里。一维表示是否已经使用迟到名额，另一维表示当前末尾连续缺席的长度。
每处理一天，就新建下一层的 \(2\times 3\) 表，然后扫描当前 6 个状态，把每个计数按照 \(O\)、\(A\)、\(L\) 三种合法转移分发到新表中。分发结束后，新表取代旧表，进入下一天。
经过 30 次迭代后，把 6 个终止状态全部相加即可。更新规则可以用较小的案例 \(T_4=43\) 来核对。由于状态数固定而且目标长度只有 30，整个计算完全可以放在普通的 64 位有符号整数范围内。
状态数始终固定为 6，每个状态在每一天只做常数次转移，因此对于长度 \(D\) 的记录，总时间复杂度是 \(O(D)\)。
空间复杂度是 \(O(1)\)，因为实现只保留当前层和下一层这两个 \(2\times 3\) 表，不需要把所有历史层都存下来。
Нужно подсчитать число строк посещаемости длины 30 над алфавитом \(\{O,A,L\}\), где \(O\) означает «вовремя», \(A\) означает «отсутствовал», а \(L\) означает «опоздал». Строка считается призовой, если в ней не более одного символа \(L\) и нигде не встречается три подряд идущих \(A\).
Эти два ограничения устроены по-разному. Ограничение на \(L\) глобальное, потому что опоздание можно использовать только один раз во всей записи. Ограничение на \(A\) локальное, потому что для следующего шага важна только длина текущего хвоста из отсутствий.
Поэтому решение запоминает не всю историю, а только ту информацию, которая действительно влияет на допустимые продолжения.
Для \(n \ge 0\) обозначим через \(S_n^{\ell,a}\) число корректных префиксов длины \(n\), где \(\ell \in \{0,1\}\) показывает, использовано ли уже опоздание, а \(a \in \{0,1,2\}\) равен длине текущего суффикса из подряд идущих \(A\).
Этого достаточно. Если известно, была ли уже потрачена единственная буква \(L\), и заканчивается ли префикс на 0, 1 или 2 символа \(A\), то более ранняя часть строки уже не влияет на законность следующего символа. Отсюда и возникают ровно \(2 \times 3 = 6\) состояний.
Начальное условие имеет вид
$$S_0^{0,0}=1,$$
а все остальные \(S_0^{\ell,a}\) равны нулю, поскольку пустая строка корректна, не содержит \(L\) и не заканчивается отсутствиями.
Из любого корректного состояния есть не более трех допустимых продолжений.
Если приписать \(O\), хвост из отсутствий обнуляется, и потому для любых \(\ell\) и \(a\)
$$S_{n+1}^{\ell,0}\leftarrow S_{n+1}^{\ell,0}+S_n^{\ell,a}.$$
Если приписать \(A\), то текущий хвост должен иметь длину меньше 2, значит
$$S_{n+1}^{\ell,a+1}\leftarrow S_{n+1}^{\ell,a+1}+S_n^{\ell,a}\qquad (a=0,1).$$
Если приписать \(L\), то раньше опоздания быть не должно, а хвост из \(A\) тоже обрывается:
$$S_{n+1}^{1,0}\leftarrow S_{n+1}^{1,0}+S_n^{0,a}\qquad (a=0,1,2).$$
Тогда общее число призовых строк длины \(n\) равно
$$T_n=\sum_{\ell=0}^{1}\sum_{a=0}^{2} S_n^{\ell,a}.$$
Именно эта рекуррентная схема и реализована в программах. На каждом шаге просто перераспределяются шесть счетчиков.
Есть и более сжатая формула. Обозначим через \(F_n\) число корректных строк длины \(n\), в которых нет ни одной \(L\). Тогда остается отслеживать только длину конечного блока из \(A\), и получается рекурсия типа Tribonacci:
$$F_n=F_{n-1}+F_{n-2}+F_{n-3}\qquad (n\ge 3),$$
с начальными значениями
$$F_0=1,\qquad F_1=2,\qquad F_2=4.$$
Теперь возьмем призовую строку длины \(n\) с ровно одной буквой \(L\). Если она стоит в позиции \(r\), то левая часть длины \(r-1\) и правая часть длины \(n-r\) должны быть корректными строками без \(L\). Эти части независимы, потому что буква \(L\) разрывает любую последовательность отсутствий. Поэтому
$$T_n=F_n+\sum_{r=1}^{n} F_{r-1}F_{n-r}.$$
Первое слагаемое считает строки без опозданий, а сумма считает строки с единственным опозданием. Код не использует эту формулу как основной цикл, но она отлично объясняет правильность модели из шести состояний.
Последовательность без \(L\) начинается так:
$$F_0=1,\qquad F_1=2,\qquad F_2=4,\qquad F_3=7,\qquad F_4=13.$$
Следовательно, строки длины 4 с ровно одним \(L\) дают вклад
$$F_0F_3+F_1F_2+F_2F_1+F_3F_0=1\cdot 7+2\cdot 4+4\cdot 2+7\cdot 1=30.$$
После добавления 13 строк без \(L\) получаем
$$T_4=13+30=43.$$
Этот маленький пример является удобной проверкой. Единственную букву \(L\) можно поставить в любое место, но обе части по ее сторонам обязаны самостоятельно избегать запрещенного шаблона \(AAA\).
Реализации на C++, Python и Java хранят шесть чисел состояний в таблице \(2\times 3\). Одно измерение отвечает за факт использования опоздания, другое за длину текущего хвоста из подряд идущих отсутствий.
Для каждого дня создается новая таблица \(2\times 3\). Затем просматриваются все шесть текущих состояний, и каждое значение переносится в следующие клетки согласно допустимым переходам для \(O\), \(A\) и \(L\). После этого новая таблица становится текущей.
После 30 итераций программа суммирует все шесть конечных состояний. Логику переходов удобно проверять на меньшем значении \(T_4=43\). Поскольку число состояний постоянно, а длина строки мала, вся арифметика спокойно помещается в стандартные 64-битные целые.
Состояний всегда ровно 6, и на каждом дне каждое из них выполняет только постоянное число действий. Поэтому для длины \(D\) время работы равно \(O(D)\).
Память имеет порядок \(O(1)\), потому что хранятся только текущая и следующая таблицы \(2\times 3\). Все предыдущие слои динамики держать не нужно.
نريد عدَّ جميع سجلات الحضور ذات الطول 30 والمكوَّنة من الرموز \(\{O,A,L\}\). يرمز \(O\) إلى الحضور في الوقت، و\(A\) إلى الغياب، و\(L\) إلى التأخر. ويكون السجل مستحقًا للجائزة إذا احتوى في المجموع على \(L\) واحد على الأكثر، ولم يظهر فيه النمط \(AAA\) في أي موضع.
القيدان هنا مختلفان في طبيعتهما. قيد \(L\) قيدٌ شامل على السلسلة كلها، لأن التأخر مسموح مرة واحدة فقط. أما قيد \(A\) فهو قيد محلي، لأن قرار إضافة \(A\) جديد يعتمد فقط على طول ذيل الغيابات المتتالية في نهاية السلسلة الحالية.
لهذا السبب لا يحتاج الحل إلى تذكّر السجل كله، بل يكتفي بالمعلومات الدنيا التي لا يزال لها أثر في اليوم التالي.
لـ \(n \ge 0\)، لنعرّف \(S_n^{\ell,a}\) على أنه عدد البوادئ الصحيحة ذات الطول \(n\)، حيث \(\ell \in \{0,1\}\) يحدد ما إذا كان قد استُخدم يوم تأخر من قبل، و\(a \in \{0,1,2\}\) هو عدد الغيابات المتتالية في نهاية البادئة.
وهذه المعلومات كافية تمامًا. فإذا عرفنا هل استُهلكت الـ \(L\) الوحيدة أم لا، وعرفنا هل تنتهي السلسلة الحالية بـ 0 أو 1 أو 2 من \(A\) المتتالية، فلن تعود التفاصيل الأقدم مؤثرة في الامتدادات المسموح بها. ومن هنا نحصل على \(2 \times 3 = 6\) حالات فقط.
شرط البداية هو
$$S_0^{0,0}=1,$$
وجميع القيم الأخرى \(S_0^{\ell,a}\) تساوي صفرًا، لأن السلسلة الفارغة صحيحة، ولم يُستخدم فيها أي تأخر، ولا تنتهي بذيل غياب.
من أي حالة صحيحة توجد ثلاث امتدادات قانونية على الأكثر.
إذا أضفنا \(O\)، فإن سلسلة الغيابات المتتالية تُصفَّر، ولذلك لكل \(\ell\) و\(a\) لدينا
$$S_{n+1}^{\ell,0}\leftarrow S_{n+1}^{\ell,0}+S_n^{\ell,a}.$$
وإذا أضفنا \(A\)، فيجب أن يكون طول الذيل الحالي أصغر من 2، ومن ثم
$$S_{n+1}^{\ell,a+1}\leftarrow S_{n+1}^{\ell,a+1}+S_n^{\ell,a}\qquad (a=0,1).$$
أما إذا أضفنا \(L\)، فلا بد من ألا تكون \(L\) قد استُخدمت سابقًا، كما أن ذيل الغياب ينقطع لأن الرمز الأخير لم يعد \(A\):
$$S_{n+1}^{1,0}\leftarrow S_{n+1}^{1,0}+S_n^{0,a}\qquad (a=0,1,2).$$
وعندئذ يكون عدد السجلات المستحقة للجائزة بطول \(n\) هو
$$T_n=\sum_{\ell=0}^{1}\sum_{a=0}^{2} S_n^{\ell,a}.$$
وهذا هو بالضبط التكرار الذي تنفذه تطبيقات C++ وPython وJava. كل دورة من الحلقة لا تفعل أكثر من إعادة توزيع ستة عدادات.
هناك أيضًا صياغة مغلقة مفيدة جدًا. لنعرّف \(F_n\) بأنه عدد السجلات الصحيحة ذات الطول \(n\) التي لا تحتوي أي \(L\) مطلقًا. حينها لا يبقى من الذاكرة إلا طول ذيل الغيابات، فنحصل على علاقة من نوع Tribonacci:
$$F_n=F_{n-1}+F_{n-2}+F_{n-3}\qquad (n\ge 3),$$
مع القيم الابتدائية
$$F_0=1,\qquad F_1=2,\qquad F_2=4.$$
الآن خذ سجلًا جائزًا بطول \(n\) يحتوي \(L\) واحدة بالضبط. إذا وُضعت هذه \(L\) في الموضع \(r\)، فإن الجزء الأيسر بطول \(r-1\) والجزء الأيمن بطول \(n-r\) يجب أن يكونا سجلين صحيحين من دون \(L\). وهذان الجزءان مستقلان لأن \(L\) تقطع أي سلسلة من الغيابات المتتالية. لذلك نحصل على
$$T_n=F_n+\sum_{r=1}^{n} F_{r-1}F_{n-r}.$$
الحد الأول يعدّ السجلات الخالية من التأخر، والمجموع يعدّ السجلات التي تحتوي تأخرًا واحدًا بالضبط. لا تنفذ الشيفرة هذا المجموع مباشرة، لكنه تفسير رياضي واضح لسبب كفاية نموذج الحالات الست.
تبدأ متتالية السجلات الخالية من \(L\) كما يلي:
$$F_0=1,\qquad F_1=2,\qquad F_2=4,\qquad F_3=7,\qquad F_4=13.$$
إذن مساهمة السجلات ذات الطول 4 والتي تحتوي \(L\) واحدة بالضبط هي
$$F_0F_3+F_1F_2+F_2F_1+F_3F_0=1\cdot 7+2\cdot 4+4\cdot 2+7\cdot 1=30.$$
وبإضافة السجلات الخالية من \(L\) نحصل على
$$T_4=13+30=43.$$
هذا المثال الصغير هو نقطة تحقق معروفة للمسألة. يمكن وضع \(L\) الوحيدة في أي مكان، لكن الجزأين المحيطين بها يجب أن يتجنبا كلٌ على حدة النمط الممنوع \(AAA\).
تخزن تطبيقات C++ وPython وJava الحالات الست في جدول \(2\times 3\). أحد البعدين يسجل ما إذا كان يوم التأخر قد استُخدم، والبعد الآخر يسجل طول ذيل الغيابات المتتالية الحالي.
في كل يوم تُنشئ الشيفرة جدولًا جديدًا للحالة التالية، ثم تمر على الخلايا الست الحالية وتوزع كل قيمة على الانتقالات القانونية المرتبطة بـ \(O\) و\(A\) و\(L\). وبعد انتهاء التوزيع يصبح الجدول الجديد هو الجدول الحالي.
بعد 30 خطوة، تجمع الشيفرة الحالات النهائية الست كلها. ويمكن فحص صحة التحديث بمقارنة النتيجة في الحالة الأصغر \(T_4=43\). وبما أن عدد الحالات ثابت وطول السلسلة صغير، فإن الحساب كله يبقى ضمن مجال الأعداد الصحيحة ذات 64 بت.
يوجد دائمًا 6 حالات فقط، وكل حالة تتطلب عملاً ثابتًا في كل يوم. لذلك إذا كان طول السجل \(D\)، فإن الزمن الكلي هو \(O(D)\).
أما الذاكرة فهي \(O(1)\)، لأن التنفيذ يحتفظ فقط بجدولي الحالة الحالية والحالة التالية، وكلاهما بحجم \(2\times 3\). لا حاجة إلى تخزين جميع طبقات البرمجة الديناميكية السابقة.