Project Euler 812 asks for the counting function \(S(n)\) associated with a family of dynamical-polynomial configurations, with the final result taken modulo \(998244353\). The key point is that the admissible objects do not need to be generated one by one. They can be encoded inside a product of generating functions, and \(S(n)\) is recovered as a single coefficient.
The implementation reorganizes all positive integers by their odd part. Every index can be written uniquely as \(2^u b\) with \(b\) odd, so the problem splits into independent dyadic chains \(b,2b,4b,\dots\). Counting the allowed contributions of all chains and extracting the coefficient of \(x^n\) gives the desired value.
The arithmetic input for the generating function is the degree contribution
$$c(1)=1,\qquad c(2)=1,\qquad c(m)=\frac{\varphi(m)}{2}\quad (m\ge 3),$$
where \(\varphi\) is Euler's totient function. These values are exactly the numbers precomputed before the coefficient DP begins.
Every positive integer has a unique form
$$m=2^u b,\qquad b\ \text{odd}.$$
For a fixed odd base \(b\), the relevant degrees form the chain
$$c(b),\ c(2b),\ c(4b),\ c(8b),\dots.$$
If \(b\ge 3\) is odd and we define
$$a_b=\frac{\varphi(b)}{2},$$
then multiplicativity of \(\varphi\) implies
$$c(b)=a_b,\qquad c(2b)=a_b,\qquad c(2^u b)=2^{u-1}a_b\quad (u\ge 2).$$
So each ordinary odd-base chain begins as
$$a_b,\ a_b,\ 2a_b,\ 4a_b,\dots.$$
For \(b\ge 3\), define cumulative chain weights
$$W_{b,j}=\sum_{u=0}^{j} c(2^u b).$$
Because the degrees follow the pattern above, these cumulative sums collapse to
$$W_{b,0}=a_b,\qquad W_{b,1}=2a_b,\qquad W_{b,2}=4a_b,\qquad W_{b,j}=2^j a_b.$$
That means the entire chain contributes the ordinary generating factor
$$F_b(x)=\prod_{j\ge 0}\frac{1}{1-x^{W_{b,j}}} =\prod_{j\ge 0}\frac{1}{1-x^{2^j a_b}}.$$
Each factor \((1-x^w)^{-1}\) says that a weight \(w\) may be used any number of times, which is why the code updates coefficients with a forward unbounded-knapsack pass.
The chain starting from \(1\) is not treated by the same unrestricted rule. After the first two low-degree terms are separated, the tail comes from \(4,8,16,\dots\), whose degree contributions are
$$c(4)=1,\qquad c(8)=2,\qquad c(16)=4,\qquad \dots.$$
Its cumulative tail weights are therefore
$$T_j=1+\sum_{u=2}^{j+2} c(2^u)=2^{j+1}\qquad (j\ge 0).$$
The implementation builds two tail products, a symmetric one and an alternating one:
$$P_+(x)=\prod_{j\ge 1}\frac{1}{1-x^{2^j}},\qquad P_-(x)=\prod_{j\ge 1}\frac{1}{1+x^{2^j}}.$$
They are combined into the core polynomial
$$C(x)=\frac{(1+x)P_+(x)+(1-x)P_-(x)}{2}.$$
Finally the exceptional chain contributes
$$F_1(x)=\frac{C(x)}{(1-x)(1-x^2)}.$$
The two denominators correspond exactly to the two cumulative coefficient passes applied after the \(P_+\) and \(P_-\) combination.
All odd bases are independent, so the full generating function is
$$F(x)=F_1(x)\prod_{\substack{b\ge 3\\ b\ \text{odd}}}\ \prod_{j\ge 0}\frac{1}{1-x^{2^j a_b}}.$$
The answer is the coefficient
$$S(n)=[x^n]F(x)\pmod{998244353}.$$
Only weights at most \(n\) matter, because a larger weight can never affect the coefficient of \(x^n\).
This is the smallest nontrivial checkpoint, and the implementations return \(S(2)=6\).
For the exceptional chain, only the weight \(2\) can matter up to degree \(2\). Hence
$$P_+(x)=1+x^2+O(x^3),\qquad P_-(x)=1-x^2+O(x^3),$$
so
$$C(x)=1+O(x^3),\qquad F_1(x)=\frac{1}{(1-x)(1-x^2)}+O(x^3)=1+x+2x^2+O(x^3).$$
Among ordinary odd bases, \(b=3\) has \(a_3=1\), so its factor is also
$$F_3(x)=\frac{1}{(1-x)(1-x^2)}+O(x^3)=1+x+2x^2+O(x^3).$$
Next, \(b=5\) has \(a_5=2\), giving
$$F_5(x)=\frac{1}{1-x^2}+O(x^3)=1+x^2+O(x^3).$$
Every larger odd base starts at degree at least \(3\), so it cannot change the coefficient of \(x^2\). Therefore
$$F(x)=(1+x+2x^2)(1+x+2x^2)(1+x^2)+O(x^3) =1+2x+6x^2+O(x^3),$$
and the coefficient of \(x^2\) is indeed
$$S(2)=6.$$
The C++, Python, and Java implementations follow the same pipeline. First they choose a sieve range proportional to \(n\) and precompute \(\varphi(m)\) for every needed \(m\). From that table they build the degree sequence \(c(m)\).
Next they construct the exceptional odd-base-\(1\) factor. They generate the usable weights \(2,4,8,\dots\), build one coefficient table for \(P_+(x)\) and another for \(P_-(x)\), combine them through the formula for \(C(x)\), and then apply two cumulative passes to account for division by \((1-x)(1-x^2)\).
After that they iterate over odd bases \(b\ge 3\). For each base they accumulate the chain weights \(a_b,2a_b,4a_b,\dots\) until the next one would exceed \(n\). Every such weight performs a forward coefficient update, which is exactly multiplication by \((1-x^w)^{-1}\). When all chains are processed, the coefficient of degree \(n\) is returned modulo \(998244353\).
Let \(M=\Theta(n)\) be the sieve limit chosen by the implementation. Computing all totients up to \(M\) costs \(O(M\log\log M)\) time and \(O(M)\) memory. The exceptional chain contributes only \(O(\log n)\) usable weights. For the ordinary odd bases, let \(W\) be the total number of cumulative weights \(2^j a_b\) that do not exceed \(n\). Each such weight triggers one forward pass over a coefficient table of length \(n+1\), so the DP phase costs \(O(nW)\) time and \(O(n)\) memory. This is a pseudo-polynomial algorithm with linear memory and a one-dimensional state array.
Project Euler 812 verlangt die Berechnung der Zählfunktion \(S(n)\) für eine Familie dynamischer Polynomkonfigurationen, wobei das Ergebnis modulo \(998244353\) genommen wird. Der entscheidende Punkt ist, dass die zulässigen Objekte nicht einzeln erzeugt werden müssen. Stattdessen lassen sie sich in ein Produkt von Erzeugenden Funktionen kodieren, und \(S(n)\) ist genau ein Koeffizient dieses Produkts.
Die Implementierung ordnet alle positiven ganzen Zahlen nach ihrem ungeraden Anteil. Jede Zahl besitzt die eindeutige Form \(2^u b\) mit ungeradem \(b\), also zerfällt das Problem in unabhängige dyadische Ketten \(b,2b,4b,\dots\). Zählt man die Beiträge aller Ketten und liest den Koeffizienten von \(x^n\) ab, erhält man die gesuchte Antwort.
Die arithmetische Grundlage der Erzeugenden Funktion ist der Gradbeitrag
$$c(1)=1,\qquad c(2)=1,\qquad c(m)=\frac{\varphi(m)}{2}\quad (m\ge 3),$$
wobei \(\varphi\) die Eulersche Phi-Funktion ist. Genau diese Werte werden vor dem Koeffizienten-DP vorbereitet.
Jede positive ganze Zahl lässt sich eindeutig schreiben als
$$m=2^u b,\qquad b\ \text{ungerade}.$$
Für eine feste ungerade Basis \(b\) entsteht die Kette
$$c(b),\ c(2b),\ c(4b),\ c(8b),\dots.$$
Ist \(b\ge 3\) ungerade und wir setzen
$$a_b=\frac{\varphi(b)}{2},$$
dann folgt aus der Multiplikativität von \(\varphi\)
$$c(b)=a_b,\qquad c(2b)=a_b,\qquad c(2^u b)=2^{u-1}a_b\quad (u\ge 2).$$
Eine gewöhnliche ungerade Basiskette beginnt also mit
$$a_b,\ a_b,\ 2a_b,\ 4a_b,\dots.$$
Für \(b\ge 3\) definieren wir kumulative Kettengewichte
$$W_{b,j}=\sum_{u=0}^{j} c(2^u b).$$
Wegen der obigen Struktur vereinfachen sich diese Summen zu
$$W_{b,0}=a_b,\qquad W_{b,1}=2a_b,\qquad W_{b,2}=4a_b,\qquad W_{b,j}=2^j a_b.$$
Damit liefert die gesamte Kette den Faktor
$$F_b(x)=\prod_{j\ge 0}\frac{1}{1-x^{W_{b,j}}} =\prod_{j\ge 0}\frac{1}{1-x^{2^j a_b}}.$$
Jeder Faktor \((1-x^w)^{-1}\) bedeutet, dass ein Gewicht \(w\) beliebig oft verwendet werden darf. Genau deshalb nutzt der Code für jedes Gewicht einen Vorwärtsdurchlauf wie beim unbeschränkten Rucksackproblem.
Die bei \(1\) startende Kette folgt nicht derselben unbeschränkten Regel. Nach dem Abtrennen der beiden kleinsten Gradbeiträge bleibt der Schwanz \(4,8,16,\dots\) mit den Werten
$$c(4)=1,\qquad c(8)=2,\qquad c(16)=4,\qquad \dots.$$
Die kumulativen Schwanzgewichte sind daher
$$T_j=1+\sum_{u=2}^{j+2} c(2^u)=2^{j+1}\qquad (j\ge 0).$$
Die Implementierung baut daraus zwei Produkte, ein symmetrisches und ein alternierendes:
$$P_+(x)=\prod_{j\ge 1}\frac{1}{1-x^{2^j}},\qquad P_-(x)=\prod_{j\ge 1}\frac{1}{1+x^{2^j}}.$$
Diese werden zum Kernpolynom
$$C(x)=\frac{(1+x)P_+(x)+(1-x)P_-(x)}{2}$$
kombiniert. Der vollständige Beitrag der Ausnahmekette lautet dann
$$F_1(x)=\frac{C(x)}{(1-x)(1-x^2)}.$$
Die beiden Nenner entsprechen exakt den beiden kumulativen Koeffizientenpässen, die nach der Kombination von \(P_+\) und \(P_-\) ausgeführt werden.
Alle ungeraden Basen sind unabhängig, also ist die vollständige Erzeugende Funktion
$$F(x)=F_1(x)\prod_{\substack{b\ge 3\\ b\ \text{ungerade}}}\ \prod_{j\ge 0}\frac{1}{1-x^{2^j a_b}}.$$
Die gesuchte Zahl ist der Koeffizient
$$S(n)=[x^n]F(x)\pmod{998244353}.$$
Nur Gewichte bis \(n\) sind relevant, denn größere Gewichte können den Koeffizienten von \(x^n\) nicht mehr beeinflussen.
Dies ist der kleinste nichttriviale Prüfpunkt, und die Implementierungen liefern \(S(2)=6\).
Für die Ausnahmekette kann bis Grad \(2\) nur das Gewicht \(2\) eine Rolle spielen. Daher gilt
$$P_+(x)=1+x^2+O(x^3),\qquad P_-(x)=1-x^2+O(x^3),$$
also
$$C(x)=1+O(x^3),\qquad F_1(x)=\frac{1}{(1-x)(1-x^2)}+O(x^3)=1+x+2x^2+O(x^3).$$
Unter den gewöhnlichen Ketten hat \(b=3\) den Wert \(a_3=1\), also
$$F_3(x)=\frac{1}{(1-x)(1-x^2)}+O(x^3)=1+x+2x^2+O(x^3).$$
Weiter hat \(b=5\) den Wert \(a_5=2\), somit
$$F_5(x)=\frac{1}{1-x^2}+O(x^3)=1+x^2+O(x^3).$$
Jede größere ungerade Basis beginnt erst in Grad mindestens \(3\) und kann den Koeffizienten von \(x^2\) daher nicht ändern. Also
$$F(x)=(1+x+2x^2)(1+x+2x^2)(1+x^2)+O(x^3) =1+2x+6x^2+O(x^3),$$
und damit
$$S(2)=6.$$
Die C++-, Python- und Java-Implementierungen folgen derselben Pipeline. Zuerst wählen sie einen zum \(n\) proportionalen Siebbereich und berechnen \(\varphi(m)\) für alle benötigten \(m\). Daraus wird die Folge \(c(m)\) aufgebaut.
Dann konstruieren sie den Sonderfaktor der ungeraden Basis \(1\). Sie erzeugen die nutzbaren Gewichte \(2,4,8,\dots\), bauen eine Koeffiziententafel für \(P_+(x)\) und eine zweite für \(P_-(x)\), kombinieren beide über die Formel für \(C(x)\) und führen anschließend zwei kumulative Durchläufe aus, die der Division durch \((1-x)(1-x^2)\) entsprechen.
Danach werden alle ungeraden Basen \(b\ge 3\) durchlaufen. Für jede Basis werden die Kettengewichte \(a_b,2a_b,4a_b,\dots\) so lange aufsummiert, bis das nächste Gewicht größer als \(n\) wäre. Jedes dieser Gewichte löst einen Vorwärtsdurchlauf auf der Koeffiziententafel aus, was genau der Multiplikation mit \((1-x^w)^{-1}\) entspricht. Sobald alle Ketten verarbeitet sind, wird der Koeffizient von Grad \(n\) modulo \(998244353\) ausgegeben.
Sei \(M=\Theta(n)\) die vom Programm gewählte Siebgrenze. Das Berechnen aller Totienten bis \(M\) kostet \(O(M\log\log M)\) Zeit und \(O(M)\) Speicher. Die Ausnahmekette liefert nur \(O(\log n)\) relevante Gewichte. Für die gewöhnlichen ungeraden Basen bezeichne \(W\) die Gesamtzahl aller kumulativen Gewichte \(2^j a_b\), die höchstens \(n\) sind. Jedes dieser Gewichte verursacht einen Vorwärtsdurchlauf über eine Koeffiziententafel der Länge \(n+1\), also benötigt die DP-Phase \(O(nW)\) Zeit und \(O(n)\) Speicher. Das Verfahren ist damit pseudo-polynomiell, verwendet aber nur linearen Speicher und einen eindimensionalen Zustand.
Project Euler 812, belirli bir dinamik polinom ailesine karşılık gelen \(S(n)\) sayım fonksiyonunu modulo \(998244353\) altında istemektedir. Kritik fikir, uygun nesneleri tek tek üretmek yerine onları bir üretici fonksiyon çarpımına kodlayabilmektir. Böylece \(S(n)\), bu çarpımın tek bir katsayısına dönüşür.
Uygulama bütün pozitif tamsayıları tek kısmına göre yeniden düzenler. Her indeks \(2^u b\) biçiminde, burada \(b\) tektir, tekil olarak yazılabildiği için problem bağımsız dyadik zincirlere \(b,2b,4b,\dots\) ayrılır. Tüm zincirlerin katkıları sayılıp \(x^n\) katsayısı çekildiğinde aranan değer elde edilir.
Üretici fonksiyonun aritmetik girdisi şu derece katkısıdır:
$$c(1)=1,\qquad c(2)=1,\qquad c(m)=\frac{\varphi(m)}{2}\quad (m\ge 3),$$
burada \(\varphi\), Euler totient fonksiyonudur. Katsayı DP'si başlamadan önce önhesaplanan değerler tam olarak bunlardır.
Her pozitif tamsayı benzersiz biçimde
$$m=2^u b,\qquad b\ \text{tek}$$
şeklinde yazılır. Sabit bir tek taban \(b\) için ilgili derece dizisi
$$c(b),\ c(2b),\ c(4b),\ c(8b),\dots$$
olur. Eğer \(b\ge 3\) tek ve
$$a_b=\frac{\varphi(b)}{2}$$
tanımlanırsa, \(\varphi\)'nin çarpımsallığından
$$c(b)=a_b,\qquad c(2b)=a_b,\qquad c(2^u b)=2^{u-1}a_b\quad (u\ge 2)$$
elde edilir. Yani sıradan bir tek-taban zinciri
$$a_b,\ a_b,\ 2a_b,\ 4a_b,\dots$$
şeklinde başlar.
\(b\ge 3\) için kümülatif zincir ağırlıklarını
$$W_{b,j}=\sum_{u=0}^{j} c(2^u b)$$
olarak tanımlayalım. Yukarıdaki yapı sayesinde bu toplamlar
$$W_{b,0}=a_b,\qquad W_{b,1}=2a_b,\qquad W_{b,2}=4a_b,\qquad W_{b,j}=2^j a_b$$
şeklinde sadeleşir. Demek ki bütün zincirin katkısı
$$F_b(x)=\prod_{j\ge 0}\frac{1}{1-x^{W_{b,j}}} =\prod_{j\ge 0}\frac{1}{1-x^{2^j a_b}}$$
olur. Buradaki her \((1-x^w)^{-1}\) çarpanı, \(w\) ağırlığının sınırsız sayıda seçilebileceğini söyler; kodun her ağırlık için ileri yönlü sınırsız sırt çantası güncellemesi yapmasının nedeni budur.
\(1\) ile başlayan zincir aynı serbest kurala uymaz. İlk iki düşük derece katkısı ayrıldıktan sonra geriye \(4,8,16,\dots\) kuyruğu kalır ve bunların dereceleri
$$c(4)=1,\qquad c(8)=2,\qquad c(16)=4,\qquad \dots$$
şeklindedir. Dolayısıyla kümülatif kuyruk ağırlıkları
$$T_j=1+\sum_{u=2}^{j+2} c(2^u)=2^{j+1}\qquad (j\ge 0)$$
olur. Uygulama burada biri simetrik, diğeri alternanslı iki çarpım kurar:
$$P_+(x)=\prod_{j\ge 1}\frac{1}{1-x^{2^j}},\qquad P_-(x)=\prod_{j\ge 1}\frac{1}{1+x^{2^j}}.$$
Bunlar
$$C(x)=\frac{(1+x)P_+(x)+(1-x)P_-(x)}{2}$$
çekirdek polinomunda birleştirilir. İstisna zincirin tam katkısı ise
$$F_1(x)=\frac{C(x)}{(1-x)(1-x^2)}$$
olur. İki payda, \(P_+\) ve \(P_-\) birleştirildikten sonra uygulanan iki kümülatif katsayı geçişine tam olarak karşılık gelir.
Bütün tek tabanlar birbirinden bağımsızdır; dolayısıyla toplam üretici fonksiyon
$$F(x)=F_1(x)\prod_{\substack{b\ge 3\\ b\ \text{tek}}}\ \prod_{j\ge 0}\frac{1}{1-x^{2^j a_b}}$$
şeklindedir. Aranan cevap
$$S(n)=[x^n]F(x)\pmod{998244353}$$
katsayısıdır. \(n\)'den büyük ağırlıkların hiçbir etkisi yoktur; çünkü onlar \(x^n\) katsayısını değiştiremez.
Bu, en küçük anlamlı kontrol noktasıdır ve uygulamalar \(S(2)=6\) döndürür.
İstisna zincirde derece \(2\)'ye kadar yalnızca \(2\) ağırlığı etkili olabilir. Bu nedenle
$$P_+(x)=1+x^2+O(x^3),\qquad P_-(x)=1-x^2+O(x^3),$$
buradan da
$$C(x)=1+O(x^3),\qquad F_1(x)=\frac{1}{(1-x)(1-x^2)}+O(x^3)=1+x+2x^2+O(x^3)$$
elde edilir. Sıradan zincirler içinde \(b=3\) için \(a_3=1\) olduğundan
$$F_3(x)=\frac{1}{(1-x)(1-x^2)}+O(x^3)=1+x+2x^2+O(x^3),$$
\(b=5\) için \(a_5=2\) olduğundan ise
$$F_5(x)=\frac{1}{1-x^2}+O(x^3)=1+x^2+O(x^3)$$
olur. Daha büyük tek tabanların hepsi en az derece \(3\)'te başlar ve \(x^2\) katsayısını değiştiremez. Dolayısıyla
$$F(x)=(1+x+2x^2)(1+x+2x^2)(1+x^2)+O(x^3) =1+2x+6x^2+O(x^3),$$
yani gerçekten
$$S(2)=6.$$
C++, Python ve Java uygulamaları aynı akışı izler. Önce \(n\) ile orantılı bir eleme sınırı seçilir ve gerekli bütün \(m\) değerleri için \(\varphi(m)\) hesaplanır. Ardından bu tablodan \(c(m)\) dizisi oluşturulur.
Sonra tek tabanı \(1\) olan özel çarpan kurulur. Kullanılabilir ağırlıklar \(2,4,8,\dots\) üretilir; \(P_+(x)\) için bir katsayı tablosu, \(P_-(x)\) için ikinci bir tablo kurulur; bunlar \(C(x)\) formülüyle birleştirilir ve sonrasında \((1-x)(1-x^2)\) ile bölmeyi temsil eden iki kümülatif geçiş uygulanır.
Bundan sonra \(b\ge 3\) olan tüm tek tabanlar dolaşılır. Her taban için zincir ağırlıkları \(a_b,2a_b,4a_b,\dots\) bir sonraki ağırlık \(n\)'i aşana kadar üretilir. Her ağırlık, katsayı tablosu üzerinde ileri yönlü bir güncelleme yapar; bu da tam olarak \((1-x^w)^{-1}\) ile çarpmaya denktir. Tüm zincirler işlendiğinde derece \(n\) katsayısı modulo \(998244353\) döndürülür.
Uygulamanın seçtiği eleme üst sınırı \(M=\Theta(n)\) olsun. \(M\)'ye kadar bütün totient değerlerini hesaplamak \(O(M\log\log M)\) zaman ve \(O(M)\) bellek gerektirir. İstisna zincir yalnızca \(O(\log n)\) kadar kullanılabilir ağırlık üretir. Sıradan tek tabanlar için, \(n\)'i aşmayan tüm \(2^j a_b\) ağırlıklarının toplam sayısına \(W\) diyelim. Her ağırlık, uzunluğu \(n+1\) olan bir katsayı tablosunda tek bir ileri geçiş tetikler; dolayısıyla DP safhası \(O(nW)\) zaman ve \(O(n)\) bellek kullanır. Yöntem pseudo-polynomial yapıdadır, fakat bellek tüketimi lineerdir ve durum uzayı tek boyutludur.
Project Euler 812 pide calcular la función de conteo \(S(n)\) asociada a una familia de configuraciones de polinomios dinámicos, con el resultado final reducido módulo \(998244353\). La idea decisiva es que no hace falta generar los objetos válidos uno por uno. Se pueden codificar dentro de un producto de funciones generadoras, y \(S(n)\) aparece como un único coeficiente.
La implementación reorganiza todos los enteros positivos según su parte impar. Cada índice se escribe de forma única como \(2^u b\) con \(b\) impar, de modo que el problema se separa en cadenas diádicas independientes \(b,2b,4b,\dots\). Al contar la contribución de todas esas cadenas y extraer el coeficiente de \(x^n\), se obtiene el valor buscado.
La entrada aritmética de la función generadora es la contribución de grado
$$c(1)=1,\qquad c(2)=1,\qquad c(m)=\frac{\varphi(m)}{2}\quad (m\ge 3),$$
donde \(\varphi\) es la función phi de Euler. Estos son exactamente los valores que se precalculan antes del DP de coeficientes.
Todo entero positivo tiene una forma única
$$m=2^u b,\qquad b\ \text{impar}.$$
Para una base impar fija \(b\), los grados relevantes forman la cadena
$$c(b),\ c(2b),\ c(4b),\ c(8b),\dots.$$
Si \(b\ge 3\) es impar y definimos
$$a_b=\frac{\varphi(b)}{2},$$
la multiplicatividad de \(\varphi\) implica
$$c(b)=a_b,\qquad c(2b)=a_b,\qquad c(2^u b)=2^{u-1}a_b\quad (u\ge 2).$$
Así, una cadena impar ordinaria empieza como
$$a_b,\ a_b,\ 2a_b,\ 4a_b,\dots.$$
Para \(b\ge 3\), definimos los pesos acumulados
$$W_{b,j}=\sum_{u=0}^{j} c(2^u b).$$
Gracias al patrón anterior, estas sumas se simplifican a
$$W_{b,0}=a_b,\qquad W_{b,1}=2a_b,\qquad W_{b,2}=4a_b,\qquad W_{b,j}=2^j a_b.$$
Por tanto, la cadena completa aporta el factor
$$F_b(x)=\prod_{j\ge 0}\frac{1}{1-x^{W_{b,j}}} =\prod_{j\ge 0}\frac{1}{1-x^{2^j a_b}}.$$
Cada factor \((1-x^w)^{-1}\) significa que un peso \(w\) puede usarse cualquier número de veces. Por eso el código aplica, para cada peso, una actualización hacia delante del tipo mochila sin límite.
La cadena que empieza en \(1\) no sigue la misma regla irrestricta. Después de separar los dos primeros términos de grado pequeño, queda la cola \(4,8,16,\dots\), cuyas contribuciones son
$$c(4)=1,\qquad c(8)=2,\qquad c(16)=4,\qquad \dots.$$
Sus pesos acumulados de cola son entonces
$$T_j=1+\sum_{u=2}^{j+2} c(2^u)=2^{j+1}\qquad (j\ge 0).$$
La implementación construye dos productos, uno simétrico y otro alternante:
$$P_+(x)=\prod_{j\ge 1}\frac{1}{1-x^{2^j}},\qquad P_-(x)=\prod_{j\ge 1}\frac{1}{1+x^{2^j}}.$$
Luego los combina en el polinomio central
$$C(x)=\frac{(1+x)P_+(x)+(1-x)P_-(x)}{2}.$$
La contribución completa de esta cadena excepcional es
$$F_1(x)=\frac{C(x)}{(1-x)(1-x^2)}.$$
Los dos denominadores corresponden exactamente a los dos recorridos acumulativos que se aplican después de combinar \(P_+\) y \(P_-\).
Todas las bases impares son independientes, así que la función generadora total es
$$F(x)=F_1(x)\prod_{\substack{b\ge 3\\ b\ \text{impar}}}\ \prod_{j\ge 0}\frac{1}{1-x^{2^j a_b}}.$$
La respuesta se obtiene como
$$S(n)=[x^n]F(x)\pmod{998244353}.$$
Solo importan los pesos menores o iguales que \(n\), porque un peso mayor ya no puede modificar el coeficiente de \(x^n\).
Este es el primer punto de control no trivial, y las implementaciones dan \(S(2)=6\).
En la cadena excepcional, hasta grado \(2\) solo puede influir el peso \(2\). Por tanto
$$P_+(x)=1+x^2+O(x^3),\qquad P_-(x)=1-x^2+O(x^3),$$
de modo que
$$C(x)=1+O(x^3),\qquad F_1(x)=\frac{1}{(1-x)(1-x^2)}+O(x^3)=1+x+2x^2+O(x^3).$$
Entre las cadenas ordinarias, \(b=3\) tiene \(a_3=1\), así que
$$F_3(x)=\frac{1}{(1-x)(1-x^2)}+O(x^3)=1+x+2x^2+O(x^3).$$
Luego \(b=5\) tiene \(a_5=2\), y por eso
$$F_5(x)=\frac{1}{1-x^2}+O(x^3)=1+x^2+O(x^3).$$
Toda base impar mayor empieza en grado al menos \(3\), así que no puede cambiar el coeficiente de \(x^2\). En consecuencia,
$$F(x)=(1+x+2x^2)(1+x+2x^2)(1+x^2)+O(x^3) =1+2x+6x^2+O(x^3),$$
y por tanto
$$S(2)=6.$$
Las implementaciones en C++, Python y Java siguen exactamente la misma secuencia. Primero eligen un límite de criba proporcional a \(n\) y calculan \(\varphi(m)\) para todos los valores necesarios. A partir de esa tabla forman la sucesión \(c(m)\).
Después construyen el factor especial de la base impar \(1\). Generan los pesos utilizables \(2,4,8,\dots\), calculan una tabla de coeficientes para \(P_+(x)\) y otra para \(P_-(x)\), combinan ambas mediante la fórmula de \(C(x)\) y finalmente aplican dos pasadas acumulativas que representan la división por \((1-x)(1-x^2)\).
Luego recorren todas las bases impares \(b\ge 3\). Para cada una generan los pesos \(a_b,2a_b,4a_b,\dots\) hasta que el siguiente excede \(n\). Cada peso provoca una actualización hacia delante de la tabla de coeficientes, que equivale exactamente a multiplicar por \((1-x^w)^{-1}\). Cuando todas las cadenas se han procesado, se devuelve el coeficiente de grado \(n\) módulo \(998244353\).
Sea \(M=\Theta(n)\) el límite de criba elegido por la implementación. Calcular todos los totientes hasta \(M\) cuesta \(O(M\log\log M)\) tiempo y \(O(M)\) memoria. La cadena excepcional aporta solo \(O(\log n)\) pesos utilizables. Para las bases impares ordinarias, sea \(W\) el número total de pesos acumulados \(2^j a_b\) que no superan \(n\). Cada uno de esos pesos activa una pasada hacia delante sobre una tabla de coeficientes de longitud \(n+1\), así que la fase DP cuesta \(O(nW)\) tiempo y \(O(n)\) memoria. Es un algoritmo pseudo-polinómico con memoria lineal y un único estado unidimensional.
Project Euler 812 要求计算一个与动力多项式构型有关的计数函数 \(S(n)\)，并把最终结果对 \(998244353\) 取模。真正的难点不在于模运算，而在于不能直接枚举所有合法对象。实现采用的思路是把这些对象编码到一个乘积型生成函数里，然后把 \(S(n)\) 还原成其中的一个系数。
具体做法是按照整数的奇数部分来重组问题。任意正整数都能唯一写成 \(2^u b\) 的形式，其中 \(b\) 为奇数，因此整个计数可以拆成互相独立的二进链 \(b,2b,4b,\dots\)。把所有链的贡献相乘，再提取 \(x^n\) 的系数，就得到答案。
生成函数的算术输入是下面这个“度贡献”函数：
$$c(1)=1,\qquad c(2)=1,\qquad c(m)=\frac{\varphi(m)}{2}\quad (m\ge 3),$$
其中 \(\varphi\) 是欧拉函数。实现首先预处理的就是这一列数，然后再进行系数 DP。
每个正整数都能唯一表示为
$$m=2^u b,\qquad b\ \text{为奇数}.$$
对固定的奇数底 \(b\)，相关的度序列就是
$$c(b),\ c(2b),\ c(4b),\ c(8b),\dots.$$
如果 \(b\ge 3\) 且为奇数，定义
$$a_b=\frac{\varphi(b)}{2},$$
那么由 \(\varphi\) 的乘法性可得
$$c(b)=a_b,\qquad c(2b)=a_b,\qquad c(2^u b)=2^{u-1}a_b\quad (u\ge 2).$$
也就是说，一条普通奇数链开头总是
$$a_b,\ a_b,\ 2a_b,\ 4a_b,\dots.$$
对 \(b\ge 3\)，定义累计权重
$$W_{b,j}=\sum_{u=0}^{j} c(2^u b).$$
由于上面的序列具有几何增长结构，这些前缀和会简化成
$$W_{b,0}=a_b,\qquad W_{b,1}=2a_b,\qquad W_{b,2}=4a_b,\qquad W_{b,j}=2^j a_b.$$
因此，这整条链对应的生成函数因子就是
$$F_b(x)=\prod_{j\ge 0}\frac{1}{1-x^{W_{b,j}}} =\prod_{j\ge 0}\frac{1}{1-x^{2^j a_b}}.$$
这里每个 \((1-x^w)^{-1}\) 都表示权重 \(w\) 可以使用任意次，所以代码里对每个权重做一次从小到大的更新，本质上就是无界背包乘上这个因子。
从 \(1\) 开始的那条链不能按同样的“完全自由”规则处理。把最开始两个低度项分离后，剩余尾部来自 \(4,8,16,\dots\)，其度贡献为
$$c(4)=1,\qquad c(8)=2,\qquad c(16)=4,\qquad \dots.$$
于是尾部的累计权重变成
$$T_j=1+\sum_{u=2}^{j+2} c(2^u)=2^{j+1}\qquad (j\ge 0).$$
实现为这条尾部构造了两个乘积，一个是对称部分，一个是交错部分：
$$P_+(x)=\prod_{j\ge 1}\frac{1}{1-x^{2^j}},\qquad P_-(x)=\prod_{j\ge 1}\frac{1}{1+x^{2^j}}.$$
然后把它们组合成核心多项式
$$C(x)=\frac{(1+x)P_+(x)+(1-x)P_-(x)}{2}.$$
这条特殊链的完整贡献为
$$F_1(x)=\frac{C(x)}{(1-x)(1-x^2)}.$$
最后这两个分母，正好对应实现里在组合 \(P_+\) 与 \(P_-\) 之后执行的两次累计扫描。
所有奇数底彼此独立，因此总生成函数是
$$F(x)=F_1(x)\prod_{\substack{b\ge 3\\ b\ \text{为奇数}}}\ \prod_{j\ge 0}\frac{1}{1-x^{2^j a_b}}.$$
所求答案就是
$$S(n)=[x^n]F(x)\pmod{998244353}.$$
只有不超过 \(n\) 的权重才有意义，因为更大的权重不可能影响 \(x^n\) 的系数。
这是最小的非平凡检验点，而实现返回的值是 \(S(2)=6\)。
对特殊链来说，在次数不超过 \(2\) 的范围内，只有权重 \(2\) 会起作用。因此
$$P_+(x)=1+x^2+O(x^3),\qquad P_-(x)=1-x^2+O(x^3),$$
从而
$$C(x)=1+O(x^3),\qquad F_1(x)=\frac{1}{(1-x)(1-x^2)}+O(x^3)=1+x+2x^2+O(x^3).$$
在普通奇数链中，\(b=3\) 时 \(a_3=1\)，所以
$$F_3(x)=\frac{1}{(1-x)(1-x^2)}+O(x^3)=1+x+2x^2+O(x^3).$$
接着 \(b=5\) 时 \(a_5=2\)，于是
$$F_5(x)=\frac{1}{1-x^2}+O(x^3)=1+x^2+O(x^3).$$
更大的奇数底其最小贡献次数都至少是 \(3\)，因此不会改变 \(x^2\) 的系数。于是
$$F(x)=(1+x+2x^2)(1+x+2x^2)(1+x^2)+O(x^3) =1+2x+6x^2+O(x^3),$$
所以确实有
$$S(2)=6.$$
C++、Python 和 Java 三个实现遵循完全相同的流程。第一步是取一个与 \(n\) 成正比的筛法上界，并计算所有需要的 \(\varphi(m)\)。然后根据这些值建立序列 \(c(m)\)。
第二步处理奇数底为 \(1\) 的特殊因子。实现生成可用权重 \(2,4,8,\dots\)，分别建立 \(P_+(x)\) 与 \(P_-(x)\) 的系数表，用 \(C(x)\) 的公式把它们组合起来，最后再做两次累计扫描，等价于除以 \((1-x)(1-x^2)\)。
第三步遍历所有 \(b\ge 3\) 的奇数底。对每个底数，逐个生成 \(a_b,2a_b,4a_b,\dots\) 这些链权重，直到下一个权重大于 \(n\) 为止。每一个权重都会触发一次从小到大的系数更新，而这恰好就是把当前生成函数乘上 \((1-x^w)^{-1}\)。所有链处理完以后，次数 \(n\) 的系数就是最终答案，再对 \(998244353\) 取模返回。
设实现选择的筛法上界为 \(M=\Theta(n)\)。计算 \(1\) 到 \(M\) 的全部欧拉函数值需要 \(O(M\log\log M)\) 时间和 \(O(M)\) 空间。特殊链只会产生 \(O(\log n)\) 个有效权重。对于普通奇数链，记所有不超过 \(n\) 的累计权重 \(2^j a_b\) 的总数为 \(W\)。每一个这样的权重都需要对长度为 \(n+1\) 的系数表做一次前向扫描，因此 DP 阶段的时间复杂度是 \(O(nW)\)，空间复杂度是 \(O(n)\)。所以这是一个伪多项式算法，但内存始终保持线性，而且状态数组只有一维。
Project Euler 812 требует вычислить функцию подсчета \(S(n)\), связанную с некоторым семейством конфигураций динамических многочленов, и взять результат по модулю \(998244353\). Главная идея состоит в том, что допустимые объекты не нужно перечислять напрямую. Их можно закодировать в произведение производящих функций, после чего \(S(n)\) становится одним коэффициентом этого произведения.
Реализация перегруппировывает все положительные числа по их нечетной части. Любой индекс единственным образом представим в виде \(2^u b\), где \(b\) нечетно, поэтому задача распадается на независимые двоичные цепочки \(b,2b,4b,\dots\). Если посчитать вклад каждой такой цепочки и извлечь коэффициент при \(x^n\), получится искомое значение.
Арифметической основой производящей функции служит вклад степени
$$c(1)=1,\qquad c(2)=1,\qquad c(m)=\frac{\varphi(m)}{2}\quad (m\ge 3),$$
где \(\varphi\) обозначает функцию Эйлера. Именно эти значения заранее вычисляются перед запуском коэффициентного DP.
Каждое положительное целое единственным образом записывается как
$$m=2^u b,\qquad b\ \text{нечетно}.$$
Для фиксированной нечетной базы \(b\) relevant последовательность степенных вкладов имеет вид
$$c(b),\ c(2b),\ c(4b),\ c(8b),\dots.$$
Если \(b\ge 3\) и \(b\) нечетно, положим
$$a_b=\frac{\varphi(b)}{2}.$$
Тогда из мультипликативности \(\varphi\) следует
$$c(b)=a_b,\qquad c(2b)=a_b,\qquad c(2^u b)=2^{u-1}a_b\quad (u\ge 2).$$
Значит, обычная нечетная цепочка начинается так:
$$a_b,\ a_b,\ 2a_b,\ 4a_b,\dots.$$
Для \(b\ge 3\) введем накопленные веса
$$W_{b,j}=\sum_{u=0}^{j} c(2^u b).$$
Из-за описанной выше геометрической структуры эти суммы упрощаются до
$$W_{b,0}=a_b,\qquad W_{b,1}=2a_b,\qquad W_{b,2}=4a_b,\qquad W_{b,j}=2^j a_b.$$
Следовательно, вся цепочка дает множитель
$$F_b(x)=\prod_{j\ge 0}\frac{1}{1-x^{W_{b,j}}} =\prod_{j\ge 0}\frac{1}{1-x^{2^j a_b}}.$$
Каждый множитель \((1-x^w)^{-1}\) означает, что вес \(w\) можно использовать сколько угодно раз. Именно поэтому код для каждого веса делает прямой проход, как в неограниченной задаче о рюкзаке.
Цепочка, начинающаяся с \(1\), не подчиняется той же неограниченной схеме. После отделения двух первых малых вкладов остается хвост \(4,8,16,\dots\) со значениями
$$c(4)=1,\qquad c(8)=2,\qquad c(16)=4,\qquad \dots.$$
Поэтому накопленные хвостовые веса равны
$$T_j=1+\sum_{u=2}^{j+2} c(2^u)=2^{j+1}\qquad (j\ge 0).$$
Реализация строит здесь два произведения, симметричное и знакопеременное:
$$P_+(x)=\prod_{j\ge 1}\frac{1}{1-x^{2^j}},\qquad P_-(x)=\prod_{j\ge 1}\frac{1}{1+x^{2^j}}.$$
Затем они объединяются в центральный полином
$$C(x)=\frac{(1+x)P_+(x)+(1-x)P_-(x)}{2}.$$
Полный вклад этой особой цепочки имеет вид
$$F_1(x)=\frac{C(x)}{(1-x)(1-x^2)}.$$
Два знаменателя в точности соответствуют двум накопительным проходам по коэффициентам, выполняемым после объединения \(P_+\) и \(P_-\).
Все нечетные базы независимы, поэтому полная производящая функция равна
$$F(x)=F_1(x)\prod_{\substack{b\ge 3\\ b\ \text{нечетно}}}\ \prod_{j\ge 0}\frac{1}{1-x^{2^j a_b}}.$$
Искомое значение получается как
$$S(n)=[x^n]F(x)\pmod{998244353}.$$
Важны только веса не больше \(n\), потому что больший вес уже не может повлиять на коэффициент при \(x^n\).
Это минимальная нетривиальная контрольная точка, и реализации выдают \(S(2)=6\).
Для особой цепочки до степени \(2\) может повлиять только вес \(2\). Поэтому
$$P_+(x)=1+x^2+O(x^3),\qquad P_-(x)=1-x^2+O(x^3),$$
откуда
$$C(x)=1+O(x^3),\qquad F_1(x)=\frac{1}{(1-x)(1-x^2)}+O(x^3)=1+x+2x^2+O(x^3).$$
Среди обычных цепочек \(b=3\) дает \(a_3=1\), поэтому
$$F_3(x)=\frac{1}{(1-x)(1-x^2)}+O(x^3)=1+x+2x^2+O(x^3).$$
Далее для \(b=5\) имеем \(a_5=2\), а значит
$$F_5(x)=\frac{1}{1-x^2}+O(x^3)=1+x^2+O(x^3).$$
Любая большая нечетная база начинается как минимум со степени \(3\), поэтому коэффициент при \(x^2\) уже не изменится. Следовательно,
$$F(x)=(1+x+2x^2)(1+x+2x^2)(1+x^2)+O(x^3) =1+2x+6x^2+O(x^3),$$
и значит
$$S(2)=6.$$
Реализации на C++, Python и Java используют один и тот же конвейер. Сначала выбирается предел решета, пропорциональный \(n\), и вычисляются значения \(\varphi(m)\) для всех нужных \(m\). Затем по этой таблице строится последовательность \(c(m)\).
После этого формируется специальный множитель для нечетной базы \(1\). Генерируются используемые веса \(2,4,8,\dots\), строится одна таблица коэффициентов для \(P_+(x)\) и вторая для \(P_-(x)\), затем они объединяются по формуле для \(C(x)\), и после этого выполняются два накопительных прохода, соответствующие делению на \((1-x)(1-x^2)\).
Далее перебираются все нечетные базы \(b\ge 3\). Для каждой из них последовательно генерируются веса \(a_b,2a_b,4a_b,\dots\), пока следующий вес не превысит \(n\). Каждый такой вес вызывает прямой проход по таблице коэффициентов, что в точности эквивалентно умножению на \((1-x^w)^{-1}\). После обработки всех цепочек коэффициент степени \(n\) возвращается по модулю \(998244353\).
Пусть \(M=\Theta(n)\) — выбранная реализацией граница решета. Вычисление всех значений функции Эйлера до \(M\) требует \(O(M\log\log M)\) времени и \(O(M)\) памяти. Особая цепочка дает только \(O(\log n)\) пригодных весов. Для обычных нечетных баз обозначим через \(W\) общее число накопленных весов \(2^j a_b\), не превосходящих \(n\). Каждый такой вес вызывает один прямой проход по таблице коэффициентов длины \(n+1\), поэтому фаза DP работает за \(O(nW)\) времени и использует \(O(n)\) памяти. Это псевдополиномиальный алгоритм с линейной памятью и одномерным состоянием.
تطلب مسألة Project Euler 812 حساب دالة العد \(S(n)\) المرتبطة بعائلة من تراكيب كثيرات الحدود الديناميكية، ثم أخذ الناتج بترديد \(998244353\). الفكرة الحاسمة هنا هي أن الأجسام المقبولة لا يلزم توليدها واحدا واحدا. يمكن ترميزها داخل حاصل ضرب من الدوال المولدة، وعندها تصبح \(S(n)\) مجرد معامل واحد في هذا الحاصل.
تعيد الخوارزمية تنظيم جميع الأعداد الموجبة بحسب جزئها الفردي. فكل فهرس يكتب بشكل وحيد على الصورة \(2^u b\) حيث \(b\) فردي، ولذلك تنقسم المسألة إلى سلاسل ثنائية مستقلة من الشكل \(b,2b,4b,\dots\). وبعد حساب مساهمة كل سلسلة واستخراج معامل \(x^n\)، نحصل على الجواب المطلوب.
المدخل الحسابي الأساسي في الدالة المولدة هو مساهمة الدرجة التالية:
$$c(1)=1,\qquad c(2)=1,\qquad c(m)=\frac{\varphi(m)}{2}\quad (m\ge 3),$$
حيث \(\varphi\) هي دالة أويلر. وهذه هي القيم التي يهيئها التنفيذ مسبقا قبل بدء برمجة المعاملات الديناميكية.
كل عدد صحيح موجب يملك تمثيلا وحيدا من الصورة
$$m=2^u b,\qquad b\ \text{odd}.$$
وبالنسبة إلى أساس فردي ثابت \(b\)، تكون سلسلة الدرجات ذات الصلة هي
$$c(b),\ c(2b),\ c(4b),\ c(8b),\dots.$$
إذا كان \(b\ge 3\) فرديا وعرّفنا
$$a_b=\frac{\varphi(b)}{2},$$
فإن خاصية الضرب في \(\varphi\) تعطي
$$c(b)=a_b,\qquad c(2b)=a_b,\qquad c(2^u b)=2^{u-1}a_b\quad (u\ge 2).$$
إذن تبدأ كل سلسلة فردية عادية بالشكل
$$a_b,\ a_b,\ 2a_b,\ 4a_b,\dots.$$
لـ \(b\ge 3\) نعرّف الأوزان التراكمية
$$W_{b,j}=\sum_{u=0}^{j} c(2^u b).$$
وبسبب النمط السابق تختزل هذه المجاميع إلى
$$W_{b,0}=a_b,\qquad W_{b,1}=2a_b,\qquad W_{b,2}=4a_b,\qquad W_{b,j}=2^j a_b.$$
وعليه فإن مساهمة السلسلة كاملة تساوي
$$F_b(x)=\prod_{j\ge 0}\frac{1}{1-x^{W_{b,j}}} =\prod_{j\ge 0}\frac{1}{1-x^{2^j a_b}}.$$
كل عامل من الشكل \((1-x^w)^{-1}\) يعني أن الوزن \(w\) يمكن استعماله أي عدد من المرات، ولهذا يطبق التنفيذ تحديثا أماميا من نوع الحقيبة غير المحدودة لكل وزن.
السلسلة التي تبدأ من \(1\) لا تتبع القاعدة الحرة نفسها. فبعد فصل أول مساهمتين صغيرتين في الدرجة، يبقى الذيل \(4,8,16,\dots\) وتكون مساهماته
$$c(4)=1,\qquad c(8)=2,\qquad c(16)=4,\qquad \dots.$$
ومن ثم فإن الأوزان التراكمية في هذا الذيل هي
$$T_j=1+\sum_{u=2}^{j+2} c(2^u)=2^{j+1}\qquad (j\ge 0).$$
يبني التنفيذ هنا حاصلَي ضرب، أحدهما متناظر والآخر متناوب الإشارة:
$$P_+(x)=\prod_{j\ge 1}\frac{1}{1-x^{2^j}},\qquad P_-(x)=\prod_{j\ge 1}\frac{1}{1+x^{2^j}}.$$
ثم يدمجهما في كثير الحدود المركزي
$$C(x)=\frac{(1+x)P_+(x)+(1-x)P_-(x)}{2}.$$
وتكون مساهمة هذه السلسلة الاستثنائية كاملة هي
$$F_1(x)=\frac{C(x)}{(1-x)(1-x^2)}.$$
ويطابق المقامان هنا تماما المرورين التراكميين على المعاملات بعد دمج \(P_+\) و\(P_-\).
جميع الأسس الفردية مستقلة عن بعضها، ولذلك تكون الدالة المولدة الكلية
$$F(x)=F_1(x)\prod_{\substack{b\ge 3\\ b\ \text{odd}}}\ \prod_{j\ge 0}\frac{1}{1-x^{2^j a_b}}.$$
والجواب النهائي هو المعامل
$$S(n)=[x^n]F(x)\pmod{998244353}.$$
ولا نحتاج إلا إلى الأوزان التي لا تتجاوز \(n\)، لأن أي وزن أكبر من ذلك لا يمكنه التأثير في معامل \(x^n\).
هذا أصغر موضع تحقق غير تافه، وتعيد التطبيقات القيمة \(S(2)=6\).
في السلسلة الاستثنائية لا يؤثر حتى الدرجة \(2\) إلا الوزن \(2\) فقط. لذلك
$$P_+(x)=1+x^2+O(x^3),\qquad P_-(x)=1-x^2+O(x^3),$$
ومن ثم
$$C(x)=1+O(x^3),\qquad F_1(x)=\frac{1}{(1-x)(1-x^2)}+O(x^3)=1+x+2x^2+O(x^3).$$
أما بين السلاسل العادية فإن \(b=3\) يعطي \(a_3=1\)، ومن ثم
$$F_3(x)=\frac{1}{(1-x)(1-x^2)}+O(x^3)=1+x+2x^2+O(x^3).$$
وكذلك \(b=5\) يعطي \(a_5=2\)، وبالتالي
$$F_5(x)=\frac{1}{1-x^2}+O(x^3)=1+x^2+O(x^3).$$
أما أي أساس فردي أكبر فيبدأ على الأقل من الدرجة \(3\)، ولذلك لا يغير معامل \(x^2\). إذن
$$F(x)=(1+x+2x^2)(1+x+2x^2)(1+x^2)+O(x^3) =1+2x+6x^2+O(x^3),$$
وبالتالي
$$S(2)=6.$$
تتبع تطبيقات C++ وPython وJava المسار نفسه تماما. أولا تختار حدا أعلى للغربلة يتناسب مع \(n\)، ثم تحسب \(\varphi(m)\) لكل القيم المطلوبة. ومن هذه القيم تبني المتتالية \(c(m)\).
بعد ذلك تبني العامل الخاص بالأساس الفردي \(1\). فهي تولد الأوزان الممكنة \(2,4,8,\dots\)، وتنشئ جدول معاملات لـ \(P_+(x)\) وجدولا آخر لـ \(P_-(x)\)، ثم تدمجهما بواسطة صيغة \(C(x)\)، وبعدها تطبق مرورين تراكميين يمثلان القسمة على \((1-x)(1-x^2)\).
ثم تمر على جميع الأسس الفردية \(b\ge 3\). ولكل أساس تولد الأوزان \(a_b,2a_b,4a_b,\dots\) إلى أن يصبح الوزن التالي أكبر من \(n\). وكل وزن يطلق تحديثا أماميا لجدول المعاملات، وهو ما يعادل تماما ضرب الدالة الحالية في \((1-x^w)^{-1}\). وبعد الانتهاء من جميع السلاسل يعاد معامل الدرجة \(n\) بترديد \(998244353\).
لتكن \(M=\Theta(n)\) هي قيمة الحد الأعلى للغربلة المختارة في التنفيذ. إن حساب جميع قيم دالة أويلر حتى \(M\) يحتاج زمنا مقداره \(O(M\log\log M)\) وذاكرة مقدارها \(O(M)\). أما السلسلة الاستثنائية فلا تنتج إلا \(O(\log n)\) من الأوزان المفيدة. وبالنسبة إلى السلاسل الفردية العادية، لنرمز بـ \(W\) إلى العدد الكلي للأوزان التراكمية \(2^j a_b\) التي لا تتجاوز \(n\). كل وزن من هذه الأوزان يسبب مرورا أماميا واحدا على جدول معاملات طوله \(n+1\)، لذا فإن مرحلة البرمجة الديناميكية تكلف \(O(nW)\) زمنا و\(O(n)\) ذاكرة. إذن فالخوارزمية شبه متعددة الحدود، لكنها تبقي الذاكرة خطية وتستخدم حالة أحادية البعد فقط.