Define
$$P(x)=1+x+x^2+x^3+x^4.$$
For each nonnegative integer \(k\), let \(Q(k)\) be the number of odd coefficients in the expansion of \(P(x)^k\). The problem asks for
$$\sum_{t=1}^{18} Q(10^t).$$
A direct expansion is hopeless when \(k\) is as large as \(10^{18}\). The implementations therefore never build the polynomial itself. They only track coefficient parity, because the question is about which coefficients are odd.
Write the binary expansion of \(k\) as
$$k=\sum_{b\ge 0} k_b 2^b,\qquad k_b\in\{0,1\}.$$
The key idea is that, modulo \(2\), the problem becomes a finite carry automaton with only five possible carry values and therefore only \(2^5=32\) parity states.
If \(a_m(k)\) denotes the coefficient of \(x^m\) in \(P(x)^k\), then
$$Q(k)=\#\{m\ge 0: a_m(k)\equiv 1 \pmod{2}\}.$$
So the problem is not asking for exact coefficients. It only asks which coefficients survive after reduction in \(\mathbb{F}_2\).
Over \(\mathbb{F}_2\), squaring obeys
$$f(x)^2=f(x^2).$$
As a consequence, \(Q(2n)=Q(n)\). This observation is useful conceptually, even though the implementations evaluate the requested powers directly.
Using the binary digits of \(k\), we can rewrite
$$P(x)^k=\prod_{b\ge 0} P(x)^{k_b 2^b}\equiv \prod_{b:k_b=1} P(x^{2^b}) \pmod{2}.$$
For one active bit \(b\), the factor is
$$P(x^{2^b})=1+x^{2^b}+x^{2\cdot 2^b}+x^{3\cdot 2^b}+x^{4\cdot 2^b}.$$
Choosing one term from each active factor is equivalent to choosing a digit \(d_b\). If \(k_b=0\), then necessarily \(d_b=0\). If \(k_b=1\), then
$$d_b\in\{0,1,2,3,4\}.$$
Every such choice contributes an exponent
$$m=\sum_{b\ge 0} d_b 2^b.$$
Hence the coefficient of \(x^m\) modulo \(2\) is the parity of the number of digit assignments that produce that same integer \(m\).
The digits \(d_b\) are not binary digits, so the representation above is not unique. The right model is binary addition with carries. Process bits from least significant to most significant. If the carry entering bit \(b\) is \(c\), then the local sum is
$$s_b=c+d_b.$$
The output bit of \(m\) at this position is
$$m_b\equiv s_b \pmod{2},$$
and the carry sent to the next position is
$$c'=\left\lfloor\frac{s_b}{2}\right\rfloor.$$
Because both \(c\) and \(d_b\) lie between \(0\) and \(4\), the next carry also lies in \(\{0,1,2,3,4\}\). So only five carry values ever occur.
For a fixed prefix of the output bits of \(m\), we do not need the exact number of partial digit assignments leading to each carry. We only need whether that number is odd or even.
So the state is a subset of \(\{0,1,2,3,4\}\): carry \(c\) is present exactly when the number of partial assignments reaching \(c\) is odd. Equivalently, the state is a 5-bit mask, so there are only \(32\) possible states.
Now fix \(t\in\{0,1\}\), where \(t=k_b\), and fix the output bit \(r\in\{0,1\}\). The allowed digits are
$$D_t=\begin{cases} \{0\}, & t=0,\\ \{0,1,2,3,4\}, & t=1. \end{cases}$$
From each active carry \(c\), inspect every \(d\in D_t\) satisfying \(c+d\equiv r\pmod{2}\). Each such pair produces the next carry \(c'=\lfloor(c+d)/2\rfloor\). If the same next carry appears twice, the two contributions cancel modulo \(2\), so the transition is naturally expressed by toggling bits in the next mask.
After the transition rule is known, we count output bit strings rather than coefficient assignments. Initially, before any bits are processed, the only active carry is \(0\). At each bit position there are two choices for the next output bit, namely \(0\) or \(1\), and each choice sends the current mask to one deterministic next mask.
If the highest set bit of \(k\) is \(B\), then the degree of \(P(x)^k\) is \(4k\), so only \(O(\log k)\) bit positions matter. After the significant bits of \(k\) are consumed, three extra zero-digit positions are enough to flush any remaining carry, because
$$4\mapsto 2\mapsto 1\mapsto 0.$$
Once all relevant bits are processed, an exponent contributes to \(Q(k)\) exactly when the final parity attached to carry \(0\) is odd. Therefore \(Q(k)\) is the total number of final masks in which carry \(0\) is active, counted with multiplicity from the outer dynamic program.
Because \(3=11_2\), only bits \(0\) and \(1\) are active, so
$$P(x)^3\equiv P(x)\,P(x^2)\pmod{2}.$$
Here we choose digits \(d_0,d_1\in\{0,1,2,3,4\}\), and the exponent is
$$m=d_0+2d_1.$$
Some exponents appear an odd number of times and survive. Others appear an even number of times and disappear. For example, \(m=4\) occurs three times, namely from \((4,0)\), \((2,1)\), and \((0,2)\), so its coefficient is odd. But \(m=5\) occurs twice, from \((3,1)\) and \((1,2)\), so it cancels modulo \(2\).
Carrying this through for all pairs gives
$$P(x)^3\equiv 1+x+x^4+x^6+x^8+x^{11}+x^{12}\pmod{2},$$
hence
$$Q(3)=7.$$
This matches the small reference value used by the implementations. Two further checkpoints are \(Q(10)=17\) and \(Q(100)=35\).
The C++, Python, and Java implementations all use the same structure. First they precompute the transition for every triple consisting of the current bit of \(k\), the requested output bit, and the current 5-bit carry-parity mask. Since there are only \(2\times 2\times 32\) such triples, this preprocessing is tiny.
For one concrete input \(k\), the implementation keeps an array of length \(32\). Entry \(M\) stores how many output prefixes currently lead to mask \(M\). The initial array has value \(1\) only at the mask representing carry \(0\) and value \(0\) everywhere else.
The program then scans bit positions from low to high. At each position it branches on the next output bit being \(0\) or \(1\), uses the precomputed transition to obtain the next mask, and adds the current count to the corresponding destination state. In other words, there is an outer count over output prefixes and an inner parity transition over carries.
The number of processed positions is the bit length of \(k\) plus three extra steps, which is sufficient to remove all remaining carry. After that, the implementation sums all state counts whose mask has the carry-\(0\) bit active. That sum is exactly \(Q(k)\). Repeating the same procedure for \(10,10^2,\dots,10^{18}\) and adding the eighteen values yields the required answer.
The transition table has constant size. For one value of \(k\), if
$$L=\lfloor\log_2 k\rfloor+3,$$
then the dynamic program processes \(32\) masks at each of the \(L\) positions. Therefore the running time is \(O(32L)=O(\log k)\), and the working memory is \(O(32)=O(1)\).
The full Project Euler task requires only eighteen inputs, so the total cost stays extremely small. The important point is that the method depends on the bit length of \(k\), not on the huge degree \(4k\) of the expanded polynomial.
Definiere
$$P(x)=1+x+x^2+x^3+x^4.$$
Für jede nichtnegative ganze Zahl \(k\) sei \(Q(k)\) die Anzahl ungerader Koeffizienten in der Entwicklung von \(P(x)^k\). Gesucht ist
$$\sum_{t=1}^{18} Q(10^t).$$
Eine direkte Ausmultiplizierung ist bei \(k=10^{18}\) völlig unpraktikabel. Deshalb verfolgen die Implementierungen nur die Parität der Koeffizienten. Genau diese Information entscheidet, welche Koeffizienten ungerade sind.
Schreibe die Binärdarstellung von \(k\) als
$$k=\sum_{b\ge 0} k_b 2^b,\qquad k_b\in\{0,1\}.$$
Der Kern der Lösung ist, dass das Problem modulo \(2\) zu einem kleinen Carry-Automaten wird. Es gibt nur fünf mögliche Überträge und damit nur \(2^5=32\) Paritätszustände.
Bezeichne mit \(a_m(k)\) den Koeffizienten von \(x^m\) in \(P(x)^k\). Dann gilt
$$Q(k)=\#\{m\ge 0: a_m(k)\equiv 1 \pmod{2}\}.$$
Wir brauchen also keine exakten Koeffizienten, sondern nur die Frage, welche Koeffizienten in \(\mathbb{F}_2\) ungleich null bleiben.
Über \(\mathbb{F}_2\) gilt beim Quadrieren
$$f(x)^2=f(x^2).$$
Daraus folgt unmittelbar \(Q(2n)=Q(n)\). Diese Beobachtung ist mathematisch nützlich, auch wenn die Implementierungen die geforderten Potenzen direkt auswerten.
Mit den Binärziffern von \(k\) erhalten wir
$$P(x)^k=\prod_{b\ge 0} P(x)^{k_b 2^b}\equiv \prod_{b:k_b=1} P(x^{2^b}) \pmod{2}.$$
Für ein aktives Bit \(b\) ist der Faktor
$$P(x^{2^b})=1+x^{2^b}+x^{2\cdot 2^b}+x^{3\cdot 2^b}+x^{4\cdot 2^b}.$$
Das Auswählen eines Terms aus jedem aktiven Faktor entspricht der Wahl einer Ziffer \(d_b\). Ist \(k_b=0\), dann muss \(d_b=0\) sein. Ist \(k_b=1\), dann gilt
$$d_b\in\{0,1,2,3,4\}.$$
Jede solche Wahl erzeugt den Exponenten
$$m=\sum_{b\ge 0} d_b 2^b.$$
Der Koeffizient von \(x^m\) modulo \(2\) ist also genau die Parität der Anzahl aller Ziffernbelegungen, die zu demselben \(m\) führen.
Die Ziffern \(d_b\) sind keine Binärziffern, deshalb ist die Darstellung nicht eindeutig. Das richtige Modell ist eine Binäraddition mit Überträgen. Wir verarbeiten die Bits von unten nach oben. Sei \(c\) der Übertrag vor Bit \(b\). Dann ist die lokale Summe
$$s_b=c+d_b.$$
Das Ausgabebit von \(m\) an dieser Stelle ist
$$m_b\equiv s_b \pmod{2},$$
und der Übertrag zum nächsten Bit ist
$$c'=\left\lfloor\frac{s_b}{2}\right\rfloor.$$
Da sowohl \(c\) als auch \(d_b\) zwischen \(0\) und \(4\) liegen, liegt auch \(c'\) immer in \(\{0,1,2,3,4\}\). Mehr als fünf Übertragswerte werden also nie benötigt.
Für ein festes Präfix der Ausgabebits von \(m\) müssen wir nicht wissen, wie viele partielle Ziffernbelegungen jeden Übertrag erzeugen. Es genügt zu wissen, ob diese Anzahl gerade oder ungerade ist.
Der Zustand ist daher eine Teilmenge von \(\{0,1,2,3,4\}\): Der Übertrag \(c\) ist genau dann aktiv, wenn die Zahl der partiellen Belegungen mit diesem Übertrag ungerade ist. Äquivalent dazu ist der Zustand eine 5-Bit-Maske, also eine von \(32\) Möglichkeiten.
Fixiere nun \(t\in\{0,1\}\) mit \(t=k_b\) und ein Ausgabebit \(r\in\{0,1\}\). Die zulässigen Ziffern sind
$$D_t=\begin{cases} \{0\}, & t=0,\\ \{0,1,2,3,4\}, & t=1. \end{cases}$$
Von jedem aktiven Übertrag \(c\) betrachten wir alle \(d\in D_t\) mit \(c+d\equiv r\pmod{2}\). Jedes solche Paar erzeugt den nächsten Übertrag \(c'=\lfloor(c+d)/2\rfloor\). Tritt derselbe nächste Übertrag zweimal auf, heben sich die beiden Beiträge modulo \(2\) weg. Deshalb wird der Übergang natürlich als Umschalten von Bits in der nächsten Maske beschrieben.
Nachdem die Übergangsregel feststeht, zählen wir nicht mehr Ziffernbelegungen, sondern Ausgabebitfolgen. Zu Beginn, bevor irgendein Bit verarbeitet wurde, ist nur der Übertrag \(0\) aktiv. An jeder Bitposition gibt es zwei Möglichkeiten für das nächste Ausgabebit, nämlich \(0\) oder \(1\), und jede dieser Wahlen führt die aktuelle Maske deterministisch in eine neue Maske über.
Ist \(B\) die höchste gesetzte Stelle von \(k\), dann hat \(P(x)^k\) den Grad \(4k\), also sind nur \(O(\log k)\) Bitpositionen relevant. Nachdem die signifikanten Bits von \(k\) verbraucht sind, reichen drei zusätzliche Nullstellen aus, um jeden Restübertrag auszuspülen, denn
$$4\mapsto 2\mapsto 1\mapsto 0.$$
Nach Abschluss aller relevanten Bits trägt ein Exponent genau dann zu \(Q(k)\) bei, wenn die Endparität beim Übertrag \(0\) ungerade ist. Also ist \(Q(k)\) die Summe über alle Endmasken, in denen der Übertrag \(0\) aktiv ist, gewichtet mit den Anzahlen aus dem äußeren DP.
Da \(3=11_2\) ist, sind nur die Bits \(0\) und \(1\) aktiv, also
$$P(x)^3\equiv P(x)\,P(x^2)\pmod{2}.$$
Wir wählen hier Ziffern \(d_0,d_1\in\{0,1,2,3,4\}\), und der Exponent lautet
$$m=d_0+2d_1.$$
Manche Exponenten entstehen ungerade oft und bleiben stehen. Andere entstehen gerade oft und verschwinden. Zum Beispiel tritt \(m=4\) dreimal auf, nämlich durch \((4,0)\), \((2,1)\) und \((0,2)\), also ist sein Koeffizient ungerade. Dagegen tritt \(m=5\) zweimal auf, durch \((3,1)\) und \((1,2)\), und verschwindet daher modulo \(2\).
Für alle Paare zusammen ergibt sich
$$P(x)^3\equiv 1+x+x^4+x^6+x^8+x^{11}+x^{12}\pmod{2},$$
also
$$Q(3)=7.$$
Das stimmt mit dem kleinen Kontrollwert der Implementierungen überein. Zwei weitere Kontrollpunkte sind \(Q(10)=17\) und \(Q(100)=35\).
Die C++-, Python- und Java-Implementierungen verwenden alle dieselbe Struktur. Zuerst berechnen sie für jedes Tripel aus aktuellem Bit von \(k\), gewünschtem Ausgabebit und aktueller 5-Bit-Maske den Übergang vor. Da es nur \(2\times 2\times 32\) Fälle gibt, ist diese Vorberechnung sehr klein.
Für ein konkretes \(k\) hält die Implementierung dann ein Array der Länge \(32\). Der Eintrag zu einer Maske \(M\) speichert, wie viele Präfixe der Ausgabebits momentan zu \(M\) führen. Anfangs ist nur die Maske mit aktivem Übertrag \(0\) mit \(1\) belegt; alle anderen Werte sind \(0\).
Anschließend werden die Bitpositionen von unten nach oben durchlaufen. Für jede Position verzweigt das Programm auf die beiden Möglichkeiten \(0\) und \(1\) für das nächste Ausgabebit, benutzt den vorberechneten Übergang zur Zielmaske und addiert die aktuelle Anzahl zum Zielzustand. Es gibt also einen äußeren Zähler über Bitpräfixe und einen inneren Paritätsübergang über Überträge.
Die Zahl der bearbeiteten Positionen ist die Bitlänge von \(k\) plus drei zusätzliche Schritte, was ausreicht, um jeden Restübertrag zu entfernen. Danach summiert die Implementierung alle Zustandsanzahlen, deren Maske das Bit für Übertrag \(0\) gesetzt hat. Diese Summe ist genau \(Q(k)\). Dasselbe Verfahren wird für \(10,10^2,\dots,10^{18}\) wiederholt, und die achtzehn Werte werden addiert.
Die Übergangstabelle hat konstante Größe. Für einen einzelnen Wert \(k\) sei
$$L=\lfloor\log_2 k\rfloor+3.$$
Dann verarbeitet das DP an jeder der \(L\) Positionen genau \(32\) Masken. Die Laufzeit ist also \(O(32L)=O(\log k)\), und der Arbeitsspeicher beträgt \(O(32)=O(1)\).
Für die eigentliche Aufgabe sind nur achtzehn Eingaben nötig, daher bleibt der Gesamtaufwand sehr klein. Entscheidend ist, dass die Methode von der Bitlänge von \(k\) abhängt und nicht vom enormen Grad \(4k\) des ausmultiplizierten Polynoms.
Şunu tanımlayalım:
$$P(x)=1+x+x^2+x^3+x^4.$$
Her negatif olmayan \(k\) tamsayısı için \(Q(k)\), \(P(x)^k\) açılımındaki tek katsayıların sayısı olsun. İstenen değer
$$\sum_{t=1}^{18} Q(10^t).$$
\(k=10^{18}\) gibi büyüklüklerde polinomu doğrudan açmak mümkün değildir. Bu yüzden uygulamalar polinomu üretmez; yalnızca katsayıların tek mi çift mi olduğuna bakar. Sorunun istediği bilgi tam olarak budur.
\(k\)'nın ikili açılımını
$$k=\sum_{b\ge 0} k_b 2^b,\qquad k_b\in\{0,1\}$$
şeklinde yazalım. Temel fikir şudur: mod \(2\) altında problem, sadece beş olası elde değeri olan küçük bir taşıma otomatına dönüşür. Bu da toplam \(2^5=32\) parite durumu demektir.
\(a_m(k)\), \(P(x)^k\) içindeki \(x^m\) katsayısı olsun. O zaman
$$Q(k)=\#\{m\ge 0: a_m(k)\equiv 1 \pmod{2}\}.$$
Yani tam katsayı değerlerine ihtiyacımız yoktur. Sadece hangi katsayıların \(\mathbb{F}_2\) üzerinde sıfırdan farklı kaldığını bilmemiz gerekir.
\(\mathbb{F}_2\) üzerinde karesini alma işlemi
$$f(x)^2=f(x^2)$$
özelliğine sahiptir. Buradan hemen \(Q(2n)=Q(n)\) sonucu çıkar. Uygulamalar istenen kuvvetleri doğrudan hesaplasa da bu gözlem matematiksel resmi netleştirir.
\(k\)'nın bitlerini kullanarak
$$P(x)^k=\prod_{b\ge 0} P(x)^{k_b 2^b}\equiv \prod_{b:k_b=1} P(x^{2^b}) \pmod{2}$$
yazarız. Etkin bir \(b\) biti için karşılık gelen çarpan
$$P(x^{2^b})=1+x^{2^b}+x^{2\cdot 2^b}+x^{3\cdot 2^b}+x^{4\cdot 2^b}$$
olur. Her etkin çarpandan bir terim seçmek, bir \(d_b\) rakamı seçmekle aynıdır. Eğer \(k_b=0\) ise zorunlu olarak \(d_b=0\) olur. Eğer \(k_b=1\) ise
$$d_b\in\{0,1,2,3,4\}$$
olabilir. Bu seçimlerin ürettiği üs
$$m=\sum_{b\ge 0} d_b 2^b$$
şeklindedir. Dolayısıyla \(x^m\) katsayısının mod \(2\) altındaki değeri, aynı \(m\)'yi veren rakam seçimlerinin sayısının paritesidir.
\(d_b\) değerleri ikili rakam değildir; \(2,3,4\) da olabilir. Bu yüzden yukarıdaki temsil tekil değildir. Doğru bakış açısı ikili toplama ve elde taşımadır. Bitleri düşük basamaktan yükseğe doğru işleyelim. Bit \(b\)'ye giren elde \(c\) olsun. Yerel toplam
$$s_b=c+d_b$$
olur. O konumdaki çıktı biti
$$m_b\equiv s_b \pmod{2},$$
bir sonraki konuma aktarılan elde ise
$$c'=\left\lfloor\frac{s_b}{2}\right\rfloor$$
şeklindedir. Hem \(c\) hem de \(d_b\) \(0\) ile \(4\) arasında olduğundan \(c'\) de her zaman \(\{0,1,2,3,4\}\) kümesinde kalır. Yani yalnızca beş elde değeri gerekir.
\(m\)'nin çıktı bitlerinin sabit bir ön eki için, her elde değerine kaç farklı kısmi seçim ulaştığını tam olarak saklamamız gerekmez. Bu sayının tek mi çift mi olduğu yeterlidir.
Bu yüzden durum, \(\{0,1,2,3,4\}\) kümesinin bir alt kümesi olarak tutulur: elde \(c\), ona ulaşan kısmi seçim sayısı tekse aktiftir. Aynı bilgi 5 bitlik bir maske olarak da görülebilir ve toplam yalnızca \(32\) olası durum vardır.
Şimdi \(t\in\{0,1\}\) olmak üzere \(t=k_b\) olsun ve çıktı biti \(r\in\{0,1\}\) sabitlensin. İzinli rakamlar
$$D_t=\begin{cases} \{0\}, & t=0,\\ \{0,1,2,3,4\}, & t=1 \end{cases}$$
şeklindedir. Her aktif elde \(c\) için, \(c+d\equiv r\pmod{2}\) koşulunu sağlayan tüm \(d\in D_t\) değerleri incelenir. Her böyle çift, bir sonraki eldeyi \(c'=\lfloor(c+d)/2\rfloor\) üretir. Aynı sonraki elde iki kez oluşursa katkılar mod \(2\) altında birbirini götürür; bu nedenle geçiş doğal olarak yeni maskede bit çevirmekle ifade edilir.
Geçiş kuralı kurulduktan sonra artık rakam seçimlerini değil, çıktı bit dizilerini sayarız. Başlangıçta henüz hiçbir bit işlenmemişken yalnızca elde \(0\) aktiftir. Her bit konumunda sonraki çıktı biti için iki seçenek vardır: \(0\) veya \(1\). Her seçim, mevcut maskeyi deterministik olarak yeni bir maskeye gönderir.
\(k\)'nın en yüksek dolu biti \(B\) ise, \(P(x)^k\)'nın derecesi \(4k\) olur; dolayısıyla yalnızca \(O(\log k)\) kadar bit konumu önemlidir. \(k\)'nın anlamlı bitleri bittikten sonra kalan eldeyi boşaltmak için üç ek sıfır basamak yeterlidir, çünkü
$$4\mapsto 2\mapsto 1\mapsto 0.$$
Tüm ilgili bitler işlendikten sonra bir üs, ancak son durumda elde \(0\)'ın paritesi tekse \(Q(k)\)'ye katkı yapar. Bu yüzden \(Q(k)\), dış DP'nin saydığı son maskeler arasında elde \(0\) aktif olanların toplamıdır.
\(3=11_2\) olduğundan yalnızca \(0\) ve \(1\). bitler etkindir. Bu yüzden
$$P(x)^3\equiv P(x)\,P(x^2)\pmod{2}.$$
Burada \(d_0,d_1\in\{0,1,2,3,4\}\) seçeriz ve üs
$$m=d_0+2d_1$$
olur. Bazı üsler tek sayıda, bazıları çift sayıda oluşur. Örneğin \(m=4\), \((4,0)\), \((2,1)\) ve \((0,2)\) seçimlerinden geldiği için üç kez oluşur ve katsayısı tektir. Buna karşılık \(m=5\), \((3,1)\) ve \((1,2)\) ile iki kez oluşur; bu yüzden mod \(2\) altında yok olur.
Tüm çiftler incelendiğinde
$$P(x)^3\equiv 1+x+x^4+x^6+x^8+x^{11}+x^{12}\pmod{2}$$
elde edilir; dolayısıyla
$$Q(3)=7.$$
Bu değer, uygulamaların kullandığı küçük doğrulama noktasıyla aynıdır. Diğer iki kontrol değeri de \(Q(10)=17\) ve \(Q(100)=35\) olur.
C++, Python ve Java uygulamalarının yapısı aynıdır. İlk adımda, \(k\)'nın o andaki biti, istenen çıktı biti ve mevcut 5 bitlik elde-parite maskesi üçlüsünün her biri için geçiş önceden hesaplanır. Toplam yalnızca \(2\times 2\times 32\) olasılık bulunduğu için bu hazırlık çok küçüktür.
Belirli bir \(k\) için uygulama uzunluğu \(32\) olan bir dizi tutar. \(M\) maskesine karşılık gelen giriş, o ana kadar hangi çıktı bit ön eklerinin \(M\) durumuna ulaştığını sayar. Başlangıçta yalnızca elde \(0\)'ı temsil eden maskenin sayısı \(1\)'dir; diğerlerinin hepsi \(0\)'dır.
Program daha sonra bit konumlarını düşükten yükseğe tarar. Her konumda sonraki çıktı bitinin \(0\) ya da \(1\) olması ayrı ayrı denenir, önceden hazırlanmış geçiş uygulanır ve mevcut sayaç hedef maskeye eklenir. Yani dışta çıktı ön eklerini sayan bir DP, içte ise elde paritesini güncelleyen küçük bir otomat vardır.
İşlenen bit sayısı, \(k\)'nın bit uzunluğu artı üç ek adımdır; bu da kalan tüm eldeyi temizlemek için yeterlidir. Sonunda maske içinde elde \(0\) biti aktif olan tüm durumların sayaçları toplanır. Bu toplam tam olarak \(Q(k)\)'dir. Aynı işlem \(10,10^2,\dots,10^{18}\) için tekrarlanır ve on sekiz sonuç bir araya getirilir.
Geçiş tablosunun boyutu sabittir. Tek bir \(k\) için
$$L=\lfloor\log_2 k\rfloor+3$$
olsun. DP, \(L\) konumun her birinde \(32\) maske işler. Bu nedenle çalışma süresi \(O(32L)=O(\log k)\), çalışma belleği ise \(O(32)=O(1)\)'dir.
Asıl problemde sadece on sekiz farklı girdi vardır. Bu yüzden toplam maliyet çok küçüktür. Esas kazanç, yöntemin açılmış polinomun devasa derecesi \(4k\)'ya değil, yalnızca \(k\)'nın bit uzunluğuna bağlı olmasıdır.
Definimos
$$P(x)=1+x+x^2+x^3+x^4.$$
Para cada entero no negativo \(k\), sea \(Q(k)\) el número de coeficientes impares en la expansión de \(P(x)^k\). Se pide calcular
$$\sum_{t=1}^{18} Q(10^t).$$
Expandir el polinomio de forma directa es inviable cuando \(k\) llega hasta \(10^{18}\). Por eso las implementaciones no construyen la expansión completa. Solo siguen la paridad de los coeficientes, porque la pregunta depende exactamente de esa información.
Escribimos la expansión binaria de \(k\) como
$$k=\sum_{b\ge 0} k_b 2^b,\qquad k_b\in\{0,1\}.$$
La idea central es que, módulo \(2\), el problema se convierte en un pequeño autómata de acarreos. Solo existen cinco valores posibles de acarreo y, por tanto, únicamente \(2^5=32\) estados de paridad.
Si \(a_m(k)\) es el coeficiente de \(x^m\) en \(P(x)^k\), entonces
$$Q(k)=\#\{m\ge 0: a_m(k)\equiv 1 \pmod{2}\}.$$
No necesitamos los coeficientes exactos. Solo necesitamos saber cuáles siguen siendo no nulos dentro de \(\mathbb{F}_2\).
En \(\mathbb{F}_2\), al elevar al cuadrado se cumple
$$f(x)^2=f(x^2).$$
Como consecuencia, \(Q(2n)=Q(n)\). Esa observación aclara la estructura del problema, aunque las implementaciones evalúan directamente las potencias solicitadas.
Usando los bits de \(k\), obtenemos
$$P(x)^k=\prod_{b\ge 0} P(x)^{k_b 2^b}\equiv \prod_{b:k_b=1} P(x^{2^b}) \pmod{2}.$$
Para un bit activo \(b\), el factor correspondiente es
$$P(x^{2^b})=1+x^{2^b}+x^{2\cdot 2^b}+x^{3\cdot 2^b}+x^{4\cdot 2^b}.$$
Elegir un término de cada factor activo equivale a elegir un dígito \(d_b\). Si \(k_b=0\), necesariamente \(d_b=0\). Si \(k_b=1\), entonces
$$d_b\in\{0,1,2,3,4\}.$$
Cada elección produce el exponente
$$m=\sum_{b\ge 0} d_b 2^b.$$
Por lo tanto, el coeficiente de \(x^m\) módulo \(2\) es la paridad del número de elecciones de dígitos que generan ese mismo entero \(m\).
Los valores \(d_b\) no son bits binarios normales, porque pueden valer \(2\), \(3\) o \(4\). La representación anterior no es única. La forma correcta de verla es como una suma binaria con acarreos. Procesamos los bits de menor a mayor. Si el acarreo que entra en la posición \(b\) es \(c\), entonces la suma local es
$$s_b=c+d_b.$$
El bit de salida de \(m\) en esa posición es
$$m_b\equiv s_b \pmod{2},$$
y el acarreo para la siguiente posición es
$$c'=\left\lfloor\frac{s_b}{2}\right\rfloor.$$
Como tanto \(c\) como \(d_b\) están entre \(0\) y \(4\), el nuevo acarreo también siempre pertenece a \(\{0,1,2,3,4\}\). Así, solo hay cinco valores posibles de acarreo.
Para un prefijo fijo de bits de salida de \(m\), no hace falta almacenar cuántas elecciones parciales llegan exactamente a cada acarreo. Basta con saber si ese número es impar o par.
El estado se puede representar como un subconjunto de \(\{0,1,2,3,4\}\): el acarreo \(c\) está activo exactamente cuando el número de elecciones parciales que llegan a \(c\) es impar. De forma equivalente, se trata de una máscara de 5 bits, así que existen solo \(32\) estados posibles.
Fijemos \(t\in\{0,1\}\) con \(t=k_b\) y el bit de salida \(r\in\{0,1\}\). Los dígitos permitidos son
$$D_t=\begin{cases} \{0\}, & t=0,\\ \{0,1,2,3,4\}, & t=1. \end{cases}$$
Desde cada acarreo activo \(c\), se inspeccionan todos los \(d\in D_t\) que satisfacen \(c+d\equiv r\pmod{2}\). Cada pareja de ese tipo genera el siguiente acarreo \(c'=\lfloor(c+d)/2\rfloor\). Si el mismo acarreo siguiente aparece dos veces, las dos contribuciones se cancelan módulo \(2\). Por eso la transición se describe naturalmente como un cambio de bits dentro de la nueva máscara.
Una vez conocida la transición, dejamos de contar elecciones de dígitos y pasamos a contar cadenas de bits de salida. Al principio, antes de procesar ninguna posición, solo el acarreo \(0\) está activo. En cada posición hay dos posibilidades para el siguiente bit de salida, \(0\) o \(1\), y cada una lleva la máscara actual a una nueva máscara determinada.
Si \(B\) es el bit más alto encendido de \(k\), entonces el grado de \(P(x)^k\) es \(4k\), así que solo importan \(O(\log k)\) posiciones. Después de consumir los bits significativos de \(k\), bastan tres posiciones extra con dígito cero para vaciar cualquier acarreo residual, ya que
$$4\mapsto 2\mapsto 1\mapsto 0.$$
Al final, un exponente cuenta para \(Q(k)\) exactamente cuando la paridad final asociada al acarreo \(0\) es impar. Por tanto, \(Q(k)\) es la suma de todos los estados finales cuya máscara tiene activo el componente de acarreo \(0\), contando las multiplicidades del programa dinámico exterior.
Como \(3=11_2\), solo están activos los bits \(0\) y \(1\), de modo que
$$P(x)^3\equiv P(x)\,P(x^2)\pmod{2}.$$
Aquí elegimos \(d_0,d_1\in\{0,1,2,3,4\}\), y el exponente vale
$$m=d_0+2d_1.$$
Algunos exponentes aparecen un número impar de veces y sobreviven; otros aparecen un número par de veces y se cancelan. Por ejemplo, \(m=4\) aparece tres veces, a partir de \((4,0)\), \((2,1)\) y \((0,2)\), así que su coeficiente es impar. En cambio, \(m=5\) aparece dos veces, a partir de \((3,1)\) y \((1,2)\), por lo que desaparece módulo \(2\).
Al completar todas las parejas se obtiene
$$P(x)^3\equiv 1+x+x^4+x^6+x^8+x^{11}+x^{12}\pmod{2},$$
y por lo tanto
$$Q(3)=7.$$
Ese valor coincide con la referencia pequeña usada por las implementaciones. Otros dos puntos de control son \(Q(10)=17\) y \(Q(100)=35\).
Las implementaciones en C++, Python y Java siguen exactamente el mismo esquema. Primero precalculan la transición para cada triple formado por el bit actual de \(k\), el bit de salida deseado y la máscara actual de paridades de acarreo de 5 bits. Como solo hay \(2\times 2\times 32\) casos, esta fase es diminuta.
Para un valor concreto de \(k\), la implementación mantiene un arreglo de longitud \(32\). La entrada asociada a una máscara \(M\) indica cuántos prefijos de bits de salida conducen actualmente a \(M\). El estado inicial tiene valor \(1\) solo en la máscara que representa el acarreo \(0\), y valor \(0\) en todas las demás.
Luego el programa recorre las posiciones de bit de menor a mayor. En cada posición prueba las dos posibilidades para el siguiente bit de salida, \(0\) y \(1\), aplica la transición precalculada y suma el conteo actual al estado destino correspondiente. En otras palabras, hay una DP exterior que cuenta prefijos de salida y una transición interior que actualiza paridades de acarreos.
El número de posiciones procesadas es la longitud binaria de \(k\) más tres pasos adicionales, suficientes para eliminar cualquier acarreo restante. Después, la implementación suma todos los conteos de estados cuya máscara tiene activo el bit correspondiente al acarreo \(0\). Esa suma es exactamente \(Q(k)\). El mismo procedimiento se repite para \(10,10^2,\dots,10^{18}\), y finalmente se suman los dieciocho valores.
La tabla de transiciones tiene tamaño constante. Para un único valor \(k\), si
$$L=\lfloor\log_2 k\rfloor+3,$$
entonces la programación dinámica procesa \(32\) máscaras en cada una de las \(L\) posiciones. Por ello, el tiempo es \(O(32L)=O(\log k)\) y la memoria de trabajo es \(O(32)=O(1)\).
La tarea completa solo requiere dieciocho valores de entrada, así que el coste total sigue siendo muy pequeño. Lo importante es que el método depende de la longitud en bits de \(k\), no del enorme grado \(4k\) del polinomio expandido.
定义
$$P(x)=1+x+x^2+x^3+x^4.$$
对每个非负整数 \(k\)，记 \(Q(k)\) 为 \(P(x)^k\) 展开式中奇数系数的个数。题目要求计算
$$\sum_{t=1}^{18} Q(10^t).$$
当 \(k\) 大到 \(10^{18}\) 时，直接把多项式展开显然不可行。实现中的做法不是去构造完整展开式，而是只追踪每个系数的奇偶性，因为题目真正关心的只是哪些系数是奇数。
把 \(k\) 写成二进制形式
$$k=\sum_{b\ge 0} k_b 2^b,\qquad k_b\in\{0,1\}.$$
核心思想是：在模 \(2\) 的世界里，这个问题会变成一个很小的进位自动机问题。进位只可能取五个值，因此总状态数只有 \(2^5=32\) 个。
设 \(a_m(k)\) 是 \(P(x)^k\) 中 \(x^m\) 的系数，那么
$$Q(k)=\#\{m\ge 0: a_m(k)\equiv 1 \pmod{2}\}.$$
也就是说，我们不需要知道系数的精确大小，只需要知道它在 \(\mathbb{F}_2\) 中是 \(0\) 还是 \(1\)。留下来的那些非零项，正对应题目要求统计的奇数系数。
在 \(\mathbb{F}_2\) 上，平方满足
$$f(x)^2=f(x^2).$$
因此可以立刻得到 \(Q(2n)=Q(n)\)。这个恒等式有助于理解问题的结构，虽然实现本身仍然按题目要求直接计算 \(10,10^2,\dots,10^{18}\) 这些值。
利用 \(k\) 的二进制位，可以把原式改写为
$$P(x)^k=\prod_{b\ge 0} P(x)^{k_b 2^b}\equiv \prod_{b:k_b=1} P(x^{2^b}) \pmod{2}.$$
对某个激活的二进制位 \(b\)，对应的因子是
$$P(x^{2^b})=1+x^{2^b}+x^{2\cdot 2^b}+x^{3\cdot 2^b}+x^{4\cdot 2^b}.$$
这说明，从每个激活因子里选一项，等价于选择一个数字 \(d_b\)。如果 \(k_b=0\)，那么这一层不存在选择自由度，只能取 \(d_b=0\)。如果 \(k_b=1\)，则有
$$d_b\in\{0,1,2,3,4\}.$$
所有这些选择共同产生的指数为
$$m=\sum_{b\ge 0} d_b 2^b.$$
于是，\(x^m\) 的系数在模 \(2\) 下是否为 \(1\)，就等于满足这条等式的数字选择方案数的奇偶性。
这里的 \(d_b\) 不是普通二进制位，因为它们可以等于 \(2\)、\(3\)、\(4\)。所以
$$m=\sum_{b\ge 0} d_b 2^b$$
并不是通常意义下的唯一二进制展开。正确的理解方式是按位处理并显式跟踪进位。假设在第 \(b\) 位进入时的进位是 \(c\)，那么该位的局部和为
$$s_b=c+d_b.$$
输出指数 \(m\) 在这一位上的比特满足
$$m_b\equiv s_b \pmod{2},$$
传到下一位的进位则是
$$c'=\left\lfloor\frac{s_b}{2}\right\rfloor.$$
由于 \(c\) 和 \(d_b\) 都只会落在 \(0\) 到 \(4\) 之间，所以新的进位 \(c'\) 也始终在 \(\{0,1,2,3,4\}\) 内。换句话说，整个问题永远只需要处理五种进位值。
对于某个固定的输出前缀，并不需要记录“有多少种”部分选择会到达每个进位值。因为最终只关心模 \(2\) 的结果，所以只要记录这个数量是奇数还是偶数即可。
因此，一个状态可以看成 \(\{0,1,2,3,4\}\) 的一个子集：如果到达进位 \(c\) 的部分方案数是奇数，就认为 \(c\) 处于激活状态。等价地，这就是一个 5 位二进制掩码，因此总共有 \(32\) 个可能状态。
现在固定 \(t\in\{0,1\}\)，其中 \(t=k_b\)，再固定当前输出位 \(r\in\{0,1\}\)。允许选择的数字集合为
$$D_t=\begin{cases} \{0\}, & t=0,\\ \{0,1,2,3,4\}, & t=1. \end{cases}$$
对每个激活进位 \(c\)，枚举所有满足 \(c+d\equiv r\pmod{2}\) 的 \(d\in D_t\)。每一对 \((c,d)\) 会产生新的进位 \(c'=\lfloor(c+d)/2\rfloor\)。如果同一个新进位被命中两次，那么这两次贡献在模 \(2\) 下会互相抵消，所以状态转移本质上就是对新掩码中的相应位做“翻转”。
当转移规则确定以后，外层动态规划统计的就不再是数字选择方案，而是“输出指数的比特前缀”。最开始还没有处理任何位，因此唯一可能的进位是 \(0\)。到了每一位，输出比特只有两种可能：\(0\) 或 \(1\)。这两种选择都会把当前掩码通过上一步的确定性转移送到一个新的掩码。
如果 \(k\) 的最高位是 \(B\)，那么 \(P(x)^k\) 的次数是 \(4k\)，所以真正相关的位数只和 \(\log k\) 成正比。等所有有效位处理完以后，再补上三个“数字只能为 \(0\)”的空位，就足以把剩余进位全部清空，因为
$$4\mapsto 2\mapsto 1\mapsto 0.$$
最终，一个指数 \(m\) 会被计入 \(Q(k)\)，当且仅当结束时与进位 \(0\) 对应的奇偶分量为奇数。于是 \(Q(k)\) 就等于所有“包含进位 \(0\)”的终止掩码的外层计数总和。
因为 \(3=11_2\)，只有第 \(0\) 位和第 \(1\) 位是激活的，所以
$$P(x)^3\equiv P(x)\,P(x^2)\pmod{2}.$$
此时需要选择 \(d_0,d_1\in\{0,1,2,3,4\}\)，对应的指数为
$$m=d_0+2d_1.$$
有些指数会出现奇数次，因此保留下来；有些指数会出现偶数次，因此在模 \(2\) 下消失。例如 \(m=4\) 会由 \((4,0)\)、\((2,1)\)、\((0,2)\) 三种选择产生，所以它的系数是奇数。相反，\(m=5\) 只会由 \((3,1)\) 和 \((1,2)\) 两种选择产生，因此会被抵消掉。
把所有配对都算完后可得
$$P(x)^3\equiv 1+x+x^4+x^6+x^8+x^{11}+x^{12}\pmod{2},$$
因此
$$Q(3)=7.$$
这正好与实现中使用的小型校验值一致。其他两个参考值是 \(Q(10)=17\) 和 \(Q(100)=35\)。
C++、Python 和 Java 实现都遵循同一套结构。第一步先把所有可能的局部转移预计算出来。一个局部转移由三部分决定：\(k\) 的当前位是 \(0\) 还是 \(1\)，当前输出位希望是 \(0\) 还是 \(1\)，以及当前的 5 位进位奇偶掩码。总共只有 \(2\times 2\times 32\) 种情况，所以这部分非常小。
对于某个具体的 \(k\)，实现维护一个长度为 \(32\) 的数组。数组中第 \(M\) 项表示：当前有多少个输出前缀会到达掩码状态 \(M\)。初始时，只有“进位 \(0\) 激活”的那个状态计数为 \(1\)，其余状态全为 \(0\)。
随后程序从低位到高位扫描。每处理一位，就分别尝试输出位为 \(0\) 和 \(1\) 的两种情况，通过预计算好的转移找到下一状态，并把当前计数累加过去。换句话说，外层是在数有多少个输出指数前缀，内层的 5 位掩码负责维护“这些前缀对应的系数奇偶模式”。
总处理位数取为 \(k\) 的二进制长度再加上 3，这足以清空所有剩余进位。最后，把所有“掩码中进位 \(0\) 位置为激活”的状态计数加起来，得到的就是 \(Q(k)\)。对 \(10,10^2,\dots,10^{18}\) 重复这个过程，再把 18 个结果相加，就是题目要求的最终答案。
转移表的大小是常数。对于单个 \(k\)，若记
$$L=\lfloor\log_2 k\rfloor+3,$$
那么动态规划会在每一位处理 \(32\) 个掩码状态，因此时间复杂度是 \(O(32L)=O(\log k)\)，空间复杂度是 \(O(32)=O(1)\)。
整个题目只需要计算 18 个输入值，所以总成本依然非常小。真正关键的是，这个方法依赖的是 \(k\) 的位数，而不是展开后多项式的巨大次数 \(4k\)。
Определим
$$P(x)=1+x+x^2+x^3+x^4.$$
Для каждого неотрицательного целого \(k\) пусть \(Q(k)\) обозначает число нечётных коэффициентов в разложении \(P(x)^k\). Требуется вычислить
$$\sum_{t=1}^{18} Q(10^t).$$
При \(k\) порядка \(10^{18}\) прямое раскрытие скобок бессмысленно. Поэтому реализации вообще не строят полный многочлен. Они отслеживают только чётность коэффициентов, потому что именно она и определяет, какие коэффициенты нечётны.
Запишем двоичное разложение числа \(k\) в виде
$$k=\sum_{b\ge 0} k_b 2^b,\qquad k_b\in\{0,1\}.$$
Ключевая идея состоит в том, что по модулю \(2\) задача превращается в маленький автомат переносов. Возможных значений переноса всего пять, а значит, состояний паритета ровно \(2^5=32\).
Пусть \(a_m(k)\) обозначает коэффициент при \(x^m\) в \(P(x)^k\). Тогда
$$Q(k)=\#\{m\ge 0: a_m(k)\equiv 1 \pmod{2}\}.$$
То есть нам не нужны точные значения коэффициентов. Нужно лишь понять, какие из них остаются ненулевыми в поле \(\mathbb{F}_2\).
В \(\mathbb{F}_2\) при возведении в квадрат выполняется тождество
$$f(x)^2=f(x^2).$$
Отсюда сразу следует полезное соотношение \(Q(2n)=Q(n)\). Оно важно для понимания структуры задачи, хотя сами реализации всё равно считают требуемые степени напрямую.
Используя двоичные цифры числа \(k\), получаем
$$P(x)^k=\prod_{b\ge 0} P(x)^{k_b 2^b}\equiv \prod_{b:k_b=1} P(x^{2^b}) \pmod{2}.$$
Для активного бита \(b\) соответствующий множитель равен
$$P(x^{2^b})=1+x^{2^b}+x^{2\cdot 2^b}+x^{3\cdot 2^b}+x^{4\cdot 2^b}.$$
Выбор одного слагаемого из каждого активного множителя эквивалентен выбору цифры \(d_b\). Если \(k_b=0\), то обязательно \(d_b=0\). Если \(k_b=1\), то
$$d_b\in\{0,1,2,3,4\}.$$
Каждый набор таких выборов создаёт показатель
$$m=\sum_{b\ge 0} d_b 2^b.$$
Следовательно, коэффициент при \(x^m\) по модулю \(2\) равен паритету числа наборов цифр, дающих одно и то же значение \(m\).
Цифры \(d_b\) не являются обычными двоичными цифрами, потому что могут быть равны \(2\), \(3\) или \(4\). Поэтому представление выше не единственно. Правильный взгляд - это двоичное сложение с переносами. Обрабатываем позиции от младших битов к старшим. Если на вход в позицию \(b\) приходит перенос \(c\), то локальная сумма равна
$$s_b=c+d_b.$$
Выходной бит числа \(m\) на этой позиции определяется как
$$m_b\equiv s_b \pmod{2},$$
а перенос на следующую позицию равен
$$c'=\left\lfloor\frac{s_b}{2}\right\rfloor.$$
Поскольку и \(c\), и \(d_b\) лежат между \(0\) и \(4\), новый перенос тоже всегда принадлежит множеству \(\{0,1,2,3,4\}\). Значит, все возможные переносы укладываются всего в пять значений.
Для фиксированного префикса выходных битов числа \(m\) нам не нужно хранить точное число частичных наборов, ведущих к каждому переносу. Достаточно знать, нечётно это число или чётно.
Поэтому состояние можно задавать как подмножество \(\{0,1,2,3,4\}\): перенос \(c\) активен тогда и только тогда, когда число частичных наборов, ведущих к нему, нечётно. Эквивалентно это 5-битовая маска, а значит, возможны только \(32\) состояния.
Зафиксируем \(t\in\{0,1\}\), где \(t=k_b\), и выходной бит \(r\in\{0,1\}\). Тогда допустимые цифры задаются так:
$$D_t=\begin{cases} \{0\}, & t=0,\\ \{0,1,2,3,4\}, & t=1. \end{cases}$$
Для каждого активного переноса \(c\) рассматриваются все \(d\in D_t\), удовлетворяющие условию \(c+d\equiv r\pmod{2}\). Каждая такая пара порождает следующий перенос \(c'=\lfloor(c+d)/2\rfloor\). Если один и тот же следующий перенос возникает дважды, то вклады взаимно уничтожаются по модулю \(2\). Поэтому переход естественно описывать как переключение битов в новой маске.
После того как правило перехода известно, мы считаем уже не наборы цифр, а строки выходных битов. Изначально, до обработки каких-либо позиций, активен только перенос \(0\). На каждой позиции есть два варианта для следующего выходного бита: \(0\) или \(1\). Каждый вариант переводит текущую маску в одну определённую следующую маску.
Если старший установленный бит числа \(k\) равен \(B\), то степень многочлена \(P(x)^k\) равна \(4k\), так что существенных позиций всего \(O(\log k)\). После обработки всех значащих битов достаточно трёх дополнительных нулевых шагов, чтобы удалить любой остаточный перенос, поскольку
$$4\mapsto 2\mapsto 1\mapsto 0.$$
В конце показатель учитывается в \(Q(k)\) тогда и только тогда, когда в конечном состоянии компонент, соответствующий переносу \(0\), остаётся нечётным. Следовательно, \(Q(k)\) равно сумме счётчиков всех конечных масок, в которых активен перенос \(0\).
Так как \(3=11_2\), активны только биты \(0\) и \(1\), поэтому
$$P(x)^3\equiv P(x)\,P(x^2)\pmod{2}.$$
Здесь выбираются цифры \(d_0,d_1\in\{0,1,2,3,4\}\), а показатель равен
$$m=d_0+2d_1.$$
Некоторые показатели возникают нечётное число раз и сохраняются, а некоторые возникают чётное число раз и исчезают. Например, \(m=4\) получается тремя способами: \((4,0)\), \((2,1)\) и \((0,2)\), значит, соответствующий коэффициент нечётный. А \(m=5\) получается двумя способами: \((3,1)\) и \((1,2)\), поэтому по модулю \(2\) он сокращается.
Полный перебор всех пар даёт
$$P(x)^3\equiv 1+x+x^4+x^6+x^8+x^{11}+x^{12}\pmod{2},$$
следовательно,
$$Q(3)=7.$$
Это совпадает с небольшим контрольным значением, используемым реализациями. Ещё два контрольных значения: \(Q(10)=17\) и \(Q(100)=35\).
Реализации на C++, Python и Java устроены одинаково. Сначала они предварительно вычисляют переход для каждой тройки: текущий бит числа \(k\), требуемый выходной бит и текущая 5-битовая маска паритетов переносов. Поскольку таких троек всего \(2\times 2\times 32\), этот этап очень мал.
Для конкретного значения \(k\) реализация хранит массив длины \(32\). Элемент, соответствующий маске \(M\), показывает, сколько префиксов выходных битов в данный момент приводят к состоянию \(M\). Начальное состояние имеет значение \(1\) только у маски, где активен перенос \(0\), и значение \(0\) во всех остальных случаях.
Далее программа проходит по битовым позициям от младших к старшим. На каждой позиции она рассматривает оба варианта следующего выходного бита, \(0\) и \(1\), применяет предварительно вычисленный переход и прибавляет текущий счётчик к соответствующему состоянию назначения. Иначе говоря, снаружи идёт DP по префиксам выходного числа, а внутри маленький автомат обновляет паритеты переносов.
Число обрабатываемых позиций равно длине двоичной записи \(k\) плюс три дополнительных шага, чего достаточно для полного удаления остаточного переноса. После этого суммируются все счётчики состояний, в чьей маске активен бит переноса \(0\). Полученная сумма и есть \(Q(k)\). Затем та же процедура выполняется для \(10,10^2,\dots,10^{18}\), и все восемнадцать результатов складываются.
Таблица переходов имеет постоянный размер. Для одного значения \(k\), если
$$L=\lfloor\log_2 k\rfloor+3,$$
то динамическая программа обрабатывает \(32\) маски на каждой из \(L\) позиций. Поэтому время работы равно \(O(32L)=O(\log k)\), а используемая память равна \(O(32)=O(1)\).
Во всей задаче требуется вычислить только восемнадцать входных значений, так что общий объём работы остаётся очень маленьким. Главное преимущество метода в том, что он зависит от длины двоичной записи числа \(k\), а не от гигантской степени \(4k\) раскрытого многочлена.
لنعرّف
$$P(x)=1+x+x^2+x^3+x^4.$$
ولكل عدد صحيح غير سالب \(k\)، نرمز بـ \(Q(k)\) إلى عدد المعاملات الفردية في توسعة \(P(x)^k\). المطلوب حساب
$$\sum_{t=1}^{18} Q(10^t).$$
عندما يصل \(k\) إلى \(10^{18}\)، يصبح التوسع المباشر للمقدار غير عملي تمامًا. لذلك لا تقوم التطبيقات ببناء كثير الحدود كاملًا، بل تتابع فقط فردية المعاملات وزوجيتها، لأن هذا هو جوهر السؤال.
نكتب التمثيل الثنائي للعدد \(k\) على الصورة
$$k=\sum_{b\ge 0} k_b 2^b,\qquad k_b\in\{0,1\}.$$
الفكرة الأساسية هي أن المسألة، عند العمل بترديد \(2\)، تتحول إلى أوتومات حمل صغير جدًا. توجد خمسة قيم ممكنة فقط للحمل، ومن ثم يوجد \(2^5=32\) حالة بارتي لا أكثر.
إذا كان \(a_m(k)\) هو معامل \(x^m\) في \(P(x)^k\)، فإن
$$Q(k)=\#\{m\ge 0: a_m(k)\equiv 1 \pmod{2}\}.$$
إذن لسنا بحاجة إلى القيم الدقيقة للمعاملات، بل نحتاج فقط إلى معرفة أي المعاملات يبقى غير صفري داخل \(\mathbb{F}_2\).
وفوق \(\mathbb{F}_2\) يتحقق قانون التربيع
$$f(x)^2=f(x^2).$$
ومن ثم نحصل مباشرة على العلاقة \(Q(2n)=Q(n)\). هذه الملاحظة مفيدة لفهم البنية الرياضية، حتى لو أن التطبيقات تحسب القوى المطلوبة مباشرة.
باستخدام البتات الثنائية للعدد \(k\) نحصل على
$$P(x)^k=\prod_{b\ge 0} P(x)^{k_b 2^b}\equiv \prod_{b:k_b=1} P(x^{2^b}) \pmod{2}.$$
ولكل بت فعّال \(b\)، يكون العامل الموافق هو
$$P(x^{2^b})=1+x^{2^b}+x^{2\cdot 2^b}+x^{3\cdot 2^b}+x^{4\cdot 2^b}.$$
اختيار حد واحد من كل عامل فعّال يكافئ اختيار رقم \(d_b\). إذا كان \(k_b=0\) فليس هناك حرية اختيار، ولا بد أن يكون \(d_b=0\). أما إذا كان \(k_b=1\) فحينها
$$d_b\in\{0,1,2,3,4\}.$$
وتنتج عن هذه الاختيارات القيمة
$$m=\sum_{b\ge 0} d_b 2^b.$$
إذن معامل \(x^m\) بترديد \(2\) يساوي بارتي عدد اختيارات الأرقام التي تعطي هذا الأس نفسه \(m\).
القيم \(d_b\) ليست بتات ثنائية عادية، لأنها قد تكون \(2\) أو \(3\) أو \(4\). لذلك فالتعبير السابق ليس تمثيلًا ثنائيًا وحيدًا. التفسير الصحيح هو أنه جمع ثنائي مع تتبع الحمل صراحة. نعالج البتات من الأصغر إلى الأكبر. إذا كان الحمل الداخل إلى الموضع \(b\) هو \(c\)، فإن المجموع المحلي يساوي
$$s_b=c+d_b.$$
أما بت الخرج في هذا الموضع من العدد \(m\) فيحقق
$$m_b\equiv s_b \pmod{2},$$
ويكون الحمل المنتقل إلى الموضع التالي هو
$$c'=\left\lfloor\frac{s_b}{2}\right\rfloor.$$
وبما أن كلا من \(c\) و\(d_b\) يقع بين \(0\) و\(4\)، فإن \(c'\) يبقى دائمًا ضمن المجموعة \(\{0,1,2,3,4\}\). لذلك لا نحتاج أبدًا إلى أكثر من خمس قيم للحمل.
عند تثبيت بادئة معينة من بتات الخرج الخاصة بالعدد \(m\)، لا نحتاج إلى معرفة العدد الدقيق للاختيارات الجزئية التي تصل إلى كل قيمة حمل. يكفي أن نعرف هل هذا العدد فردي أم زوجي.
لهذا يمكن تمثيل الحالة على أنها مجموعة جزئية من \(\{0,1,2,3,4\}\): تكون قيمة الحمل \(c\) فعّالة إذا وفقط إذا كان عدد المسارات الجزئية المؤدية إليها عددًا فرديًا. وهذا يكافئ قناعًا من 5 بتات، وبالتالي لا توجد سوى \(32\) حالة ممكنة.
ثبّت الآن \(t\in\{0,1\}\) حيث \(t=k_b\)، وثبّت أيضًا بت الخرج \(r\in\{0,1\}\). عندئذ تكون مجموعة الأرقام المسموح بها هي
$$D_t=\begin{cases} \{0\}, & t=0,\\ \{0,1,2,3,4\}, & t=1. \end{cases}$$
ومن كل حمل فعّال \(c\)، نفحص جميع \(d\in D_t\) التي تحقق \(c+d\equiv r\pmod{2}\). كل زوج من هذا النوع يولد الحمل التالي \(c'=\lfloor(c+d)/2\rfloor\). وإذا ظهر الحمل التالي نفسه مرتين، فإن الإسهامين يتلاشيان بترديد \(2\). لذلك تُوصف عملية الانتقال طبيعيًا على أنها قلب للبتات المناسبة في القناع الجديد.
بعد تثبيت قاعدة الانتقال، لا نعدّ اختيارات الأرقام نفسها، بل نعدّ سلاسل بتات الخرج. في البداية، قبل معالجة أي موضع، يكون الحمل الفعّال الوحيد هو \(0\). وفي كل موضع توجد إمكانيتان فقط لبت الخرج التالي: \(0\) أو \(1\). وكل اختيار ينقل القناع الحالي إلى قناع جديد محدد بشكل حتمي.
إذا كان أعلى بت فعّال في \(k\) هو \(B\)، فإن درجة \(P(x)^k\) تساوي \(4k\)، لذا فإن عدد المواضع المهمة لا يتجاوز \(O(\log k)\). وبعد انتهاء البتات المهمة في \(k\)، تكفي ثلاث خطوات إضافية تكون فيها الأرقام صفرية لتفريغ أي حمل متبق، لأن
$$4\mapsto 2\mapsto 1\mapsto 0.$$
في النهاية يساهم الأس في \(Q(k)\) إذا وفقط إذا كانت البارتي النهائية المرتبطة بالحمل \(0\) فردية. وعليه فإن \(Q(k)\) يساوي مجموع عدادات جميع الأقنعة النهائية التي يكون فيها مكوّن الحمل \(0\) فعّالًا.
بما أن \(3=11_2\)، فالبتان الفعّالان الوحيدان هما \(0\) و\(1\)، وبالتالي
$$P(x)^3\equiv P(x)\,P(x^2)\pmod{2}.$$
في هذه الحالة نختار \(d_0,d_1\in\{0,1,2,3,4\}\)، ويكون الأس الناتج
$$m=d_0+2d_1.$$
بعض الأسس يظهر عددًا فرديًا من المرات فيبقى، وبعضها يظهر عددًا زوجيًا من المرات فيختفي. مثلًا \(m=4\) يظهر ثلاث مرات عبر الأزواج \((4,0)\) و\((2,1)\) و\((0,2)\)، لذا فمعامله فردي. أما \(m=5\) فيظهر مرتين فقط عبر \((3,1)\) و\((1,2)\)، ولذلك يُلغى بترديد \(2\).
وبعد فحص جميع الأزواج نحصل على
$$P(x)^3\equiv 1+x+x^4+x^6+x^8+x^{11}+x^{12}\pmod{2},$$
ومن ثم
$$Q(3)=7.$$
وهذا يطابق قيمة التحقق الصغيرة المستخدمة في التطبيقات. كما أن قيمتي التحقق الأخريين هما \(Q(10)=17\) و\(Q(100)=35\).
تتبع تطبيقات C++ وPython وJava الخطة نفسها تمامًا. ففي البداية تُحسب مسبقًا جميع الانتقالات الممكنة التي يحددها ثلاثي مكوّن من: البت الحالي في \(k\)، وبت الخرج المطلوب، وقناع بارتي الحمل الحالي ذي الخمسة بتات. وبما أن عدد هذه الحالات لا يتجاوز \(2\times 2\times 32\)، فإن هذا الجزء صغير جدًا.
بالنسبة إلى قيمة معيّنة من \(k\)، تحتفظ الشيفرة بمصفوفة طولها \(32\). والعنصر الموافق للقناع \(M\) يمثل عدد بادئات الخرج التي تصل حاليًا إلى الحالة \(M\). في البداية تكون القيمة \(1\) فقط عند القناع الذي يمثل كون الحمل \(0\) فعّالًا، وتكون بقية القيم صفرًا.
بعد ذلك تمر الشيفرة على المواضع الثنائية من الأصغر إلى الأكبر. في كل موضع تجرّب احتمالَي بت الخرج \(0\) و\(1\)، وتستخدم الانتقال المحسوب مسبقًا لتحديد القناع التالي، ثم تضيف العداد الحالي إلى حالة الوصول المناسبة. وبصياغة أخرى، هناك برمجة ديناميكية خارجية تعدّ بادئات الخرج، بينما يقوم الأوتومات الداخلي الصغير بتحديث بارتي حالات الحمل.
عدد المواضع المعالجة يساوي طول التمثيل الثنائي لـ \(k\) مع ثلاث خطوات إضافية، وهو ما يكفي لإزالة أي حمل متبق. وفي النهاية تُجمع جميع العدادات التي يكون فيها بت الحمل \(0\) مفعّلًا داخل القناع. وهذه القيمة هي \(Q(k)\) بالضبط. ثم تتكرر العملية نفسها للقيم \(10,10^2,\dots,10^{18}\)، وتُجمع النتائج الثمانية عشر للحصول على الجواب النهائي.
حجم جدول الانتقالات ثابت. ولعدد واحد \(k\)، إذا وضعنا
$$L=\lfloor\log_2 k\rfloor+3,$$
فإن البرمجة الديناميكية تعالج \(32\) قناعًا عند كل واحد من المواضع \(L\). لذلك يكون الزمن \(O(32L)=O(\log k)\)، بينما تكون الذاكرة العاملة \(O(32)=O(1)\).
المسألة الكاملة تطلب ثمانية عشر إدخالًا فقط، لذا تبقى الكلفة الإجمالية صغيرة جدًا. النقطة الجوهرية هي أن المنهج يعتمد على عدد البتات في \(k\)، لا على الدرجة الضخمة \(4k\) لكثير الحدود بعد التوسع.