The required quantity for Problem 709 is the value on the right edge of the Entringer triangle at row \(n=24680\), reduced modulo \(1020202009\). Equivalently, the implementations are computing the \(n\)-th Euler zigzag number in its Entringer refinement. The main challenge is therefore not direct enumeration, but finding a recurrence that produces the same sequence with a much smaller state space.
The fast method is built around the classical Entringer triangle. A small reference dynamic program can still be used for tiny sizes, but the production solver replaces the expensive binomial transition with a compact row-by-row recurrence.
For a small sanity check one may keep a state indexed by a positive integer \(r\), starting from one active state at size \(1\). When the size increases by one, the reference transition is
$$D_{k+1}(r')=\sum_{\substack{r\ge 1,\ 0\le t\le r \\ t\equiv 0\pmod{2} \\ r'=r-t+1}} D_k(r)\binom{r}{t}.$$
The total count at size \(k\) is then
$$T_k=\sum_{r\ge 1} D_k(r).$$
This auxiliary computation already gives the checkpoints
$$T_4=5,\qquad T_8=1385.$$
Those are exactly the values produced by the Euler zigzag sequence at the same indices, which is the clue that the larger state space can be collapsed to Entringer numbers.
Define numbers \(E(r,k)\) for \(0\le k\le r\) by the boundary conditions
$$E(0,0)=1,\qquad E(r,0)=0\quad (r\ge 1),$$
and the recurrence
$$E(r,k)=E(r,k-1)+E(r-1,r-k)\qquad (1\le k\le r).$$
Each row is therefore formed by reading the previous row in reverse order and taking prefix sums. All computations are performed modulo
$$M=1020202009.$$
The desired value is the rightmost entry of row \(n\):
$$A_n=E(n,n).$$
Because the recurrence adds one reversed entry from the previous row at each step, the last entry of row \(r\) is the sum of the whole preceding row:
$$E(r,r)=\sum_{j=0}^{r-1} E(r-1,j).$$
This is why the right edge reproduces the Euler zigzag sequence
$$1,1,1,2,5,16,61,\dots$$
The full triangle refines the sequence, while the problem only asks for the final value on the right boundary.
Starting from the base row
$$[1],$$
the recurrence generates
$$\begin{aligned} r=1&:& [0,1],\\ r=2&:& [0,1,1],\\ r=3&:& [0,1,2,2],\\ r=4&:& [0,2,4,5,5]. \end{aligned}$$
Hence
$$E(4,4)=5,$$
which matches the small verification. Continuing the same construction to row \(8\) yields
$$E(8,8)=1385,$$
the second checkpoint used by the implementation.
The reference transition involves many binomial coefficients and many candidate state values \(r\). The Entringer triangle compresses that information into a two-parameter table with a purely additive update. This replacement is mathematically natural because the small-size totals coincide with classical Euler zigzag values, and the Entringer triangle is the standard refinement behind that sequence. Once the identification is made, the binomial transition is only needed as a tiny checker, not as the main solver.
The C++, Python, and Java implementations all follow the same optimized plan. They store only two rows of the triangle, initialize the base case \(E(0,0)=1\), and iterate from row \(1\) up to row \(n\). Inside a row, the first entry is set to \(0\), and each later entry is obtained by adding the previous entry in the current row to the mirrored entry from the previous row:
$$E(r,k)=E(r,k-1)+E(r-1,r-k)\pmod{M}.$$
After completing a row, the two row buffers are swapped and reused. The C++ implementation also includes a tiny reference dynamic program based on the even-binomial transition above, and it cross-checks the optimized triangle on small cases such as \(n=8\) and \(n=12\). The reported result is the final right-edge value \(E(n,n)\).
Row \(r\) performs exactly \(r\) updates, so the total amount of work is
$$\sum_{r=1}^{n} r=\frac{n(n+1)}{2}=O(n^2).$$
Only two rows of length \(n+1\) are stored, so the memory usage is \(O(n)\). Each inner-loop step uses one modular addition and, when needed, one subtraction, which keeps the implementation simple and efficient.
Die gesuchte Groesse fuer Problem 709 ist der Wert am rechten Rand des Entringer-Dreiecks in Zeile \(n=24680\), reduziert modulo \(1020202009\). Gleichbedeutend berechnen die Implementierungen die \(n\)-te Euler-Zickzack-Zahl in ihrer Entringer-Verfeinerung. Die eigentliche Aufgabe ist also nicht direkte Enumeration, sondern eine Rekursion zu finden, die dieselbe Folge mit deutlich kleinerem Zustandsraum erzeugt.
Die schnelle Methode basiert auf dem klassischen Entringer-Dreieck. Fuer sehr kleine Groessen kann man zwar noch ein Referenz-DP verwenden, aber der eigentliche Solver ersetzt die teure Binomialtransition durch eine kompakte zeilenweise Rekursion.
Als kleiner Plausibilitaetstest kann man einen Zustand mit positivem Index \(r\) fuehren und bei Groesse \(1\) mit genau einem aktiven Zustand starten. Beim Uebergang auf die naechste Groesse lautet die Referenztransition
$$D_{k+1}(r')=\sum_{\substack{r\ge 1,\ 0\le t\le r \\ t\equiv 0\pmod{2} \\ r'=r-t+1}} D_k(r)\binom{r}{t}.$$
Die Gesamtzahl bei Groesse \(k\) ist dann
$$T_k=\sum_{r\ge 1} D_k(r).$$
Diese Hilfsrechnung liefert bereits die Kontrollwerte
$$T_4=5,\qquad T_8=1385.$$
Genau dieselben Werte treten in der Euler-Zickzack-Folge an denselben Stellen auf. Das ist der Hinweis darauf, dass sich der groessere Zustandsraum auf Entringer-Zahlen komprimieren laesst.
Definiere Zahlen \(E(r,k)\) fuer \(0\le k\le r\) durch die Randbedingungen
$$E(0,0)=1,\qquad E(r,0)=0\quad (r\ge 1),$$
und die Rekursion
$$E(r,k)=E(r,k-1)+E(r-1,r-k)\qquad (1\le k\le r).$$
Jede Zeile entsteht also, indem man die vorherige Zeile rueckwaerts liest und davon Praefixsummen bildet. Alle Rechnungen erfolgen modulo
$$M=1020202009.$$
Gesucht ist der rechte Randwert der Zeile \(n\):
$$A_n=E(n,n).$$
Da die Rekursion in jedem Schritt genau einen rueckwaerts gelesenen Eintrag der vorherigen Zeile addiert, ist der letzte Eintrag von Zeile \(r\) die Summe der gesamten Zeile \(r-1\):
$$E(r,r)=\sum_{j=0}^{r-1} E(r-1,j).$$
Deshalb reproduziert die rechte Kante die Euler-Zickzack-Folge
$$1,1,1,2,5,16,61,\dots$$
Das volle Dreieck ist also eine Verfeinerung der Folge, waehrend das Problem nur den Endwert am rechten Rand braucht.
Ausgehend von der Startzeile
$$[1],$$
erzeugt die Rekursion nacheinander
$$\begin{aligned} r=1&:& [0,1],\\ r=2&:& [0,1,1],\\ r=3&:& [0,1,2,2],\\ r=4&:& [0,2,4,5,5]. \end{aligned}$$
Damit folgt
$$E(4,4)=5,$$
genau wie im kleinen Test. Fuehrt man denselben Aufbau bis Zeile \(8\) fort, erhaelt man
$$E(8,8)=1385,$$
den zweiten Kontrollwert der Implementierung.
Die Referenztransition enthaelt viele Binomialkoeffizienten und viele moegliche Zustandswerte \(r\). Das Entringer-Dreieck komprimiert diese Information in eine Tabelle mit zwei Parametern und rein additiven Updates. Dieser Ersatz ist mathematisch natürlich, weil die kleinen Kontrollwerte mit den klassischen Euler-Zickzack-Zahlen uebereinstimmen und das Entringer-Dreieck genau die Standardverfeinerung dieser Folge ist. Nach dieser Identifikation braucht man die Binomialtransition nur noch als kleinen Checker, nicht mehr fuer grosse \(n\).
Die C++-, Python- und Java-Implementierungen folgen alle demselben schnellen Plan. Es werden nur zwei Zeilen des Dreiecks gespeichert, der Basisfall \(E(0,0)=1\) gesetzt und dann die Zeilen \(1\) bis \(n\) nacheinander aufgebaut. Innerhalb einer Zeile wird der erste Eintrag auf \(0\) gesetzt, und jeder spaetere Eintrag entsteht aus der Summe des vorherigen Eintrags derselben Zeile und des gespiegelten Eintrags aus der Vorzeile:
$$E(r,k)=E(r,k-1)+E(r-1,r-k)\pmod{M}.$$
Nach jeder fertigen Zeile werden die beiden Zeilenpuffer vertauscht und wiederverwendet. Die C++-Implementierung enthaelt zusaetzlich ein kleines Referenz-DP auf Basis der obigen Gerade-Binomialtransition und prueft damit die optimierte Dreiecksrekursion fuer kleine Faelle wie \(n=8\) und \(n=12\). Das ausgegebene Ergebnis ist der rechte Randwert \(E(n,n)\).
Zeile \(r\) benoetigt genau \(r\) Updates, also insgesamt
$$\sum_{r=1}^{n} r=\frac{n(n+1)}{2}=O(n^2).$$
Gespeichert werden nur zwei Zeilen der Laenge \(n+1\), daher liegt der Speicherbedarf bei \(O(n)\). Jeder Schritt der inneren Schleife braucht nur eine modulare Addition und gegebenenfalls eine Subtraktion, was die Implementierung einfach und effizient macht.
Problem 709 icin aranan nicelik, Entringer ucgeninin \(n=24680\) satirindaki sag kenar degerinin \(1020202009\) moduna gore alinmis halidir. Esdeger bicimde, implementasyonlar Entringer inceltmesi altindaki \(n\). Euler zigzag sayisini hesaplar. Bu nedenle asil is, nesneleri dogrudan saymak degil, ayni diziyi cok daha kucuk bir durum uzayiyla ureten yinelemeyi kullanmaktir.
Hizli cozum klasik Entringer ucgenine dayanir. Cok kucuk boyutlarda bir referans dinamik program kullanilabilir, fakat asil cozum pahali binom gecisini bir satirlik kompakt yinelemeyle degistirir.
Kucuk bir saglama yapmak icin, pozitif bir \(r\) indeksli durum tutulabilir ve boyut \(1\) icin tek aktif durumla baslanir. Boyut bir arttiginda referans gecis su sekildedir:
$$D_{k+1}(r')=\sum_{\substack{r\ge 1,\ 0\le t\le r \\ t\equiv 0\pmod{2} \\ r'=r-t+1}} D_k(r)\binom{r}{t}.$$
Boyut \(k\) icin toplam sayi ise
$$T_k=\sum_{r\ge 1} D_k(r)$$
olur. Bu yardimci hesap bile su kontrol degerlerini verir:
$$T_4=5,\qquad T_8=1385.$$
Bu degerler ayni indislerdeki Euler zigzag dizisiyle tam olarak ortusur. Yani daha genis durum uzayinin Entringer sayilarina indirgenebilecegi burada gorulur.
\(0\le k\le r\) icin \(E(r,k)\) sayilarini su sinir kosullariyla tanimlayalim:
$$E(0,0)=1,\qquad E(r,0)=0\quad (r\ge 1),$$
ve yineleme
$$E(r,k)=E(r,k-1)+E(r-1,r-k)\qquad (1\le k\le r).$$
Buna gore her satir, onceki satirin ters cevrilmis halinin on ek toplamlarindan olusur. Tum hesaplar
$$M=1020202009$$
modunda yapilir.
Istenen deger, \(n\) satirinin en sag elemanidir:
$$A_n=E(n,n).$$
Cunku yineleme her adimda onceki satirdan ters sirada bir terim daha ekler. Bu nedenle \(r\) satirinin son terimi, \(r-1\) satirinin tum elemanlarinin toplamina esit olur:
$$E(r,r)=\sum_{j=0}^{r-1} E(r-1,j).$$
Bu yuzden sag kenar
$$1,1,1,2,5,16,61,\dots$$
Euler zigzag dizisini yeniden uretir. Ucgenin tamami daha ince bir dagilim verir; problem ise sadece sag sinirdaki son degeri ister.
Baslangic satiri
$$[1]$$
olsun. Yineleme sirayla su satirlari uretir:
$$\begin{aligned} r=1&:& [0,1],\\ r=2&:& [0,1,1],\\ r=3&:& [0,1,2,2],\\ r=4&:& [0,2,4,5,5]. \end{aligned}$$
Buradan
$$E(4,4)=5$$
elde edilir; bu kucuk dogrulamayla aynidir. Ayni insayi \(8\). satira kadar surdurdugumuzde
$$E(8,8)=1385$$
sonucuna ulasiriz; bu da implementasyonun ikinci kontrol noktasidir.
Referans gecisi cok sayida binom katsayisi ve cok sayida olasi \(r\) durumu icerir. Entringer ucgeni ise ayni bilgiyi iki parametreli ve sadece toplama kullanan bir tabloya sikistirir. Bu degisim matematikseldir; cunku kucuk boyutlarda elde edilen toplamlar klasik Euler zigzag degerleriyle uyusur ve Entringer ucgeni zaten bu dizinin standart inceltmesidir. Bu eslestirme yapildiktan sonra binom gecisini buyuk \(n\) icin surdurmeye gerek kalmaz.
C++, Python ve Java implementasyonlari ayni hizli plani uygular. Ucgenin sadece iki satiri saklanir, taban durum \(E(0,0)=1\) olarak kurulur ve sonra \(1\)'den \(n\)'e kadar satirlar sirayla uretilir. Bir satirin ilk elemani \(0\) yapilir; sonraki her eleman ise ayni satirdaki bir onceki eleman ile onceki satirdaki aynalanmis elemanin toplanmasiyla elde edilir:
$$E(r,k)=E(r,k-1)+E(r-1,r-k)\pmod{M}.$$
Bir satir tamamlaninca iki tampon yer degistirir ve yeniden kullanilir. C++ implementasyonu ayrica yukaridaki cift-binomsal gecise dayanan kucuk bir referans dinamik program da icerir; boylece \(n=8\) ve \(n=12\) gibi kucuk durumlarda hizli ucgen yontemi capraz kontrol edilir. Raporlanan sonuc, en sonda elde edilen \(E(n,n)\) degeridir.
\(r\) satiri tam olarak \(r\) guncelleme yapar. Dolayisiyla toplam is miktari
$$\sum_{r=1}^{n} r=\frac{n(n+1)}{2}=O(n^2)$$
olur. Her anda uzunlugu \(n+1\) olan sadece iki satir tutuldugu icin bellek kullanimi \(O(n)\)'dir. Icteki dongu her adimda bir moduler toplama ve gerekirse bir cikarma yaptigindan, uygulama hem basit hem de verimlidir.
La cantidad buscada en el Problema 709 es el valor del borde derecho del triangulo de Entringer en la fila \(n=24680\), reducido modulo \(1020202009\). De manera equivalente, las implementaciones calculan el \(n\)-esimo numero zigzag de Euler en su refinamiento de Entringer. Por eso la dificultad real no es enumerar objetos de forma directa, sino usar una recurrencia que produzca la misma sucesion con un espacio de estados mucho mas pequeno.
El metodo rapido se apoya en el triangulo clasico de Entringer. Para tamanos diminutos todavia se puede usar un programa dinamico de referencia, pero el solucionador principal reemplaza la costosa transicion binomial por una recurrencia compacta fila por fila.
Como comprobacion pequena, puede mantenerse un estado indexado por un entero positivo \(r\), comenzando con un unico estado activo en tamano \(1\). Cuando el tamano aumenta en uno, la transicion de referencia es
$$D_{k+1}(r')=\sum_{\substack{r\ge 1,\ 0\le t\le r \\ t\equiv 0\pmod{2} \\ r'=r-t+1}} D_k(r)\binom{r}{t}.$$
El total en tamano \(k\) pasa a ser
$$T_k=\sum_{r\ge 1} D_k(r).$$
Incluso este calculo auxiliar ya produce los puntos de control
$$T_4=5,\qquad T_8=1385.$$
Esos valores coinciden exactamente con la sucesion zigzag de Euler en los mismos indices. Esa coincidencia indica que el espacio de estados grande puede comprimirse usando numeros de Entringer.
Definimos \(E(r,k)\) para \(0\le k\le r\) mediante las condiciones de borde
$$E(0,0)=1,\qquad E(r,0)=0\quad (r\ge 1),$$
y la recurrencia
$$E(r,k)=E(r,k-1)+E(r-1,r-k)\qquad (1\le k\le r).$$
Cada fila se obtiene leyendo la fila anterior en orden inverso y tomando sumas prefijas. Todos los calculos se hacen modulo
$$M=1020202009.$$
El valor buscado es la entrada mas a la derecha de la fila \(n\):
$$A_n=E(n,n).$$
Como la recurrencia agrega en cada paso una entrada invertida de la fila anterior, el ultimo elemento de la fila \(r\) es la suma de toda la fila \(r-1\):
$$E(r,r)=\sum_{j=0}^{r-1} E(r-1,j).$$
Por eso el borde derecho reproduce la sucesion zigzag de Euler
$$1,1,1,2,5,16,61,\dots$$
El triangulo completo es un refinamiento de la sucesion, mientras que el problema solo necesita el valor final de la frontera derecha.
Partiendo de la fila base
$$[1],$$
la recurrencia genera
$$\begin{aligned} r=1&:& [0,1],\\ r=2&:& [0,1,1],\\ r=3&:& [0,1,2,2],\\ r=4&:& [0,2,4,5,5]. \end{aligned}$$
Por tanto,
$$E(4,4)=5,$$
que coincide con la verificacion pequena. Si se continua el mismo proceso hasta la fila \(8\), se obtiene
$$E(8,8)=1385,$$
que es el segundo punto de control usado por la implementacion.
La transicion de referencia contiene muchos coeficientes binomiales y muchos posibles estados \(r\). El triangulo de Entringer comprime esa informacion en una tabla de dos parametros cuya actualizacion solo usa sumas. El reemplazo es natural desde el punto de vista matematico, porque los totales pequenos coinciden con los valores clasicos zigzag de Euler y el triangulo de Entringer es precisamente el refinamiento estandar de esa sucesion. Una vez hecha esa identificacion, la transicion binomial solo sirve como comprobacion pequena.
Las implementaciones en C++, Python y Java siguen el mismo plan rapido. Guardan solo dos filas del triangulo, inicializan el caso base \(E(0,0)=1\) y despues construyen las filas desde \(1\) hasta \(n\). Dentro de cada fila, la primera entrada se fija en \(0\), y cada entrada posterior se obtiene sumando la entrada anterior de la misma fila con la entrada reflejada de la fila previa:
$$E(r,k)=E(r,k-1)+E(r-1,r-k)\pmod{M}.$$
Al terminar una fila, los dos buffers se intercambian y se reutilizan. La implementacion en C++ tambien incluye un pequeno programa dinamico de referencia basado en la transicion binomial con \(t\) par, y compara ambos enfoques en casos pequenos como \(n=8\) y \(n=12\). El resultado que se informa es el valor final del borde derecho \(E(n,n)\).
La fila \(r\) realiza exactamente \(r\) actualizaciones, asi que el trabajo total es
$$\sum_{r=1}^{n} r=\frac{n(n+1)}{2}=O(n^2).$$
Solo se almacenan dos filas de longitud \(n+1\), de modo que la memoria es \(O(n)\). Cada paso interno usa una suma modular y, si hace falta, una resta, lo que mantiene la implementacion simple y eficiente.
Problem 709 需要的量，可以从 Entringer 三角形的右边界读出：在第 \(n=24680\) 行取最右侧的值，再对 \(1020202009\) 取模。换句话说，C++、Python 和 Java 实现都在计算第 \(n\) 个 Euler zigzag 数，只是采用了 Entringer 三角形这一更细的表示方式。真正的难点不是直接枚举组合对象，而是找到一个能够生成同一序列、却只需要较小状态空间的递推。
高效解法围绕经典的 Entringer 三角形展开。C++ 版本中保留了一个只适合很小规模的参考动态规划，用来确认前几个值；正式求解则把那个包含大量二项式项的转移压缩成一个按行推进的简单递推。
先看一个只用于校验的小规模模型。设状态用正整数 \(r\) 编号，并且在规模 \(1\) 时只有一个活动状态。规模从 \(k\) 增加到 \(k+1\) 时，参考转移写成
$$D_{k+1}(r')=\sum_{\substack{r\ge 1,\ 0\le t\le r \\ t\equiv 0\pmod{2} \\ r'=r-t+1}} D_k(r)\binom{r}{t}.$$
规模 \(k\) 的总数则是
$$T_k=\sum_{r\ge 1} D_k(r).$$
这个辅助模型已经能得到两个很关键的检查点：
$$T_4=5,\qquad T_8=1385.$$
这两个数恰好就是对应位置上的 Euler zigzag 数。也就是说，虽然这个参考模型的状态看起来更杂，但它最终汇总出来的总量已经暴露出背后的经典序列。
对所有满足 \(0\le k\le r\) 的指标，定义 Entringer 数 \(E(r,k)\)。边界条件是
$$E(0,0)=1,\qquad E(r,0)=0\quad (r\ge 1),$$
而递推关系是
$$E(r,k)=E(r,k-1)+E(r-1,r-k)\qquad (1\le k\le r).$$
这个公式的含义很直观：要构造第 \(r\) 行，只要把第 \(r-1\) 行倒过来读，然后做前缀和即可。因此三角形每往下一行，实际上只是把上一行的反向信息逐步累加。全部运算都在模
$$M=1020202009$$
下进行。
程序真正需要的是第 \(n\) 行最右端的值：
$$A_n=E(n,n).$$
由于递推在同一行中不断把“上一行反向后的下一个元素”加进来，所以第 \(r\) 行最后一个元素，恰好等于第 \(r-1\) 行所有元素的总和：
$$E(r,r)=\sum_{j=0}^{r-1} E(r-1,j).$$
这就解释了为什么右边界会重现 Euler zigzag 序列
$$1,1,1,2,5,16,61,\dots$$
整个三角形给出了更细的分解，而题目最终只需要这条右边界上的终值。
从初始行
$$[1]$$
开始，按递推逐行展开，可以得到
$$\begin{aligned} r=1&:& [0,1],\\ r=2&:& [0,1,1],\\ r=3&:& [0,1,2,2],\\ r=4&:& [0,2,4,5,5]. \end{aligned}$$
因此
$$E(4,4)=5,$$
正好对应小规模检查值。如果继续把同样的过程推到第 \(8\) 行，就会得到
$$E(8,8)=1385,$$
这也是实现中用来交叉验证的第二个检查点。
参考转移中既有大量二项式系数，又有很多可能的 \(r\) 状态，因此只适合很小规模。Entringer 三角形则把这些信息压缩成一个二维表，而且更新只依赖加法，不再需要显式展开所有二项式分支。从数学上看，这种替换是自然的：小规模参考值已经和经典 Euler zigzag 数完全一致，而 Entringer 三角形正是这条序列的标准细化表示。一旦确认了这个对应关系，大规模计算就应当直接使用三角形递推。
C++、Python 和 Java 实现采用的是同一套高效流程。它们只保存三角形的上一行和当前行，先设定基例 \(E(0,0)=1\)，然后从第 \(1\) 行一直推进到第 \(n\) 行。在每一行内部，第一项固定为 \(0\)，后面的每一项都由“本行前一项”和“上一行中镜像位置的一项”相加得到：
$$E(r,k)=E(r,k-1)+E(r-1,r-k)\pmod{M}.$$
一行完成后，两块行缓冲区交换角色并重复使用，所以不需要保存整张三角表。C++ 版本还额外保留了一个基于“只枚举偶数 \(t\)”的参考动态规划，用它来核对小规模情况，例如 \(n=8\) 和 \(n=12\)。最终输出的就是最后一行最右侧的值 \(E(n,n)\)。
第 \(r\) 行恰好需要 \(r\) 次更新，因此总运算量为
$$\sum_{r=1}^{n} r=\frac{n(n+1)}{2}=O(n^2).$$
由于任意时刻只保存两行、每行长度为 \(n+1\)，空间复杂度是 \(O(n)\)。内层循环的每一步只做一次模加法，并在必要时做一次减法，因此实现简单，常数因子也很小。
Для Problem 709 требуется значение на правой границе треугольника Энтрингера в строке \(n=24680\), взятое по модулю \(1020202009\). Эквивалентно реализации вычисляют \(n\)-е число Эйлера зигзаг в его уточнении через числа Энтрингера. Поэтому главная идея состоит не в прямом переборе, а в использовании рекуррентной схемы, которая порождает ту же последовательность при гораздо меньшем пространстве состояний.
Быстрое решение опирается на классический треугольник Энтрингера. Для совсем малых размеров можно оставить эталонный динамический процесс, но основной алгоритм заменяет дорогой биномиальный переход компактной построчной рекурсией.
Для небольшой проверки можно хранить состояние с положительным индексом \(r\), начиная с единственного активного состояния при размере \(1\). При переходе к размеру \(k+1\) эталонная формула имеет вид
$$D_{k+1}(r')=\sum_{\substack{r\ge 1,\ 0\le t\le r \\ t\equiv 0\pmod{2} \\ r'=r-t+1}} D_k(r)\binom{r}{t}.$$
Общее число объектов размера \(k\) равно
$$T_k=\sum_{r\ge 1} D_k(r).$$
Уже этот вспомогательный расчет дает контрольные значения
$$T_4=5,\qquad T_8=1385.$$
Они точно совпадают с числами Эйлера зигзаг на тех же местах, и именно это подсказывает, что большой набор состояний можно свернуть к числам Энтрингера.
Определим числа \(E(r,k)\) для \(0\le k\le r\) граничными условиями
$$E(0,0)=1,\qquad E(r,0)=0\quad (r\ge 1),$$
и рекуррентным соотношением
$$E(r,k)=E(r,k-1)+E(r-1,r-k)\qquad (1\le k\le r).$$
Это означает, что каждая новая строка строится как префиксные суммы предыдущей строки, прочитанной справа налево. Все вычисления выполняются по модулю
$$M=1020202009.$$
Искомая величина - это самый правый элемент строки \(n\):
$$A_n=E(n,n).$$
Так как в рекурсии на каждом шаге добавляется очередной элемент предыдущей строки в обратном порядке, последний элемент строки \(r\) равен сумме всей строки \(r-1\):
$$E(r,r)=\sum_{j=0}^{r-1} E(r-1,j).$$
Именно поэтому правая граница воспроизводит последовательность Эйлера зигзаг
$$1,1,1,2,5,16,61,\dots$$
Полный треугольник дает более тонкое разбиение, а задаче нужен только финальный элемент на правой границе.
Начиная с базовой строки
$$[1],$$
получаем по рекурсии
$$\begin{aligned} r=1&:& [0,1],\\ r=2&:& [0,1,1],\\ r=3&:& [0,1,2,2],\\ r=4&:& [0,2,4,5,5]. \end{aligned}$$
Следовательно,
$$E(4,4)=5,$$
что совпадает с малой проверкой. Если продолжить до строки \(8\), получится
$$E(8,8)=1385,$$
второе контрольное значение, используемое реализациями.
Эталонный переход содержит много биномиальных коэффициентов и много возможных состояний \(r\), поэтому пригоден только для маленьких размеров. Треугольник Энтрингера сжимает ту же информацию в двумерную таблицу, где обновление использует только сложение. Такая замена математически естественна: малые контрольные значения совпадают с классическими числами Эйлера зигзаг, а треугольник Энтрингера является стандартным уточнением этой последовательности. После такого отождествления биномиальный переход нужен лишь как небольшой контроль.
Реализации на C++, Python и Java используют один и тот же быстрый план. Они хранят только предыдущую строку и текущую строку треугольника, задают базовый случай \(E(0,0)=1\), а затем последовательно строят строки от \(1\) до \(n\). Внутри строки первый элемент устанавливается в \(0\), а каждый следующий элемент получается как сумма предыдущего элемента той же строки и зеркального элемента из предыдущей строки:
$$E(r,k)=E(r,k-1)+E(r-1,r-k)\pmod{M}.$$
После завершения строки два буфера меняются ролями и используются снова, поэтому хранить весь треугольник не нужно. В версии на C++ дополнительно есть маленький эталонный динамический расчет на основе перехода с четным \(t\); он проверяет совпадение с быстрым методом для малых случаев, например \(n=8\) и \(n=12\). Итоговым ответом является конечное значение \(E(n,n)\).
Строка \(r\) требует ровно \(r\) обновлений, поэтому общий объем работы равен
$$\sum_{r=1}^{n} r=\frac{n(n+1)}{2}=O(n^2).$$
Одновременно хранятся только две строки длины \(n+1\), так что память составляет \(O(n)\). Каждый шаг внутреннего цикла делает одно сложение по модулю и при необходимости одно вычитание, поэтому алгоритм остается простым и эффективным.
الكمية المطلوبة في Problem 709 هي القيمة الموجودة على الحافة اليمنى من مثلث Entringer عند الصف \(n=24680\)، ثم تؤخذ بترديد \(1020202009\). وبصورة مكافئة، فإن التنفيذات في C++ وPython وJava تحسب العدد المتعرج لاويلر عند الرتبة \(n\) بصيغته المفصلة عبر اعداد Entringer. لذلك فالمسألة الحقيقية ليست تعداد البنى مباشرة، بل استعمال علاقة تكرارية تولد السلسلة نفسها ضمن فضاء حالات اصغر بكثير.
الحل السريع مبني على مثلث Entringer الكلاسيكي. توجد طريقة ديناميكية مرجعية صغيرة تصلح فقط للاحجام الصغيرة جدا، لكن الحل الفعلي يستبدل الانتقال الثنائي الحدين المكلف بعلاقة صفية مضغوطة.
من اجل فحص صغير يمكن الاحتفاظ بحالة مفهرسة بعدد صحيح موجب \(r\)، مع البدء بحالة فعالة واحدة عند الحجم \(1\). وعند الانتقال من الحجم \(k\) الى الحجم \(k+1\) تكون الصيغة المرجعية
$$D_{k+1}(r')=\sum_{\substack{r\ge 1,\ 0\le t\le r \\ t\equiv 0\pmod{2} \\ r'=r-t+1}} D_k(r)\binom{r}{t}.$$
ويكون العدد الكلي عند الحجم \(k\)
$$T_k=\sum_{r\ge 1} D_k(r).$$
حتى هذا النموذج المساعد يعطي قيمتي التحقق
$$T_4=5,\qquad T_8=1385.$$
وهاتان القيمتان تتطابقان تماما مع اعداد اويلر المتعرجة عند الفهارس نفسها. وهذه المطابقة هي الاشارة الى ان فضاء الحالات الاكبر يمكن ضغطه الى اعداد Entringer.
نعرف الاعداد \(E(r,k)\) لكل \(0\le k\le r\) بواسطة الشروط الحدية
$$E(0,0)=1,\qquad E(r,0)=0\quad (r\ge 1),$$
وبالعلاقة التكرارية
$$E(r,k)=E(r,k-1)+E(r-1,r-k)\qquad (1\le k\le r).$$
وهذا يعني ان كل صف جديد يتكون من جمع بادئات الصف السابق بعد قراءته بترتيب معكوس. وتجرى جميع الحسابات بترديد
$$M=1020202009.$$
القيمة المطلوبة هي العنصر الاخير في الصف \(n\):
$$A_n=E(n,n).$$
ولان العلاقة التكرارية تضيف في كل خطوة عنصرا اخر من الصف السابق بعد عكس ترتيبه، فان اخر عنصر في الصف \(r\) يساوي مجموع الصف \(r-1\) كله:
$$E(r,r)=\sum_{j=0}^{r-1} E(r-1,j).$$
ولهذا تعيد الحافة اليمنى توليد سلسلة اويلر المتعرجة
$$1,1,1,2,5,16,61,\dots$$
فالمثلث الكامل يعطي تفصيلا ادق، بينما تحتاج المسألة في النهاية الى القيمة النهائية على الحدود اليمنى فقط.
إذا بدأنا من الصف الاساسي
$$[1],$$
فان العلاقة التكرارية تولد الصفوف التالية:
$$\begin{aligned} r=1&:& [0,1],\\ r=2&:& [0,1,1],\\ r=3&:& [0,1,2,2],\\ r=4&:& [0,2,4,5,5]. \end{aligned}$$
ومن ثم
$$E(4,4)=5,$$
وهي نفس قيمة التحقق الصغيرة. وإذا واصلنا البناء حتى الصف \(8\) نحصل على
$$E(8,8)=1385,$$
وهي نقطة التحقق الثانية المستخدمة في التنفيذ.
الانتقال المرجعي يحتوي على عدد كبير من معاملات ثنائية الحدين وعلى عدد كبير من الحالات الممكنة \(r\)، ولذلك فهو مناسب فقط للاحجام الصغيرة. اما مثلث Entringer فيضغط هذه المعلومات في جدول ثنائي البعد، وتصبح عملية التحديث جمعا بسيطا فقط. هذا الاستبدال طبيعي رياضيا، لان القيم الصغيرة المتحققة تطابق اعداد اويلر المتعرجة الكلاسيكية، ومثلث Entringer هو التمثيل التفصيلي القياسي لهذه السلسلة. وبعد تثبيت هذا التطابق لا يعود هناك داع لاستخدام الانتقال الثنائي الحدين في الاحجام الكبيرة.
التنفيذات في C++ وPython وJava تتبع الخطة السريعة نفسها. فهي تحتفظ بصفين فقط من المثلث، وتبدا من الحالة الاساسية \(E(0,0)=1\)، ثم تبني الصفوف من \(1\) حتى \(n\) بالتتابع. داخل كل صف تضبط القيمة الاولى على \(0\)، ثم تحسب كل قيمة لاحقة بجمع القيمة السابقة من الصف نفسه مع القيمة المنعكسة من الصف السابق:
$$E(r,k)=E(r,k-1)+E(r-1,r-k)\pmod{M}.$$
وبعد اكمال الصف يتم تبادل مخزني الصفوف واعادة استخدامهما، لذلك لا حاجة لتخزين المثلث كاملا. ويحتوي تنفيذ C++ ايضا على برنامج ديناميكي مرجعي صغير يعتمد على انتقال ثنائي الحدين مع \(t\) زوجي، ويستخدمه للتحقق من توافق الطريقة السريعة في الحالات الصغيرة مثل \(n=8\) و\(n=12\). والنتيجة المعلنة في النهاية هي القيمة \(E(n,n)\).
الصف \(r\) يحتاج الى \(r\) تحديثات بالضبط، ولذلك يكون مقدار العمل الكلي
$$\sum_{r=1}^{n} r=\frac{n(n+1)}{2}=O(n^2).$$
ويجري تخزين صفين فقط بطول \(n+1\)، لذا يكون استهلاك الذاكرة \(O(n)\). وكل خطوة في الحلقة الداخلية تستخدم جمعا واحدا بترديد، ومعه طرح واحد عند الحاجة، مما يجعل التنفيذ بسيطا وفعالا.