For Problem 865, the implementation does not attempt to enumerate admissible numbers directly. Instead, it evaluates a counting function \(T(N)\) at \(N=10^4\) modulo the prime
$$M=998244353.$$
The whole problem is encoded by three coupled sequences \(U_n\), \(V_n\), and \(E_n\). Their recurrences capture how valid structures of total size \(n\) are assembled from smaller ones, and the final answer is extracted from the \(E_n\) sequence.
The C++, Python, and Java implementations use the same three recurrences:
$$V_1=1,\qquad V_n=9\sum_{i=0}^{n-1}U_iV_{n-1-i}\quad (n\ge 2),$$
$$U_n=V_{n-1}+9\sum_{i=0}^{n-1}U_iU_{n-1-i}\quad (n\ge 1),$$
$$E_0=1,\qquad E_n=10\sum_{i=0}^{n-1}U_iE_{n-1-i}\quad (n\ge 1).$$
The target quantity is then
$$T(N)=\sum_{n=1}^{N}\frac{9E_n}{10}.$$
Because every \(E_n\) with \(n\ge 1\) is a multiple of \(10\), this expression is an integer in exact arithmetic.
Each sum runs over all decompositions of \(n-1\) into
$$i+(n-1-i).$$
That is exactly the Cauchy-product pattern for combining two smaller structures into one larger structure. The coefficients \(9\) and \(10\) are fixed multiplicative weights that come from the decimal choices built into the counting model. So the problem is reduced to computing convolution sums, not to scanning integers one by one.
This viewpoint matters because it immediately explains why a dynamic program works: every value at size \(n\) depends only on values from smaller sizes.
Introduce formal power series
$$U(z)=\sum_{n\ge 0}U_nz^n,\qquad V(z)=\sum_{n\ge 1}V_nz^n,\qquad E(z)=\sum_{n\ge 0}E_nz^n.$$
The convolution rules become
$$V(z)=z+9z\,U(z)V(z),$$
$$U(z)=zV(z)+9z\,U(z)^2,$$
$$E(z)=1+10z\,U(z)E(z)=\frac{1}{1-10z\,U(z)}.$$
The first identity shows that \(V\) is the basic seed \(z\) plus a recursive correction. The third identity is especially useful: once \(U(z)\) is known, \(E(z)\) is just a geometric-series type transform.
We can also eliminate \(V(z)\) via
$$V(z)=\frac{z}{1-9z\,U(z)},$$
which gives the cubic relation
$$81z^2U(z)^3-18zU(z)^2+U(z)-z^2=0.$$
The implementation does not solve this cubic symbolically, but it is a good consistency check on the recurrence system.
The first few exact values already reveal a rigid pattern:
$$V_1=1,\qquad U_2=1,\qquad E_3=10,$$
and then the nonzero terms continue at spacings of \(3\). This is not accidental.
Assume inductively that \(U_n\) can be nonzero only for \(n\equiv 2\pmod 3\) and \(V_n\) only for \(n\equiv 1\pmod 3\). In the recurrence for \(V_n\), a nonzero summand requires
$$i\equiv 2\pmod 3,\qquad n-1-i\equiv 1\pmod 3,$$
so \(n-1\equiv 0\pmod 3\), hence
$$V_n\neq 0\implies n\equiv 1\pmod 3.$$
In the recurrence for \(U_n\), the term \(V_{n-1}\) is nonzero only when \(n-1\equiv 1\pmod 3\), and the convolution term needs
$$2+2\equiv 1\pmod 3,$$
again forcing
$$U_n\neq 0\implies n\equiv 2\pmod 3.$$
Finally, for \(E_n\) a nonzero summand must pair a \(U\)-index congruent to \(2\) with an \(E\)-index congruent to \(0\), so
$$E_n\neq 0\implies n\equiv 0\pmod 3.$$
This residue-class behavior is the clearest structural fingerprint of the triplicate phenomenon in the recurrence system.
Because only every third term survives, it is natural to define
$$A_k=U_{3k+2},\qquad B_k=V_{3k+1},\qquad C_k=E_{3k}.$$
Then
$$A_0=1,\qquad B_0=1,\qquad C_0=1,$$
and for \(k\ge 1\) the recurrences simplify to
$$B_k=9\sum_{a=0}^{k-1}A_aB_{k-1-a},$$
$$A_k=B_k+9\sum_{a=0}^{k-1}A_aA_{k-1-a},$$
$$C_k=10\sum_{a=0}^{k-1}A_aC_{k-1-a}.$$
The target sum becomes
$$T(N)=\frac{9}{10}\sum_{k=1}^{\lfloor N/3\rfloor}C_k.$$
This reindexing is mathematically equivalent to the original system, but it makes the structure much easier to read: \(B\) feeds \(A\), and \(A\) feeds \(C\).
Starting from \(A_0=B_0=C_0=1\), the next values are
$$B_1=9A_0B_0=9,$$
$$A_1=B_1+9A_0A_0=9+9=18,$$
$$C_1=10A_0C_0=10.$$
One more round gives
$$B_2=9(A_0B_1+A_1B_0)=9(9+18)=243,$$
$$A_2=B_2+9(A_0A_1+A_1A_0)=243+9(18+18)=567,$$
$$C_2=10(A_0C_1+A_1C_0)=10(10+18)=280.$$
Returning to the original indexing, this means
$$E_3=10,\qquad E_6=280.$$
Therefore
$$T(6)=\frac{9}{10}(E_3+E_6)=\frac{9}{10}(10+280)=261,$$
which matches the exact small-\(N\) check used by the implementation.
For the actual task the program computes
$$T(10^4)\equiv 9\cdot 10^{-1}\sum_{n=1}^{10^4}E_n\pmod M,$$
and because only indices divisible by \(3\) matter, this is the same as
$$T(10^4)\equiv 9\cdot 10^{-1}\sum_{k=1}^{\lfloor 10^4/3\rfloor}C_k\pmod M.$$
Since \(M\) is prime, the modular inverse is obtained from Fermat's little theorem:
$$10^{-1}\equiv 10^{M-2}\pmod M.$$
The C++, Python, and Java implementations all follow the same pipeline. First, they allocate three arrays of length \(N+1\) for the sequences \(U\), \(V\), and \(E\), with the initial condition \(E_0=1\). They then sweep forward from \(n=1\) to \(n=N\).
In the first sweep, each \(n\) computes two convolution sums at once: one for the mixed product \(U_iV_{n-1-i}\), and one for the self-product \(U_iU_{n-1-i}\). Those two sums immediately produce \(V_n\) and \(U_n\). In the second sweep, the implementation computes \(E_n\) from the convolution of \(U\) and \(E\).
After all \(E_n\) values are known, the program accumulates
$$\sum_{n=1}^{N}E_n$$
and multiplies by \(9\cdot 10^{-1}\bmod M\). The C++ implementation also performs exact small-\(N\) consistency checks before the modular evaluation, including the benchmark
$$T(6)=261$$
and a larger exact value at \(N=30\). That is a good safeguard against recurrence or indexing mistakes.
Let \(N\) be the requested size limit. The first phase computes two length-\(n\) convolutions for each \(n\), and the second phase computes one more length-\(n\) convolution. Therefore the total work is proportional to
$$\sum_{n=1}^{N} n = O(N^2).$$
More concretely, the algorithm performs about three triangular convolution passes, so the constant factor is moderate but the asymptotic order remains quadratic. The memory usage is \(O(N)\), because only the three one-dimensional arrays must be stored.
Bei Problem 865 werden die zulässigen Zahlen nicht direkt durchprobiert. Stattdessen berechnet die Implementierung eine Zählfunktion \(T(N)\) für \(N=10^4\) modulo der Primzahl
$$M=998244353.$$
Das gesamte Problem wird in drei gekoppelte Folgen \(U_n\), \(V_n\) und \(E_n\) übersetzt. Ihre Rekurrenzen beschreiben, wie gültige Strukturen der Gesamtgröße \(n\) aus kleineren Teilstrukturen zusammengesetzt werden, und aus der Folge \(E_n\) wird am Ende das gesuchte Ergebnis gewonnen.
Die C++-, Python- und Java-Implementierungen verwenden dieselben drei Rekurrenzen:
$$V_1=1,\qquad V_n=9\sum_{i=0}^{n-1}U_iV_{n-1-i}\quad (n\ge 2),$$
$$U_n=V_{n-1}+9\sum_{i=0}^{n-1}U_iU_{n-1-i}\quad (n\ge 1),$$
$$E_0=1,\qquad E_n=10\sum_{i=0}^{n-1}U_iE_{n-1-i}\quad (n\ge 1).$$
Die Zielgröße ist
$$T(N)=\sum_{n=1}^{N}\frac{9E_n}{10}.$$
Da jedes \(E_n\) mit \(n\ge 1\) durch \(10\) teilbar ist, ist dieser Ausdruck in exakter Arithmetik wohldefiniert.
Jede Summe läuft über alle Zerlegungen von \(n-1\) in
$$i+(n-1-i).$$
Genau das ist das Muster eines Cauchy-Produkts: Zwei kleinere Bausteine werden zu einem größeren Objekt kombiniert. Die Faktoren \(9\) und \(10\) sind feste Gewichte, die aus der dezimalen Struktur des Zählproblems stammen. Dadurch wird die Aufgabe auf Faltungssummen reduziert, nicht auf eine direkte Enumeration ganzer Zahlen.
Das erklärt sofort, warum eine dynamische Programmierung möglich ist: Jeder Wert der Größe \(n\) hängt nur von kleineren Größen ab.
Wir führen formale Potenzreihen ein:
$$U(z)=\sum_{n\ge 0}U_nz^n,\qquad V(z)=\sum_{n\ge 1}V_nz^n,\qquad E(z)=\sum_{n\ge 0}E_nz^n.$$
Dann werden die Rekurrenzen zu
$$V(z)=z+9z\,U(z)V(z),$$
$$U(z)=zV(z)+9z\,U(z)^2,$$
$$E(z)=1+10z\,U(z)E(z)=\frac{1}{1-10z\,U(z)}.$$
Die erste Gleichung zeigt, dass \(V\) aus einem Basisterm \(z\) plus rekursiver Korrektur besteht. Die dritte Gleichung ist besonders nützlich: Sobald \(U(z)\) bekannt ist, folgt \(E(z)\) als einfacher geometrischer Transform.
Außerdem kann man \(V(z)\) eliminieren:
$$V(z)=\frac{z}{1-9z\,U(z)},$$
woraus die kubische Beziehung
$$81z^2U(z)^3-18zU(z)^2+U(z)-z^2=0$$
entsteht. Das Programm löst diese Gleichung nicht symbolisch, aber sie bestätigt die Konsistenz des Systems.
Schon die ersten exakten Werte zeigen ein starres Muster:
$$V_1=1,\qquad U_2=1,\qquad E_3=10,$$
und danach liegen alle weiteren von Null verschiedenen Terme jeweils im Abstand \(3\). Das ist eine direkte Folge der Rekurrenzen.
Nimmt man induktiv an, dass \(U_n\) nur für \(n\equiv 2\pmod 3\) und \(V_n\) nur für \(n\equiv 1\pmod 3\) von Null verschieden sein können, dann erfordert ein nichtverschwindender Summand in der Rekurrenz für \(V_n\)
$$i\equiv 2\pmod 3,\qquad n-1-i\equiv 1\pmod 3,$$
also \(n-1\equiv 0\pmod 3\) und damit
$$V_n\neq 0\implies n\equiv 1\pmod 3.$$
Für \(U_n\) ist der Term \(V_{n-1}\) nur dann nichtnull, wenn \(n-1\equiv 1\pmod 3\), und im Faltungsterm gilt
$$2+2\equiv 1\pmod 3,$$
sodass ebenfalls
$$U_n\neq 0\implies n\equiv 2\pmod 3$$
erzwingt wird. Für \(E_n\) koppelt man einen Index aus \(U\) mit Restklasse \(2\) mit einem Index aus \(E\) mit Restklasse \(0\), also
$$E_n\neq 0\implies n\equiv 0\pmod 3.$$
Dieses Restklassenmuster ist das deutlichste algebraische Merkmal des Triplikat-Charakters in der Lösung.
Weil nur jede dritte Position beiträgt, definieren wir
$$A_k=U_{3k+2},\qquad B_k=V_{3k+1},\qquad C_k=E_{3k}.$$
Dann gilt
$$A_0=1,\qquad B_0=1,\qquad C_0=1,$$
und für \(k\ge 1\) vereinfachen sich die Rekurrenzen zu
$$B_k=9\sum_{a=0}^{k-1}A_aB_{k-1-a},$$
$$A_k=B_k+9\sum_{a=0}^{k-1}A_aA_{k-1-a},$$
$$C_k=10\sum_{a=0}^{k-1}A_aC_{k-1-a}.$$
Die Zielsumme wird zu
$$T(N)=\frac{9}{10}\sum_{k=1}^{\lfloor N/3\rfloor}C_k.$$
Diese Umindizierung ändert mathematisch nichts, macht aber das Zusammenspiel der Folgen wesentlich transparenter: \(B\) erzeugt \(A\), und \(A\) erzeugt \(C\).
Ausgehend von \(A_0=B_0=C_0=1\) erhält man
$$B_1=9A_0B_0=9,$$
$$A_1=B_1+9A_0A_0=9+9=18,$$
$$C_1=10A_0C_0=10.$$
Eine weitere Runde liefert
$$B_2=9(A_0B_1+A_1B_0)=9(9+18)=243,$$
$$A_2=B_2+9(A_0A_1+A_1A_0)=243+9(18+18)=567,$$
$$C_2=10(A_0C_1+A_1C_0)=10(10+18)=280.$$
Im ursprünglichen Indexschema bedeutet das
$$E_3=10,\qquad E_6=280.$$
Somit folgt
$$T(6)=\frac{9}{10}(E_3+E_6)=\frac{9}{10}(10+280)=261,$$
genau der exakte Kontrollwert aus der Implementierung.
Für die eigentliche Aufgabe berechnet das Programm
$$T(10^4)\equiv 9\cdot 10^{-1}\sum_{n=1}^{10^4}E_n\pmod M,$$
und weil nur Indizes teilbar durch \(3\) beitragen, ist das gleichbedeutend mit
$$T(10^4)\equiv 9\cdot 10^{-1}\sum_{k=1}^{\lfloor 10^4/3\rfloor}C_k\pmod M.$$
Da \(M\) prim ist, erhält man das inverse Element von \(10\) mit dem kleinen Satz von Fermat:
$$10^{-1}\equiv 10^{M-2}\pmod M.$$
Die C++-, Python- und Java-Implementierungen folgen derselben Pipeline. Zuerst werden drei Arrays der Länge \(N+1\) für \(U\), \(V\) und \(E\) angelegt, mit der Anfangsbedingung \(E_0=1\). Danach wird von \(n=1\) bis \(n=N\) nach vorne iteriert.
Im ersten Durchlauf berechnet jede Position \(n\) gleichzeitig zwei Faltungssummen: einmal das gemischte Produkt \(U_iV_{n-1-i}\) und einmal das Selbstprodukt \(U_iU_{n-1-i}\). Daraus entstehen direkt \(V_n\) und \(U_n\). Im zweiten Durchlauf wird \(E_n\) aus der Faltung von \(U\) und \(E\) aufgebaut.
Sind alle \(E_n\) bekannt, summiert die Implementierung
$$\sum_{n=1}^{N}E_n$$
und multipliziert anschließend mit \(9\cdot 10^{-1}\bmod M\). Die C++-Implementierung enthält zusätzlich exakte Tests für kleine \(N\), darunter
$$T(6)=261$$
sowie einen größeren exakten Referenzwert bei \(N=30\). Das schützt gut gegen Index- und Rekurrenzfehler.
Sei \(N\) die geforderte Größenobergrenze. Die erste Phase berechnet für jedes \(n\) zwei Faltungen der Länge \(n\), die zweite Phase eine weitere Faltung der Länge \(n\). Deshalb ist der Gesamtaufwand proportional zu
$$\sum_{n=1}^{N} n = O(N^2).$$
Anschaulich sind es etwa drei dreieckige Faltungsdurchläufe; der konstante Faktor bleibt also moderat, die asymptotische Ordnung aber quadratisch. Der Speicherbedarf beträgt \(O(N)\), weil nur die drei eindimensionalen Folgen gespeichert werden.
Problem 865 için çözüm, uygun sayıları tek tek üretmeye çalışmaz. Bunun yerine \(N=10^4\) için bir sayım fonksiyonu olan \(T(N)\) değerini şu asal mod altında hesaplar:
$$M=998244353.$$
Tüm problem üç bağlı diziye dönüştürülür: \(U_n\), \(V_n\) ve \(E_n\). Bu dizilerin bağıntıları, toplam boyutu \(n\) olan geçerli yapıların daha küçük parçalardan nasıl kurulduğunu anlatır; nihai sonuç da \(E_n\) dizisinden çıkarılır.
C++, Python ve Java uygulamaları aynı üç bağıntıyı kullanır:
$$V_1=1,\qquad V_n=9\sum_{i=0}^{n-1}U_iV_{n-1-i}\quad (n\ge 2),$$
$$U_n=V_{n-1}+9\sum_{i=0}^{n-1}U_iU_{n-1-i}\quad (n\ge 1),$$
$$E_0=1,\qquad E_n=10\sum_{i=0}^{n-1}U_iE_{n-1-i}\quad (n\ge 1).$$
Hedef büyüklük ise
$$T(N)=\sum_{n=1}^{N}\frac{9E_n}{10}.$$
\(n\ge 1\) için her \(E_n\) zaten \(10\)'a bölünebildiğinden, bu ifade tam sayılı aritmetikte de anlamlıdır.
Her toplam, \(n-1\)'in
$$i+(n-1-i)$$
şeklindeki tüm ayrışmalarını dolaşır. Bu tam olarak Cauchy çarpımı desenidir: iki küçük yapı birleştirilip daha büyük bir yapı elde edilir. \(9\) ve \(10\) katsayıları ise sayım modelinin onluk tabandaki sabit ağırlıklarıdır. Böylece problem, sayıları tek tek gezmek yerine evrişim toplamları hesaplama problemine dönüşür.
Bu bakış açısı neden dinamik programlamanın işe yaradığını da açıklar: boyut \(n\) olan her değer yalnızca daha küçük boyutlardan beslenir.
Şu biçimsel kuvvet serilerini tanımlayalım:
$$U(z)=\sum_{n\ge 0}U_nz^n,\qquad V(z)=\sum_{n\ge 1}V_nz^n,\qquad E(z)=\sum_{n\ge 0}E_nz^n.$$
Bağıntılar şu hale gelir:
$$V(z)=z+9z\,U(z)V(z),$$
$$U(z)=zV(z)+9z\,U(z)^2,$$
$$E(z)=1+10z\,U(z)E(z)=\frac{1}{1-10z\,U(z)}.$$
İlk denklem, \(V\)'nin temel tohum \(z\) ile başlayıp özyinelemeli olarak düzeltildiğini gösterir. Üçüncü denklem özellikle kullanışlıdır: \(U(z)\) bilindiğinde \(E(z)\) doğrudan geometrik seri türü bir dönüşümle elde edilir.
Ayrıca
$$V(z)=\frac{z}{1-9z\,U(z)}$$
yazılabildiği için, \(V\) elimine edilirse
$$81z^2U(z)^3-18zU(z)^2+U(z)-z^2=0$$
kübik bağıntısı bulunur. Uygulama bunu sembolik olarak çözmez, ama bu denklem sistemin tutarlılığını gösterir.
İlk birkaç tam değer çok düzenli bir desen verir:
$$V_1=1,\qquad U_2=1,\qquad E_3=10,$$
ve bundan sonra sıfır olmayan terimler hep \(3\) adım arayla gelir. Bu tesadüf değildir.
Tümevarımsal olarak \(U_n\) yalnızca \(n\equiv 2\pmod 3\) iken, \(V_n\) ise yalnızca \(n\equiv 1\pmod 3\) iken sıfırdan farklı olsun. \(V_n\) bağıntısında sıfır olmayan bir terim için
$$i\equiv 2\pmod 3,\qquad n-1-i\equiv 1\pmod 3$$
olmalıdır. Bu da \(n-1\equiv 0\pmod 3\) ve dolayısıyla
$$V_n\neq 0\implies n\equiv 1\pmod 3$$
demektir. \(U_n\) için \(V_{n-1}\) terimi ancak \(n-1\equiv 1\pmod 3\) ise katkı verir; evrişim kısmında ise
$$2+2\equiv 1\pmod 3$$
olduğundan yine
$$U_n\neq 0\implies n\equiv 2\pmod 3$$
zorunlu olur. Son olarak \(E_n\) için, \(U\)'dan gelen bir \(2\) kalanı ile \(E\)'den gelen bir \(0\) kalanı birleşir ve
$$E_n\neq 0\implies n\equiv 0\pmod 3$$
elde edilir. Bu artık sınıfı davranışı, problemdeki triplicate yapının bağıntılardaki en belirgin izidir.
Sadece her üçüncü terim yaşadığı için
$$A_k=U_{3k+2},\qquad B_k=V_{3k+1},\qquad C_k=E_{3k}$$
tanımlarını yapalım. O zaman
$$A_0=1,\qquad B_0=1,\qquad C_0=1,$$
ve \(k\ge 1\) için
$$B_k=9\sum_{a=0}^{k-1}A_aB_{k-1-a},$$
$$A_k=B_k+9\sum_{a=0}^{k-1}A_aA_{k-1-a},$$
$$C_k=10\sum_{a=0}^{k-1}A_aC_{k-1-a}$$
elde edilir. Hedef toplam da
$$T(N)=\frac{9}{10}\sum_{k=1}^{\lfloor N/3\rfloor}C_k$$
şeklini alır. Bu yeniden indisleme matematiği değiştirmez; sadece \(B\)'nin \(A\)'yı, \(A\)'nın da \(C\)'yi nasıl beslediğini daha görünür hale getirir.
\(A_0=B_0=C_0=1\) ile başlayalım. Sonraki değerler:
$$B_1=9A_0B_0=9,$$
$$A_1=B_1+9A_0A_0=9+9=18,$$
$$C_1=10A_0C_0=10.$$
Bir tur daha gidersek
$$B_2=9(A_0B_1+A_1B_0)=9(9+18)=243,$$
$$A_2=B_2+9(A_0A_1+A_1A_0)=243+9(18+18)=567,$$
$$C_2=10(A_0C_1+A_1C_0)=10(10+18)=280$$
bulunur. Orijinal indislemeye geri dönersek
$$E_3=10,\qquad E_6=280.$$
Dolayısıyla
$$T(6)=\frac{9}{10}(E_3+E_6)=\frac{9}{10}(10+280)=261,$$
ki bu, uygulamadaki tam sayılı küçük-\(N\) doğrulamasıyla aynıdır.
Gerçek görevde program şu değeri hesaplar:
$$T(10^4)\equiv 9\cdot 10^{-1}\sum_{n=1}^{10^4}E_n\pmod M.$$
Yalnızca \(3\)'ün katı indisler katkı verdiği için bu aynı zamanda
$$T(10^4)\equiv 9\cdot 10^{-1}\sum_{k=1}^{\lfloor 10^4/3\rfloor}C_k\pmod M$$
demektir. \(M\) asal olduğundan modüler ters, Fermat'nın küçük teoremiyle bulunur:
$$10^{-1}\equiv 10^{M-2}\pmod M.$$
C++, Python ve Java uygulamaları aynı akışı izler. Önce \(U\), \(V\) ve \(E\) için \(N+1\) uzunluğunda üç dizi ayrılır ve başlangıç koşulu olarak \(E_0=1\) atanır. Ardından \(n=1\)'den \(n=N\)'e kadar ileri doğru gidilir.
İlk geçişte her \(n\) için iki evrişim toplamı aynı anda hesaplanır: biri \(U_iV_{n-1-i}\), diğeri \(U_iU_{n-1-i}\) içindir. Bu iki toplam hemen \(V_n\) ve \(U_n\) değerlerini üretir. İkinci geçişte ise \(E_n\), \(U\) ile \(E\)'nin evrişiminden hesaplanır.
Tüm \(E_n\) değerleri hazır olduğunda uygulama
$$\sum_{n=1}^{N}E_n$$
toplamını alır ve bunu \(9\cdot 10^{-1}\bmod M\) ile çarpar. C++ uygulaması ayrıca modüler koşudan önce küçük \(N\) için tam sayılı tutarlılık kontrolleri yapar; bunların arasında
$$T(6)=261$$
ve \(N=30\) için daha büyük bir referans değer de vardır. Bu kontroller, indis veya bağıntı hatalarını erken yakalamaya yarar.
\(N\) istenen boyut üst sınırı olsun. İlk aşama her \(n\) için uzunluğu \(n\) olan iki evrişim, ikinci aşama ise yine uzunluğu \(n\) olan bir evrişim hesaplar. Bu yüzden toplam iş miktarı
$$\sum_{n=1}^{N} n = O(N^2)$$
mertebesindedir. Başka bir deyişle yaklaşık üç üçgensel evrişim geçişi yapılır; sabit katsayı makuldür ama asimptotik düzen yine ikinci derecedir. Bellek kullanımı \(O(N)\)'dir, çünkü yalnızca üç tek boyutlu dizi saklanır.
En el Problema 865 la solución no intenta enumerar directamente los números válidos. En su lugar, evalúa una función de conteo \(T(N)\) en \(N=10^4\) módulo el primo
$$M=998244353.$$
Todo el problema queda codificado en tres sucesiones acopladas \(U_n\), \(V_n\) y \(E_n\). Sus recurrencias describen cómo se construyen estructuras válidas de tamaño total \(n\) a partir de piezas más pequeñas, y la respuesta final se extrae de la sucesión \(E_n\).
Las implementaciones en C++, Python y Java usan las mismas tres recurrencias:
$$V_1=1,\qquad V_n=9\sum_{i=0}^{n-1}U_iV_{n-1-i}\quad (n\ge 2),$$
$$U_n=V_{n-1}+9\sum_{i=0}^{n-1}U_iU_{n-1-i}\quad (n\ge 1),$$
$$E_0=1,\qquad E_n=10\sum_{i=0}^{n-1}U_iE_{n-1-i}\quad (n\ge 1).$$
La cantidad objetivo es
$$T(N)=\sum_{n=1}^{N}\frac{9E_n}{10}.$$
Como cada \(E_n\) con \(n\ge 1\) es múltiplo de \(10\), esta expresión es entera en aritmética exacta.
Cada suma recorre todas las descomposiciones de \(n-1\) en
$$i+(n-1-i).$$
Eso es exactamente el patrón del producto de Cauchy: dos estructuras pequeñas se combinan para formar una más grande. Los factores \(9\) y \(10\) son pesos fijos que provienen del modelo decimal del conteo. Así, el problema se convierte en calcular convoluciones en vez de recorrer enteros uno por uno.
Esta lectura explica de inmediato por qué la programación dinámica funciona: cada valor de tamaño \(n\) depende solo de tamaños menores.
Introducimos las series formales
$$U(z)=\sum_{n\ge 0}U_nz^n,\qquad V(z)=\sum_{n\ge 1}V_nz^n,\qquad E(z)=\sum_{n\ge 0}E_nz^n.$$
Las recurrencias se transforman en
$$V(z)=z+9z\,U(z)V(z),$$
$$U(z)=zV(z)+9z\,U(z)^2,$$
$$E(z)=1+10z\,U(z)E(z)=\frac{1}{1-10z\,U(z)}.$$
La primera identidad muestra que \(V\) es una semilla básica \(z\) más una corrección recursiva. La tercera es especialmente útil: una vez conocido \(U(z)\), la serie \(E(z)\) aparece como una transformación geométrica simple.
También puede eliminarse \(V(z)\):
$$V(z)=\frac{z}{1-9z\,U(z)},$$
lo que conduce a la relación cúbica
$$81z^2U(z)^3-18zU(z)^2+U(z)-z^2=0.$$
La implementación no resuelve ese cúbico de forma simbólica, pero la identidad sirve como verificación algebraica del sistema.
Los primeros valores exactos ya muestran un patrón rígido:
$$V_1=1,\qquad U_2=1,\qquad E_3=10,$$
y después todos los términos no nulos siguen apareciendo separados por \(3\). No es casual.
Supongamos por inducción que \(U_n\) solo puede ser no nulo cuando \(n\equiv 2\pmod 3\), y que \(V_n\) solo puede ser no nulo cuando \(n\equiv 1\pmod 3\). En la recurrencia de \(V_n\), un sumando no nulo exige
$$i\equiv 2\pmod 3,\qquad n-1-i\equiv 1\pmod 3,$$
de donde se obtiene \(n-1\equiv 0\pmod 3\), es decir,
$$V_n\neq 0\implies n\equiv 1\pmod 3.$$
Para \(U_n\), el término \(V_{n-1}\) solo aporta cuando \(n-1\equiv 1\pmod 3\), y el término de convolución necesita
$$2+2\equiv 1\pmod 3,$$
lo que fuerza
$$U_n\neq 0\implies n\equiv 2\pmod 3.$$
Finalmente, en \(E_n\) un índice de \(U\) con residuo \(2\) debe emparejarse con un índice de \(E\) con residuo \(0\), así que
$$E_n\neq 0\implies n\equiv 0\pmod 3.$$
Este comportamiento por clases de residuos es la huella algebraica más clara del carácter triplicado del problema.
Como solo sobrevive uno de cada tres términos, definimos
$$A_k=U_{3k+2},\qquad B_k=V_{3k+1},\qquad C_k=E_{3k}.$$
Entonces
$$A_0=1,\qquad B_0=1,\qquad C_0=1,$$
y para \(k\ge 1\) las recurrencias se simplifican a
$$B_k=9\sum_{a=0}^{k-1}A_aB_{k-1-a},$$
$$A_k=B_k+9\sum_{a=0}^{k-1}A_aA_{k-1-a},$$
$$C_k=10\sum_{a=0}^{k-1}A_aC_{k-1-a}.$$
La suma objetivo pasa a ser
$$T(N)=\frac{9}{10}\sum_{k=1}^{\lfloor N/3\rfloor}C_k.$$
Esta reindexación no cambia la matemática, pero hace mucho más visible la dependencia en cadena: \(B\) alimenta a \(A\), y \(A\) alimenta a \(C\).
Empezando con \(A_0=B_0=C_0=1\), se obtiene
$$B_1=9A_0B_0=9,$$
$$A_1=B_1+9A_0A_0=9+9=18,$$
$$C_1=10A_0C_0=10.$$
Una ronda más da
$$B_2=9(A_0B_1+A_1B_0)=9(9+18)=243,$$
$$A_2=B_2+9(A_0A_1+A_1A_0)=243+9(18+18)=567,$$
$$C_2=10(A_0C_1+A_1C_0)=10(10+18)=280.$$
Volviendo a los índices originales, esto significa
$$E_3=10,\qquad E_6=280.$$
Por tanto,
$$T(6)=\frac{9}{10}(E_3+E_6)=\frac{9}{10}(10+280)=261,$$
que coincide con la verificación exacta para tamaño pequeño incluida en la implementación.
Para la tarea real, el programa evalúa
$$T(10^4)\equiv 9\cdot 10^{-1}\sum_{n=1}^{10^4}E_n\pmod M,$$
y como solo cuentan los índices divisibles por \(3\), esto equivale a
$$T(10^4)\equiv 9\cdot 10^{-1}\sum_{k=1}^{\lfloor 10^4/3\rfloor}C_k\pmod M.$$
Puesto que \(M\) es primo, el inverso modular se obtiene con el pequeño teorema de Fermat:
$$10^{-1}\equiv 10^{M-2}\pmod M.$$
Las implementaciones en C++, Python y Java siguen exactamente el mismo esquema. Primero reservan tres arreglos de longitud \(N+1\) para \(U\), \(V\) y \(E\), con la condición inicial \(E_0=1\). Luego recorren \(n=1,2,\dots,N\).
En la primera pasada, cada \(n\) calcula dos sumas de convolución a la vez: una para el producto mixto \(U_iV_{n-1-i}\) y otra para el producto \(U_iU_{n-1-i}\). Con ellas se obtienen directamente \(V_n\) y \(U_n\). En la segunda pasada, \(E_n\) se construye a partir de la convolución entre \(U\) y \(E\).
Cuando todos los \(E_n\) ya están disponibles, la implementación acumula
$$\sum_{n=1}^{N}E_n$$
y multiplica por \(9\cdot 10^{-1}\bmod M\). La versión en C++ además realiza comprobaciones exactas para valores pequeños de \(N\), entre ellas
$$T(6)=261$$
y un valor exacto mayor en \(N=30\). Eso ayuda a detectar errores de recurrencia o de indexación.
Sea \(N\) el límite de tamaño. La primera fase calcula dos convoluciones de longitud \(n\) para cada \(n\), y la segunda fase calcula una más de longitud \(n\). Por ello, el trabajo total es proporcional a
$$\sum_{n=1}^{N} n = O(N^2).$$
En términos prácticos, son unas tres pasadas triangulares de convolución; el factor constante es razonable, pero el orden asintótico sigue siendo cuadrático. La memoria usada es \(O(N)\), porque solo se almacenan tres arreglos unidimensionales.
对于第 865 题，程序并不是直接枚举所有满足条件的数字，而是把问题转写成一个计数函数 \(T(N)\)，并在
$$N=10^4,\qquad M=998244353$$
这个素数模数下求值。整个计数过程由三个相互耦合的数列 \(U_n\)、\(V_n\) 与 \(E_n\) 驱动。它们的递推式描述了总规模为 \(n\) 的合法结构如何由更小的结构拼接而成，而最终答案则从 \(E_n\) 中提取出来。
C++、Python 和 Java 实现使用的是同一组递推关系：
$$V_1=1,\qquad V_n=9\sum_{i=0}^{n-1}U_iV_{n-1-i}\quad (n\ge 2),$$
$$U_n=V_{n-1}+9\sum_{i=0}^{n-1}U_iU_{n-1-i}\quad (n\ge 1),$$
$$E_0=1,\qquad E_n=10\sum_{i=0}^{n-1}U_iE_{n-1-i}\quad (n\ge 1).$$
目标量定义为
$$T(N)=\sum_{n=1}^{N}\frac{9E_n}{10}.$$
由于所有 \(n\ge 1\) 的 \(E_n\) 都天然带有一个因子 \(10\)，所以在精确整数运算里这也是逐项成立的整数表达式。
每个求和都在遍历 \(n-1\) 的所有拆分方式
$$i+(n-1-i).$$
这正是 Cauchy 乘积的标准形式：两个较小对象拼成一个较大的对象。递推中的系数 \(9\) 和 \(10\) 是十进制计数模型带来的固定权重，因此程序真正做的不是暴力枚举整数，而是不断计算卷积和。
一旦从这个角度理解问题，动态规划为什么可行就非常清楚了：规模为 \(n\) 的值只依赖于更小规模的结果。
定义形式幂级数
$$U(z)=\sum_{n\ge 0}U_nz^n,\qquad V(z)=\sum_{n\ge 1}V_nz^n,\qquad E(z)=\sum_{n\ge 0}E_nz^n.$$
那么递推可以改写为
$$V(z)=z+9z\,U(z)V(z),$$
$$U(z)=zV(z)+9z\,U(z)^2,$$
$$E(z)=1+10z\,U(z)E(z)=\frac{1}{1-10z\,U(z)}.$$
第一式表明 \(V\) 由最初的种子项 \(z\) 出发，再叠加递归修正。第三式尤其重要，因为一旦知道 \(U(z)\)，\(E(z)\) 就是一个标准的几何级数型变换。
还可以先消去 \(V(z)\)：
$$V(z)=\frac{z}{1-9z\,U(z)},$$
于是得到关于 \(U(z)\) 的三次关系
$$81z^2U(z)^3-18zU(z)^2+U(z)-z^2=0.$$
实现本身并没有去符号求解这个三次方程，但它很好地说明了整个递推系统的代数一致性。
前几个精确值已经表现出非常强的规律：
$$V_1=1,\qquad U_2=1,\qquad E_3=10,$$
之后所有非零项都每隔 \(3\) 个位置才出现一次。这不是偶然，而是递推本身强制出来的。
设归纳假设为：只有当 \(n\equiv 2\pmod 3\) 时 \(U_n\) 才可能非零，而只有当 \(n\equiv 1\pmod 3\) 时 \(V_n\) 才可能非零。要使 \(V_n\) 的卷积项非零，必须满足
$$i\equiv 2\pmod 3,\qquad n-1-i\equiv 1\pmod 3,$$
因此 \(n-1\equiv 0\pmod 3\)，也就是
$$V_n\neq 0\implies n\equiv 1\pmod 3.$$
对 \(U_n\) 来说，单独的 \(V_{n-1}\) 项只有在 \(n-1\equiv 1\pmod 3\) 时才可能非零，而卷积项中两边都来自 \(U\)，所以需要
$$2+2\equiv 1\pmod 3,$$
从而推出
$$U_n\neq 0\implies n\equiv 2\pmod 3.$$
最后，\(E_n\) 的卷积必须把一个模 \(3\) 余 \(2\) 的 \(U\) 项和一个模 \(3\) 余 \(0\) 的 \(E\) 项配对，因此
$$E_n\neq 0\implies n\equiv 0\pmod 3.$$
这种按余数类分层的现象，是题目中 “triplicate” 结构在递推方程里的最直接体现。
既然只有每三个位置中的一个会留下来，就定义
$$A_k=U_{3k+2},\qquad B_k=V_{3k+1},\qquad C_k=E_{3k}.$$
于是初值变成
$$A_0=1,\qquad B_0=1,\qquad C_0=1,$$
并且对 \(k\ge 1\) 有更紧凑的递推：
$$B_k=9\sum_{a=0}^{k-1}A_aB_{k-1-a},$$
$$A_k=B_k+9\sum_{a=0}^{k-1}A_aA_{k-1-a},$$
$$C_k=10\sum_{a=0}^{k-1}A_aC_{k-1-a}.$$
最终目标也可写成
$$T(N)=\frac{9}{10}\sum_{k=1}^{\lfloor N/3\rfloor}C_k.$$
这一步并没有改变数学本质，只是把原来稀疏的序列重新压缩，令依赖关系更清楚：\(B\) 先生成 \(A\)，再由 \(A\) 生成 \(C\)。
从 \(A_0=B_0=C_0=1\) 出发，第一轮得到
$$B_1=9A_0B_0=9,$$
$$A_1=B_1+9A_0A_0=9+9=18,$$
$$C_1=10A_0C_0=10.$$
再算一轮：
$$B_2=9(A_0B_1+A_1B_0)=9(9+18)=243,$$
$$A_2=B_2+9(A_0A_1+A_1A_0)=243+9(18+18)=567,$$
$$C_2=10(A_0C_1+A_1C_0)=10(10+18)=280.$$
换回原始下标，就是
$$E_3=10,\qquad E_6=280.$$
因此
$$T(6)=\frac{9}{10}(E_3+E_6)=\frac{9}{10}(10+280)=261,$$
这与实现中用于校验的小规模精确结果完全一致。
真正求解时，程序计算的是
$$T(10^4)\equiv 9\cdot 10^{-1}\sum_{n=1}^{10^4}E_n\pmod M.$$
由于只有 \(3\) 的倍数下标会贡献非零项，这也等价于
$$T(10^4)\equiv 9\cdot 10^{-1}\sum_{k=1}^{\lfloor 10^4/3\rfloor}C_k\pmod M.$$
因为 \(M\) 是素数，所以 \(10\) 的模逆由费马小定理给出：
$$10^{-1}\equiv 10^{M-2}\pmod M.$$
C++、Python 和 Java 实现的流程完全一致。首先分配长度为 \(N+1\) 的三个数组来存储 \(U\)、\(V\) 和 \(E\)，并设定初始条件 \(E_0=1\)。随后按 \(n=1,2,\dots,N\) 的顺序向前推进。
第一遍循环里，每个 \(n\) 同时计算两个卷积和：一个是 \(U_iV_{n-1-i}\)，另一个是 \(U_iU_{n-1-i}\)。这两项立刻产生 \(V_n\) 与 \(U_n\)。第二遍循环则计算 \(U\) 与 \(E\) 的卷积，从而得到 \(E_n\)。
当所有 \(E_n\) 都准备好以后，实现会累加
$$\sum_{n=1}^{N}E_n$$
并再乘上 \(9\cdot 10^{-1}\bmod M\)。其中 C++ 实现还会在模运算之前做若干小规模精确校验，包括
$$T(6)=261$$
以及 \(N=30\) 时的一个更大精确值。这些检查可以有效防止递推或下标处理出错。
设 \(N\) 为目标规模上界。第一阶段对每个 \(n\) 计算两个长度为 \(n\) 的卷积，第二阶段再计算一个长度为 \(n\) 的卷积，因此总工作量与
$$\sum_{n=1}^{N} n = O(N^2)$$
同阶。更直观地说，算法大约进行了三次三角形卷积扫描，所以常数不算大，但渐近复杂度仍然是二次的。空间复杂度为 \(O(N)\)，因为只需要保存三个一维数组。
В задаче 865 программа не перебирает допустимые числа напрямую. Вместо этого она вычисляет счетную функцию \(T(N)\) при \(N=10^4\) по модулю простого числа
$$M=998244353.$$
Вся структура решения зашита в три связанные последовательности \(U_n\), \(V_n\) и \(E_n\). Их рекуррентные формулы описывают, как допустимый объект размера \(n\) собирается из меньших объектов, а окончательный результат извлекается из последовательности \(E_n\).
Реализации на C++, Python и Java используют одну и ту же систему рекурсий:
$$V_1=1,\qquad V_n=9\sum_{i=0}^{n-1}U_iV_{n-1-i}\quad (n\ge 2),$$
$$U_n=V_{n-1}+9\sum_{i=0}^{n-1}U_iU_{n-1-i}\quad (n\ge 1),$$
$$E_0=1,\qquad E_n=10\sum_{i=0}^{n-1}U_iE_{n-1-i}\quad (n\ge 1).$$
Искомая величина задается формулой
$$T(N)=\sum_{n=1}^{N}\frac{9E_n}{10}.$$
Так как каждое \(E_n\) при \(n\ge 1\) кратно \(10\), эта сумма корректна и в точной целой арифметике.
Каждая сумма перебирает все разложения числа \(n-1\) в виде
$$i+(n-1-i).$$
Это в точности схема произведения Коши: два меньших объекта объединяются в один больший. Коэффициенты \(9\) и \(10\) являются фиксированными весами, идущими от десятичной природы модели. Поэтому задача сводится не к перебору самих чисел, а к вычислению сверток.
Отсюда сразу видно, почему работает динамическое программирование: значение размера \(n\) зависит только от меньших размеров.
Введем формальные степенные ряды
$$U(z)=\sum_{n\ge 0}U_nz^n,\qquad V(z)=\sum_{n\ge 1}V_nz^n,\qquad E(z)=\sum_{n\ge 0}E_nz^n.$$
Тогда рекурсии переписываются так:
$$V(z)=z+9z\,U(z)V(z),$$
$$U(z)=zV(z)+9z\,U(z)^2,$$
$$E(z)=1+10z\,U(z)E(z)=\frac{1}{1-10z\,U(z)}.$$
Первая формула показывает, что \(V\) строится из базового зерна \(z\) и рекурсивной поправки. Третья особенно удобна: если известна \(U(z)\), то \(E(z)\) получается как геометрический тип преобразования.
Можно также исключить \(V(z)\):
$$V(z)=\frac{z}{1-9z\,U(z)},$$
после чего возникает кубическое соотношение
$$81z^2U(z)^3-18zU(z)^2+U(z)-z^2=0.$$
Код не решает этот кубик в явном виде, но сама формула полезна как алгебраическая проверка системы.
Первые точные значения уже демонстрируют строгий шаблон:
$$V_1=1,\qquad U_2=1,\qquad E_3=10,$$
а затем все ненулевые члены снова появляются только через \(3\) позиции. Это не совпадение.
Предположим по индукции, что \(U_n\) может быть ненулевым только при \(n\equiv 2\pmod 3\), а \(V_n\) только при \(n\equiv 1\pmod 3\). Для ненулевого слагаемого в рекурсии для \(V_n\) необходимо
$$i\equiv 2\pmod 3,\qquad n-1-i\equiv 1\pmod 3,$$
значит \(n-1\equiv 0\pmod 3\), то есть
$$V_n\neq 0\implies n\equiv 1\pmod 3.$$
Для \(U_n\) одиночный член \(V_{n-1}\) ненулевой только при \(n-1\equiv 1\pmod 3\), а в свертке нужно
$$2+2\equiv 1\pmod 3,$$
поэтому получается
$$U_n\neq 0\implies n\equiv 2\pmod 3.$$
Наконец, в формуле для \(E_n\) индекс из \(U\) с остатком \(2\) должен сочетаться с индексом из \(E\) с остатком \(0\), откуда
$$E_n\neq 0\implies n\equiv 0\pmod 3.$$
Именно это поведение по классам вычетов является самым наглядным алгебраическим следом трипликативной структуры задачи.
Поскольку выживает только каждый третий индекс, удобно положить
$$A_k=U_{3k+2},\qquad B_k=V_{3k+1},\qquad C_k=E_{3k}.$$
Тогда начальные значения равны
$$A_0=1,\qquad B_0=1,\qquad C_0=1,$$
а при \(k\ge 1\) система упрощается до
$$B_k=9\sum_{a=0}^{k-1}A_aB_{k-1-a},$$
$$A_k=B_k+9\sum_{a=0}^{k-1}A_aA_{k-1-a},$$
$$C_k=10\sum_{a=0}^{k-1}A_aC_{k-1-a}.$$
Целевая сумма принимает вид
$$T(N)=\frac{9}{10}\sum_{k=1}^{\lfloor N/3\rfloor}C_k.$$
Переиндексация не меняет математику, но делает зависимость последовательностей намного прозрачнее: \(B\) порождает \(A\), а \(A\) порождает \(C\).
Стартуем с \(A_0=B_0=C_0=1\). Тогда
$$B_1=9A_0B_0=9,$$
$$A_1=B_1+9A_0A_0=9+9=18,$$
$$C_1=10A_0C_0=10.$$
Следующий шаг дает
$$B_2=9(A_0B_1+A_1B_0)=9(9+18)=243,$$
$$A_2=B_2+9(A_0A_1+A_1A_0)=243+9(18+18)=567,$$
$$C_2=10(A_0C_1+A_1C_0)=10(10+18)=280.$$
В исходной нумерации это означает
$$E_3=10,\qquad E_6=280.$$
Следовательно,
$$T(6)=\frac{9}{10}(E_3+E_6)=\frac{9}{10}(10+280)=261,$$
что в точности совпадает с малой точной проверкой, заложенной в реализации.
В реальном запуске программа считает
$$T(10^4)\equiv 9\cdot 10^{-1}\sum_{n=1}^{10^4}E_n\pmod M,$$
а поскольку вклад дают только индексы, кратные \(3\), это то же самое, что
$$T(10^4)\equiv 9\cdot 10^{-1}\sum_{k=1}^{\lfloor 10^4/3\rfloor}C_k\pmod M.$$
Так как \(M\) простое, обратный к \(10\) элемент находится по малой теореме Ферма:
$$10^{-1}\equiv 10^{M-2}\pmod M.$$
Реализации на C++, Python и Java устроены одинаково. Сначала выделяются три массива длины \(N+1\) для \(U\), \(V\) и \(E\), и задается начальное условие \(E_0=1\). Затем цикл идет вперед по \(n=1,2,\dots,N\).
На первом проходе для каждого \(n\) одновременно вычисляются две свертки: смешанная \(U_iV_{n-1-i}\) и квадратурная \(U_iU_{n-1-i}\). Из них сразу получаются значения \(V_n\) и \(U_n\). На втором проходе вычисляется свертка \(U\) с \(E\), из которой строится \(E_n\).
После этого программа накапливает сумму
$$\sum_{n=1}^{N}E_n$$
и умножает результат на \(9\cdot 10^{-1}\bmod M\). Реализация на C++ дополнительно содержит точные проверки для малых \(N\), включая
$$T(6)=261$$
и более крупное точное контрольное значение при \(N=30\). Это помогает быстро заметить ошибки в формулах и индексах.
Пусть \(N\) — верхняя граница размера. На первой фазе для каждого \(n\) считаются две свертки длины \(n\), на второй фазе — еще одна свертка длины \(n\). Поэтому общий объем работы пропорционален
$$\sum_{n=1}^{N} n = O(N^2).$$
Иначе говоря, алгоритм выполняет примерно три треугольных прохода по сверткам. Константа умеренная, но асимптотически метод квадратичный. Память равна \(O(N)\), потому что хранятся только три одномерных массива.
في المسألة 865 لا تحاول الخوارزمية تعداد الأعداد الصالحة مباشرة. بدلًا من ذلك تحسب دالة عدّ \(T(N)\) عند \(N=10^4\) بترديد العدد الأولي
$$M=998244353.$$
جوهر المسألة كلّه مضغوط داخل ثلاث متتاليات مترابطة هي \(U_n\) و\(V_n\) و\(E_n\). علاقات الرجوع بينها تصف كيف تُبنى البنى الصحيحة ذات الحجم الكلي \(n\) انطلاقًا من بنيات أصغر، ثم تُستخرج النتيجة النهائية من متتالية \(E_n\).
تستخدم تطبيقات C++ وPython وJava نفس العلاقات الثلاث:
$$V_1=1,\qquad V_n=9\sum_{i=0}^{n-1}U_iV_{n-1-i}\quad (n\ge 2),$$
$$U_n=V_{n-1}+9\sum_{i=0}^{n-1}U_iU_{n-1-i}\quad (n\ge 1),$$
$$E_0=1,\qquad E_n=10\sum_{i=0}^{n-1}U_iE_{n-1-i}\quad (n\ge 1).$$
أما الكمية المطلوبة فهي
$$T(N)=\sum_{n=1}^{N}\frac{9E_n}{10}.$$
وبما أن كل \(E_n\) عندما \(n\ge 1\) يكون من مضاعفات \(10\)، فإن هذه الصيغة صحيحة أيضًا في الحساب الصحيح غير المعياري.
كل مجموع يمر على جميع تفكيكات \(n-1\) من الصورة
$$i+(n-1-i).$$
وهذا بالضبط نمط حاصل Cauchy: نجمع بنيتين أصغر لنحصل على بنية أكبر. أما المعاملان \(9\) و\(10\) فهما أوزان ثابتة تأتي من البنية العشرية الكامنة في نموذج العد. لذلك تتحول المسألة من فحص الأعداد واحدًا واحدًا إلى حساب مجاميع التفاف.
ومن هنا يتضح سبب نجاح البرمجة الديناميكية: قيمة الحجم \(n\) تعتمد فقط على قيم بأحجام أصغر.
نعرف السلاسل الشكلية التالية:
$$U(z)=\sum_{n\ge 0}U_nz^n,\qquad V(z)=\sum_{n\ge 1}V_nz^n,\qquad E(z)=\sum_{n\ge 0}E_nz^n.$$
فتصبح العلاقات
$$V(z)=z+9z\,U(z)V(z),$$
$$U(z)=zV(z)+9z\,U(z)^2,$$
$$E(z)=1+10z\,U(z)E(z)=\frac{1}{1-10z\,U(z)}.$$
المعادلة الأولى تقول إن \(V\) يبدأ ببذرة أساسية \(z\) ثم يُصحَّح بشكل تراجعي. أما الثالثة فهي الأكثر فائدة، لأنها تعطي \(E(z)\) مباشرة على هيئة تحويل شبيه بالسلسلة الهندسية متى عرفنا \(U(z)\).
كما يمكن حذف \(V(z)\) باستعمال
$$V(z)=\frac{z}{1-9z\,U(z)},$$
فنحصل على العلاقة التكعيبية
$$81z^2U(z)^3-18zU(z)^2+U(z)-z^2=0.$$
التنفيذ لا يحل هذا التكعيبي رمزيًا، لكنه مفيد جدًا كفحص جبري لتماسك النظام كله.
أول القيم الدقيقة تكشف نمطًا صارمًا:
$$V_1=1,\qquad U_2=1,\qquad E_3=10,$$
ثم تستمر جميع الحدود غير الصفرية بالظهور كل ثلاث مراتب فقط. هذا ليس عرضًا جانبيًا، بل نتيجة مباشرة للعلاقات.
افترض استقرائيًا أن \(U_n\) لا يكون غير صفري إلا عندما
$$n\equiv 2\pmod 3,$$
وأن \(V_n\) لا يكون غير صفري إلا عندما
$$n\equiv 1\pmod 3.$$
لكي يكون حد في علاقة \(V_n\) غير صفري، لا بد أن يتحقق
$$i\equiv 2\pmod 3,\qquad n-1-i\equiv 1\pmod 3,$$
ومن ثم \(n-1\equiv 0\pmod 3\)، أي
$$V_n\neq 0\implies n\equiv 1\pmod 3.$$
وبالنسبة إلى \(U_n\)، فإن الحد \(V_{n-1}\) لا يساهم إلا إذا كان \(n-1\equiv 1\pmod 3\)، أما حد الالتفاف فيحتاج إلى
$$2+2\equiv 1\pmod 3,$$
فتنتج القاعدة
$$U_n\neq 0\implies n\equiv 2\pmod 3.$$
وأخيرًا، في علاقة \(E_n\) يجب أن يقترن فهرس من \(U\) بباقي \(2\) مع فهرس من \(E\) بباقي \(0\)، لذا
$$E_n\neq 0\implies n\equiv 0\pmod 3.$$
هذه الطبقات حسب بواقي القسمة على \(3\) هي أوضح أثر جبري لفكرة التثليث التي يحملها السؤال.
بما أن حدًا واحدًا فقط من كل ثلاثة حدود يبقى غير صفري، فمن الطبيعي أن نعرّف
$$A_k=U_{3k+2},\qquad B_k=V_{3k+1},\qquad C_k=E_{3k}.$$
عندها تصبح القيم الابتدائية
$$A_0=1,\qquad B_0=1,\qquad C_0=1,$$
ولكل \(k\ge 1\) نحصل على النظام المضغوط
$$B_k=9\sum_{a=0}^{k-1}A_aB_{k-1-a},$$
$$A_k=B_k+9\sum_{a=0}^{k-1}A_aA_{k-1-a},$$
$$C_k=10\sum_{a=0}^{k-1}A_aC_{k-1-a}.$$
كما تصبح دالة الهدف
$$T(N)=\frac{9}{10}\sum_{k=1}^{\lfloor N/3\rfloor}C_k.$$
إعادة الفهرسة هذه لا تغيّر المحتوى الرياضي، لكنها تجعل الاعتماد بين السلاسل أوضح بكثير: \(B\) يغذي \(A\)، و\(A\) يغذي \(C\).
انطلاقًا من \(A_0=B_0=C_0=1\) نحصل على
$$B_1=9A_0B_0=9,$$
$$A_1=B_1+9A_0A_0=9+9=18,$$
$$C_1=10A_0C_0=10.$$
وفي الجولة التالية:
$$B_2=9(A_0B_1+A_1B_0)=9(9+18)=243,$$
$$A_2=B_2+9(A_0A_1+A_1A_0)=243+9(18+18)=567,$$
$$C_2=10(A_0C_1+A_1C_0)=10(10+18)=280.$$
وبالعودة إلى الفهرسة الأصلية فهذا يعني
$$E_3=10,\qquad E_6=280.$$
إذًا
$$T(6)=\frac{9}{10}(E_3+E_6)=\frac{9}{10}(10+280)=261,$$
وهو بالضبط نفس التحقق الصغير الدقيق الذي تستعمله الخوارزمية.
في التشغيل الفعلي يحسب البرنامج
$$T(10^4)\equiv 9\cdot 10^{-1}\sum_{n=1}^{10^4}E_n\pmod M,$$
ومادام الإسهام يأتي فقط من المؤشرات المضاعفة لـ \(3\)، فهذا يكافئ
$$T(10^4)\equiv 9\cdot 10^{-1}\sum_{k=1}^{\lfloor 10^4/3\rfloor}C_k\pmod M.$$
ولأن \(M\) أولي، فإن معكوس \(10\) المعياري يُحسب من مبرهنة فيرما الصغرى:
$$10^{-1}\equiv 10^{M-2}\pmod M.$$
تسير تطبيقات C++ وPython وJava بالطريقة نفسها. أولًا تُنشأ ثلاثة مصفوفات بطول \(N+1\) لحفظ \(U\) و\(V\) و\(E\)، مع الشرط الابتدائي \(E_0=1\). بعد ذلك يجري المرور على \(n=1,2,\dots,N\) تصاعديًا.
في المرور الأول تُحسب عند كل \(n\) مجموعتا التفاف معًا: واحدة للجداء المختلط \(U_iV_{n-1-i}\)، وأخرى للجداء \(U_iU_{n-1-i}\). ومن هذين المجموعين تُستخرج مباشرة القيمتان \(V_n\) و\(U_n\). في المرور الثاني يُحسب \(E_n\) من التفاف \(U\) مع \(E\).
بعد اكتمال جميع قيم \(E_n\)، تجمع الخوارزمية
$$\sum_{n=1}^{N}E_n$$
ثم تضرب الناتج في \(9\cdot 10^{-1}\bmod M\). كما أن تنفيذ C++ يضيف اختبارات دقيقة لأحجام صغيرة قبل الحساب المعياري، ومنها
$$T(6)=261$$
وقيمة مرجعية أكبر عند \(N=30\). هذه خطوة مفيدة جدًا لاكتشاف أخطاء الفهارس أو العلاقات قبل الوصول إلى \(N=10^4\).
إذا كان \(N\) هو الحد الأعلى للحجم، فإن المرحلة الأولى تحسب التفافين بطول \(n\) لكل \(n\)، والمرحلة الثانية تحسب التفافًا ثالثًا بطول \(n\). لذلك يكون العمل الكلي متناسبًا مع
$$\sum_{n=1}^{N} n = O(N^2).$$
وبصورة عملية، لدينا نحو ثلاث تمريرات مثلثية على التفافات؛ لذا يظل الثابت معقولًا لكن الرتبة الأسيمبتوطية تبقى تربيعية. أما الذاكرة فهي \(O(N)\)، لأن المطلوب فقط هو تخزين ثلاث مصفوفات أحادية البعد.