Fix integers \(k\) and \(\ell\) with \(3 \le k \le 6\) and \(1 \le \ell \le k-2\). Write a positive integer \(x\) in binary as
$$x=\sum_{p\ge 0} b_p 2^p,\qquad b_p\in\{0,1\}.$$
For each period \(r\), define the weighted binary digit sum
$$B_r(x)=\sum_{p\ge 0} b_p\,2^{p \bmod r}.$$
For a fixed pair \((k,\ell)\), the quantity of interest is
$$S_{k,\ell}(n)=\sum_{1\le x\le n,\ B_k(x)=B_\ell(x)} x \pmod{10^{16}}.$$
The full Project Euler task asks for the sum of \(S_{k,\ell}(10^{16})\) over all admissible pairs \((k,\ell)\). Direct enumeration is impossible, so the solution turns the digit condition into a bounded-state dynamic program over the bits of \(n\).
The central trick is to replace the equality of two weighted digit sums by a single signed balance equation. Once that balance is tracked while scanning the binary digits of \(n\), the algorithm can count all admissible numbers and add their values without listing them individually.
For each bit position \(p\), define
$$\delta_p=2^{p \bmod k}-2^{p \bmod \ell}.$$
Then the difference between the two weighted sums is
$$B_k(x)-B_\ell(x)=\sum_{p\ge 0} b_p\,\delta_p.$$
Therefore the matching condition is equivalent to
$$\sum_{p\ge 0} b_p\,\delta_p=0.$$
Each bit set to \(1\) contributes a fixed signed amount to a running balance, while each bit set to \(0\) contributes nothing. The coefficient pattern is periodic because it depends only on \(p \bmod k\) and \(p \bmod \ell\), but the program only needs the finitely many positions that appear below the highest bit of \(n\).
Let
$$L=\lfloor\log_2 n\rfloor+1$$
be the number of relevant bit positions when \(n>0\). Over these positions, define the safe bound
$$A=\sum_{p=0}^{L-1} |\delta_p|.$$
No partial or final balance can ever leave the interval
$$-A\le d\le A.$$
This observation turns the problem into a finite-state DP. Instead of storing balances in a dictionary, the implementation shifts the interval by an offset and uses ordinary arrays of width
$$2A+1.$$
That is why the method stays compact even though the original condition is phrased over all integers \(x\le n\).
Process the bits of \(n\) from the most significant bit down to the least significant bit. After deciding the higher bits, a DP state records
$$\text{state}=(d,e),$$
where \(d\) is the current balance and \(e\in\{0,1\}\) is a prefix-equality flag. The value \(e=1\) means the chosen prefix is still exactly equal to the prefix of \(n\); the value \(e=0\) means the constructed number is already smaller, so the remaining bits may be chosen freely.
If the current bit of \(n\) is \(n_p\in\{0,1\}\) and we choose the new bit \(u\in\{0,1\}\), then in the equal-prefix layer we must respect \(u\le n_p\). The balance update is
$$d'=d+u\,\delta_p.$$
The new flag becomes
$$e'=\begin{cases} 1,& e=1\ \text{and}\ u=n_p,\\ 0,& \text{otherwise}. \end{cases}$$
This is the standard digit-DP tightness idea, specialized to binary digits and to the balance defined above.
For every reachable state, the DP stores two quantities modulo \(10^{16}\):
$$C(d,e)=\text{number of represented prefixes},\qquad V(d,e)=\text{sum of their numeric values}.$$
When the next bit \(u\) is appended at position \(p\), every represented number gains \(u\,2^p\). Therefore the transition rules are
$$C'(d',e')\equiv C'(d',e')+C(d,e)\pmod{10^{16}},$$
$$V'(d',e')\equiv V'(d',e')+V(d,e)+u\,2^p\,C(d,e)\pmod{10^{16}}.$$
The second formula is what makes the solution efficient: a single transition adds the contribution of an entire family of numbers at once, rather than adding admissible integers one by one.
After all \(L\) bits are processed, the condition \(B_k(x)=B_\ell(x)\) is satisfied exactly when the final balance is zero. Hence
$$S_{k,\ell}(n)=V_{\mathrm{final}}(0,0)+V_{\mathrm{final}}(0,1)\pmod{10^{16}}.$$
The state for \(x=0\) is harmless: it also ends with balance \(0\), but it contributes value \(0\), so the sum over positive integers is unchanged.
Because \(10=1010_2\), the relevant positions are \(p=0,1,2,3\). Since \(p \bmod 1=0\) always, the coefficients are
$$\delta_0=2^0-2^0=0,\qquad \delta_1=2^1-2^0=1,\qquad \delta_2=2^2-2^0=3,\qquad \delta_3=2^0-2^0=0.$$
So bits at positions \(0\) and \(3\) do not affect the balance, while bits at positions \(1\) and \(2\) add \(1\) and \(3\). Among the integers \(1\le x\le 10\), the only values with total balance \(0\) are
$$1=0001_2,\qquad 8=1000_2,\qquad 9=1001_2.$$
Their sum is
$$1+8+9=18,$$
which matches the first checkpoint used by the C++, Python, and Java implementations. Those implementations also verify the larger checkpoints \(292\) for \(n=100\) and \(19{,}173{,}952\) for \(n=10^6\) when \((k,\ell)=(3,1)\).
The implementations begin with the trivial case \(n=0\), for which the required sum is \(0\). Otherwise they compute the bit length of \(n\), generate the coefficient list \(\delta_0,\dots,\delta_{L-1}\), and add their absolute values to determine the balance range.
Next they maintain four rolling arrays: counts and value sums for the smaller-prefix layer, and counts and value sums for the equal-prefix layer. For each bit position, fresh arrays are created for the next layer, the allowable bit choices are applied, and all arithmetic is reduced modulo \(10^{16}\).
The C++ implementation uses 128-bit intermediate multiplication to keep modular products safe, the Python implementation relies on arbitrary-precision integers, and the Java implementation uses repeated doubling so multiplication cannot overflow a signed 64-bit value. After evaluating one pair \((k,\ell)\), the implementation adds that contribution to the running total over all required pairs and prints the final result as a 16-digit decimal string.
For fixed \(n\), \(k\), and \(\ell\), let
$$L=\lfloor\log_2 n\rfloor+1,\qquad A=\sum_{p=0}^{L-1} |\delta_p|.$$
The DP uses two prefix layers and \(2A+1\) balance states. Therefore the running time is
$$O\bigl(L(2A+1)\bigr)=O(LA),$$
and the memory usage with rolling arrays is
$$O(2A+1)=O(A).$$
In the actual problem there are only ten admissible pairs \((k,\ell)\), and the bit length of \(10^{16}\) is small, so this bounded-state DP is easily fast enough in all three languages.
Fixiere ganze Zahlen \(k\) und \(\ell\) mit \(3 \le k \le 6\) und \(1 \le \ell \le k-2\). Schreibe eine positive Zahl \(x\) in Binärdarstellung als
$$x=\sum_{p\ge 0} b_p 2^p,\qquad b_p\in\{0,1\}.$$
Für jede Periode \(r\) definieren wir die gewichtete binäre Ziffernsumme
$$B_r(x)=\sum_{p\ge 0} b_p\,2^{p \bmod r}.$$
Für ein festes Paar \((k,\ell)\) interessiert die Größe
$$S_{k,\ell}(n)=\sum_{1\le x\le n,\ B_k(x)=B_\ell(x)} x \pmod{10^{16}}.$$
Die vollständige Aufgabe verlangt anschließend die Summe von \(S_{k,\ell}(10^{16})\) über alle zulässigen Paare \((k,\ell)\). Eine direkte Enumeration ist unmöglich; deshalb formt die Lösung die Ziffernbedingung in ein DP mit beschränktem Zustandsraum über die Bits von \(n\) um.
Der entscheidende Schritt ist, die Gleichheit zweier gewichteter Ziffernsummen durch eine einzige Vorzeichenbilanz zu ersetzen. Verfolgt man diese Bilanz beim Durchlaufen der Bits von \(n\), kann man sowohl die Anzahl der zulässigen Zahlen als auch ihre Summe berechnen, ohne jede Zahl einzeln zu erzeugen.
Für jede Bitposition \(p\) definieren wir
$$\delta_p=2^{p \bmod k}-2^{p \bmod \ell}.$$
Dann gilt für die Differenz der beiden gewichteten Summen
$$B_k(x)-B_\ell(x)=\sum_{p\ge 0} b_p\,\delta_p.$$
Die Matching-Bedingung ist also genau äquivalent zu
$$\sum_{p\ge 0} b_p\,\delta_p=0.$$
Jedes gesetzte Bit trägt einen festen positiven oder negativen Betrag zu einer laufenden Bilanz bei, jedes nicht gesetzte Bit trägt \(0\) bei. Das Muster der Koeffizienten ist periodisch, weil es nur von \(p \bmod k\) und \(p \bmod \ell\) abhängt; praktisch braucht das Programm aber nur die endlich vielen Positionen bis zum höchsten Bit von \(n\).
Sei
$$L=\lfloor\log_2 n\rfloor+1$$
die Anzahl relevanter Bitpositionen für \(n>0\). Über diese Positionen setzen wir die sichere Schranke
$$A=\sum_{p=0}^{L-1} |\delta_p|.$$
Keine partielle oder endgültige Bilanz kann dann den Bereich
$$-A\le d\le A$$
verlassen. Genau dadurch wird das Problem endlich. Die Implementierung verschiebt dieses Intervall mit einem Offset und speichert alle Zustände in gewöhnlichen Arrays der Breite
$$2A+1.$$
So entsteht aus einer globalen Zahleneigenschaft eine kompakte Zustandsmenge.
Die Bits von \(n\) werden vom höchstwertigen Bit bis zum niederwertigsten Bit verarbeitet. Nach der Wahl der höheren Bits speichert ein Zustand
$$\text{state}=(d,e),$$
wobei \(d\) die aktuelle Bilanz und \(e\in\{0,1\}\) ein Präfix-Flag ist. \(e=1\) bedeutet, dass das bisher gebildete Präfix noch exakt mit dem Präfix von \(n\) übereinstimmt; \(e=0\) bedeutet, dass die gebildete Zahl bereits kleiner ist und die restlichen Bits frei gewählt werden dürfen.
Ist das aktuelle Bit von \(n\) gleich \(n_p\in\{0,1\}\) und wir wählen das neue Bit \(u\in\{0,1\}\), dann gilt in der Gleichheitslage die Beschränkung \(u\le n_p\). Die Bilanz wird aktualisiert durch
$$d'=d+u\,\delta_p.$$
Das neue Präfix-Flag ist
$$e'=\begin{cases} 1,& e=1\ \text{and}\ u=n_p,\\ 0,& \text{otherwise}. \end{cases}$$
Das ist die übliche Tightness-Idee aus dem Digit-DP, hier auf Binärziffern und die definierte Bilanz zugeschnitten.
Zu jedem erreichbaren Zustand speichert das DP zwei Größen modulo \(10^{16}\):
$$C(d,e)=\text{count of prefixes},\qquad V(d,e)=\text{value sum}.$$
Wird an Position \(p\) das nächste Bit \(u\) angehängt, dann wächst jede dargestellte Zahl um \(u\,2^p\). Daher lauten die Übergänge
$$C'(d',e')\equiv C'(d',e')+C(d,e)\pmod{10^{16}},$$
$$V'(d',e')\equiv V'(d',e')+V(d,e)+u\,2^p\,C(d,e)\pmod{10^{16}}.$$
Gerade die zweite Formel macht die Methode effizient: Ein einziger DP-Übergang addiert den Beitrag einer ganzen Familie von Zahlen.
Nachdem alle \(L\) Bits verarbeitet wurden, ist die Bedingung \(B_k(x)=B_\ell(x)\) genau dann erfüllt, wenn die Endbilanz \(0\) ist. Also gilt
$$S_{k,\ell}(n)=V_{\mathrm{final}}(0,0)+V_{\mathrm{final}}(0,1)\pmod{10^{16}}.$$
Der Zustand für \(x=0\) stört nicht: Er endet ebenfalls mit Bilanz \(0\), trägt aber den Wert \(0\) zur Summe bei.
Da \(10=1010_2\), sind die relevanten Positionen \(p=0,1,2,3\). Weil stets \(p \bmod 1=0\) gilt, erhält man
$$\delta_0=2^0-2^0=0,\qquad \delta_1=2^1-2^0=1,\qquad \delta_2=2^2-2^0=3,\qquad \delta_3=2^0-2^0=0.$$
Die Bitpositionen \(0\) und \(3\) verändern die Bilanz also nicht; die Positionen \(1\) und \(2\) liefern Beiträge \(1\) bzw. \(3\). Unter den Zahlen \(1\le x\le 10\) haben genau
$$1=0001_2,\qquad 8=1000_2,\qquad 9=1001_2$$
Gesamtbilanz \(0\). Ihre Summe ist
$$1+8+9=18,$$
genau der erste Kontrollwert der C++-, Python- und Java-Implementierungen. Dort werden zusätzlich die Kontrollwerte \(292\) für \(n=100\) und \(19{,}173{,}952\) für \(n=10^6\) bei \((k,\ell)=(3,1)\) geprüft.
Die Implementierungen behandeln zuerst den trivialen Fall \(n=0\). Danach bestimmen sie die Bitlänge von \(n\), erzeugen die Koeffizientenliste \(\delta_0,\dots,\delta_{L-1}\) und summieren die Absolutbeträge, um die Breite des Bilanzraums festzulegen.
Anschließend verwalten sie vier rollierende Arrays: Anzahl und Wertsumme für die Schicht der bereits kleineren Präfixe sowie Anzahl und Wertsumme für die Schicht der noch gleichen Präfixe. Für jede Bitposition werden neue Arrays erzeugt, die zulässigen Bitentscheidungen eingetragen und alle Rechnungen modulo \(10^{16}\) reduziert.
Die C++-Implementierung verwendet 128-Bit-Zwischenprodukte für sichere modulare Multiplikation, die Python-Implementierung nutzt Ganzzahlen mit beliebiger Präzision, und die Java-Implementierung verwendet wiederholtes Verdoppeln, damit keine 64-Bit-Multiplikation überläuft. Nach einem festen Paar \((k,\ell)\) wird dessen Beitrag zur laufenden Gesamtsumme addiert und am Ende als 16-stellige Dezimalzahl ausgegeben.
Für feste Werte \(n\), \(k\) und \(\ell\) seien
$$L=\lfloor\log_2 n\rfloor+1,\qquad A=\sum_{p=0}^{L-1} |\delta_p|.$$
Das DP besitzt zwei Präfixschichten und \(2A+1\) Bilanzzustände. Damit beträgt die Laufzeit
$$O\bigl(L(2A+1)\bigr)=O(LA),$$
und der Speicherverbrauch mit rollierenden Arrays ist
$$O(2A+1)=O(A).$$
In der eigentlichen Aufgabe gibt es nur zehn zulässige Paare \((k,\ell)\), und die Bitlänge von \(10^{16}\) ist klein. Deshalb ist dieser Ansatz in allen drei Sprachen problemlos schnell genug.
\(3 \le k \le 6\) ve \(1 \le \ell \le k-2\) olacak şekilde \(k\) ve \(\ell\) sabit olsun. Pozitif bir \(x\) sayısını ikili tabanda
$$x=\sum_{p\ge 0} b_p 2^p,\qquad b_p\in\{0,1\}$$
şeklinde yazalım. Her \(r\) periyodu için ağırlıklı ikili basamak toplamı
$$B_r(x)=\sum_{p\ge 0} b_p\,2^{p \bmod r}$$
olarak tanımlanır. Sabit bir \((k,\ell)\) çifti için ilgilendiğimiz büyüklük
$$S_{k,\ell}(n)=\sum_{1\le x\le n,\ B_k(x)=B_\ell(x)} x \pmod{10^{16}}.$$
Asıl Project Euler sorusu, tüm uygun \((k,\ell)\) çiftleri için \(S_{k,\ell}(10^{16})\) değerlerinin toplamını ister. Doğrudan tarama yapılamadığı için çözüm, bu basamak eşitliğini bitler üzerinde çalışan ve durum sayısı sınırlı olan bir dinamik programa dönüştürür.
Ana fikir, iki ağırlıklı basamak toplamının eşitliğini tek bir işaretli denge denklemine çevirmektir. Bu denge, \(n\)'in bitleri taranırken izlendiğinde, uygun sayıların hem adedi hem de değer toplamı tek tek sayı üretmeden hesaplanabilir.
Her bit konumu \(p\) için
$$\delta_p=2^{p \bmod k}-2^{p \bmod \ell}$$
tanımını yapalım. O zaman iki ağırlıklı toplamın farkı
$$B_k(x)-B_\ell(x)=\sum_{p\ge 0} b_p\,\delta_p$$
olur. Dolayısıyla eşleşme koşulu tam olarak
$$\sum_{p\ge 0} b_p\,\delta_p=0$$
demektir. \(1\) olan her bit, yürüyen dengeye sabit bir pozitif ya da negatif katkı yapar; \(0\) olan bit hiçbir katkı yapmaz. Katsayı deseni yalnızca \(p \bmod k\) ve \(p \bmod \ell\) değerlerine bağlı olduğu için periyodiktir, fakat program için yalnızca \(n\)'in en yüksek bitine kadar olan sonlu konumlar gerekir.
\(n>0\) için ilgili bit sayısı
$$L=\lfloor\log_2 n\rfloor+1$$
olsun. Bu bitler üzerinde güvenli sınır
$$A=\sum_{p=0}^{L-1} |\delta_p|$$
şeklindedir. Hiçbir ara ya da nihai denge değeri
$$-A\le d\le A$$
aralığının dışına çıkamaz. Bu nokta kritik önemdedir; çünkü sınırsız gibi görünen koşul, genişliği
$$2A+1$$
olan sonlu bir dizi aralığına indirgenmiş olur. Uygulama bu aralığı bir ofset ile kaydırıp sıradan diziler kullanır.
\(n\)'in bitleri en anlamlı bitten en düşük bite doğru işlenir. Daha yüksek bitler seçildikten sonra bir DP durumu
$$\text{state}=(d,e)$$
şeklindedir. Burada \(d\) mevcut denge, \(e\in\{0,1\}\) ise önek eşitliği bayrağıdır. \(e=1\) değeri, oluşturulan önekin hâlâ \(n\)'in önekiyle tamamen aynı olduğunu; \(e=0\) değeri ise sayının artık kesin olarak daha küçük olduğunu ve kalan bitlerin serbestçe seçilebileceğini gösterir.
\(n\)'in o andaki biti \(n_p\in\{0,1\}\) olsun ve biz yeni biti \(u\in\{0,1\}\) seçelim. Eşit önek katmanında \(u\le n_p\) şartı vardır. Yeni denge
$$d'=d+u\,\delta_p$$
olur. Yeni bayrak ise
$$e'=\begin{cases} 1,& e=1\ \text{and}\ u=n_p,\\ 0,& \text{otherwise}. \end{cases}$$
Bu, klasik digit DP içindeki tight mantığının ikili basamaklara uyarlanmış hâlidir.
Her ulaşılabilir durum için DP, \(10^{16}\) modunda iki nicelik tutar:
$$C(d,e)=\text{count of prefixes},\qquad V(d,e)=\text{value sum}.$$
Pozisyon \(p\)'de yeni bit \(u\) eklendiğinde, temsil edilen her sayı \(u\,2^p\) kadar büyür. Bu yüzden geçişler
$$C'(d',e')\equiv C'(d',e')+C(d,e)\pmod{10^{16}},$$
$$V'(d',e')\equiv V'(d',e')+V(d,e)+u\,2^p\,C(d,e)\pmod{10^{16}}$$
şeklindedir. İkinci formül yönteminin verimliliğini sağlar; tek bir geçiş, çok sayıda sayının toplam katkısını bir anda ekler.
Tüm \(L\) bit işlendiğinde, \(B_k(x)=B_\ell(x)\) koşulu tam olarak son dengenin \(0\) olması demektir. Dolayısıyla
$$S_{k,\ell}(n)=V_{\mathrm{final}}(0,0)+V_{\mathrm{final}}(0,1)\pmod{10^{16}}.$$
\(x=0\) durumu sorun yaratmaz; onun da dengesi \(0\) olur ama değeri \(0\) olduğu için pozitif sayıların toplamını değiştirmez.
\(10=1010_2\) olduğundan ilgili konumlar \(p=0,1,2,3\)'tür. \(p \bmod 1\) her zaman \(0\) olduğu için katsayılar
$$\delta_0=2^0-2^0=0,\qquad \delta_1=2^1-2^0=1,\qquad \delta_2=2^2-2^0=3,\qquad \delta_3=2^0-2^0=0$$
olur. Yani \(0\) ve \(3\). konumdaki bitler dengeyi değiştirmez; \(1\) ve \(2\). konumdaki bitler sırasıyla \(1\) ve \(3\) ekler. \(1\le x\le 10\) aralığında toplam dengesi \(0\) olan sayılar yalnızca
$$1=0001_2,\qquad 8=1000_2,\qquad 9=1001_2$$
olur. Toplamları
$$1+8+9=18$$
eder; bu da C++, Python ve Java uygulamalarında doğrulanan ilk kontrol değeridir. Aynı uygulamalar \((k,\ell)=(3,1)\) için \(n=100\) değerinde \(292\), \(n=10^6\) değerinde ise \(19{,}173{,}952\) sonucunu da doğrular.
Uygulamalar önce \(n=0\) özel durumunu ele alır. Daha sonra \(n\)'in bit uzunluğunu hesaplar, \(\delta_0,\dots,\delta_{L-1}\) katsayı listesini oluşturur ve mutlak değer toplamından denge aralığını belirler.
Ardından dört kayan dizi kullanılır: daha küçük önek katmanı için adet ve toplam, eşit önek katmanı için adet ve toplam. Her bit konumu işlendiğinde yeni diziler oluşturulur, izin verilen bit seçimleri uygulanır ve bütün aritmetik \(10^{16}\) modunda tutulur.
C++ uygulaması modüler çarpımda güvenlik için 128 bit ara çarpım kullanır; Python uygulaması keyfi büyüklükte tamsayılara dayanır; Java uygulaması ise işaretli 64 bit çarpma taşmasını önlemek için tekrar eden ikiye katlama tekniğini kullanır. Bir \((k,\ell)\) çifti tamamlandığında elde edilen katkı genel toplama eklenir ve sonuç 16 haneli ondalık biçimde yazdırılır.
Sabit \(n\), \(k\) ve \(\ell\) için
$$L=\lfloor\log_2 n\rfloor+1,\qquad A=\sum_{p=0}^{L-1} |\delta_p|$$
olsun. DP iki önek katmanı ve \(2A+1\) adet denge durumu kullanır. Buna göre zaman karmaşıklığı
$$O\bigl(L(2A+1)\bigr)=O(LA),$$
kayan dizilerle bellek karmaşıklığı ise
$$O(2A+1)=O(A)$$
olur. Gerçek problemde yalnızca on uygun \((k,\ell)\) çifti vardır ve \(10^{16}\)'nın bit uzunluğu küçüktür; bu nedenle yöntem her üç dilde de rahatlıkla yeterlidir.
Fijemos enteros \(k\) y \(\ell\) con \(3 \le k \le 6\) y \(1 \le \ell \le k-2\). Escribimos un entero positivo \(x\) en binario como
$$x=\sum_{p\ge 0} b_p 2^p,\qquad b_p\in\{0,1\}.$$
Para cada período \(r\), definimos la suma ponderada de dígitos binarios
$$B_r(x)=\sum_{p\ge 0} b_p\,2^{p \bmod r}.$$
Para un par fijo \((k,\ell)\), la cantidad buscada es
$$S_{k,\ell}(n)=\sum_{1\le x\le n,\ B_k(x)=B_\ell(x)} x \pmod{10^{16}}.$$
La tarea completa suma después \(S_{k,\ell}(10^{16})\) sobre todos los pares admisibles \((k,\ell)\). Una enumeración directa es inviable, así que la solución transforma la condición sobre dígitos en una programación dinámica de estados acotados sobre los bits de \(n\).
La idea clave consiste en reemplazar la igualdad entre dos sumas ponderadas por una sola ecuación de balance con signos. Si ese balance se sigue mientras se recorren los bits de \(n\), se pueden contar todos los números válidos y sumar sus valores sin generarlos uno por uno.
Para cada posición binaria \(p\), definimos
$$\delta_p=2^{p \bmod k}-2^{p \bmod \ell}.$$
Entonces la diferencia entre las dos sumas ponderadas vale
$$B_k(x)-B_\ell(x)=\sum_{p\ge 0} b_p\,\delta_p.$$
Por tanto, la condición de coincidencia es exactamente
$$\sum_{p\ge 0} b_p\,\delta_p=0.$$
Cada bit igual a \(1\) aporta una cantidad fija, positiva o negativa, al balance acumulado, mientras que cada bit igual a \(0\) no aporta nada. El patrón de coeficientes es periódico porque depende solo de \(p \bmod k\) y \(p \bmod \ell\), aunque en la práctica solo interesan las posiciones hasta el bit más alto de \(n\).
Sea
$$L=\lfloor\log_2 n\rfloor+1$$
el número de bits relevantes cuando \(n>0\). Sobre esas posiciones definimos la cota segura
$$A=\sum_{p=0}^{L-1} |\delta_p|.$$
Ningún balance parcial ni final puede salir del intervalo
$$-A\le d\le A.$$
Esa observación convierte el problema en un DP finito. En lugar de guardar balances en un mapa, la implementación desplaza el intervalo mediante un offset y usa arreglos normales de anchura
$$2A+1.$$
Así, una restricción global sobre enteros se traduce en una colección compacta de estados.
Los bits de \(n\) se procesan desde el más significativo hasta el menos significativo. Después de fijar los bits altos, un estado del DP guarda
$$\text{state}=(d,e),$$
donde \(d\) es el balance actual y \(e\in\{0,1\}\) es una bandera de igualdad de prefijo. El valor \(e=1\) significa que el prefijo construido todavía coincide exactamente con el prefijo de \(n\); el valor \(e=0\) significa que el número ya es menor y, por tanto, los bits restantes pueden elegirse libremente.
Si el bit actual de \(n\) es \(n_p\in\{0,1\}\) y elegimos el nuevo bit \(u\in\{0,1\}\), entonces en la capa de igualdad de prefijo debemos respetar \(u\le n_p\). El balance se actualiza mediante
$$d'=d+u\,\delta_p.$$
La nueva bandera vale
$$e'=\begin{cases} 1,& e=1\ \text{and}\ u=n_p,\\ 0,& \text{otherwise}. \end{cases}$$
Este es el mecanismo estándar de tightness en digit DP, adaptado aquí a dígitos binarios y al balance anterior.
Para cada estado alcanzable, el DP almacena dos magnitudes módulo \(10^{16}\):
$$C(d,e)=\text{count of prefixes},\qquad V(d,e)=\text{value sum}.$$
Cuando se añade el siguiente bit \(u\) en la posición \(p\), cada número representado aumenta en \(u\,2^p\). Por eso las transiciones son
$$C'(d',e')\equiv C'(d',e')+C(d,e)\pmod{10^{16}},$$
$$V'(d',e')\equiv V'(d',e')+V(d,e)+u\,2^p\,C(d,e)\pmod{10^{16}}.$$
La segunda fórmula es la pieza esencial: un solo paso del DP agrega la contribución de toda una familia de números.
Una vez procesados los \(L\) bits, la condición \(B_k(x)=B_\ell(x)\) se cumple exactamente cuando el balance final es cero. En consecuencia,
$$S_{k,\ell}(n)=V_{\mathrm{final}}(0,0)+V_{\mathrm{final}}(0,1)\pmod{10^{16}}.$$
El estado correspondiente a \(x=0\) no causa ningún problema: también termina con balance \(0\), pero aporta valor \(0\), de modo que la suma sobre enteros positivos no cambia.
Como \(10=1010_2\), las posiciones relevantes son \(p=0,1,2,3\). Dado que \(p \bmod 1=0\) siempre, los coeficientes son
$$\delta_0=2^0-2^0=0,\qquad \delta_1=2^1-2^0=1,\qquad \delta_2=2^2-2^0=3,\qquad \delta_3=2^0-2^0=0.$$
Por lo tanto, las posiciones \(0\) y \(3\) no modifican el balance, mientras que las posiciones \(1\) y \(2\) aportan \(1\) y \(3\). Entre los enteros \(1\le x\le 10\), los únicos con balance total \(0\) son
$$1=0001_2,\qquad 8=1000_2,\qquad 9=1001_2.$$
Su suma es
$$1+8+9=18,$$
exactamente el primer punto de control verificado por las implementaciones en C++, Python y Java. Esas implementaciones también comprueban los valores \(292\) para \(n=100\) y \(19{,}173{,}952\) para \(n=10^6\) cuando \((k,\ell)=(3,1)\).
Las implementaciones comienzan tratando el caso trivial \(n=0\). Después calculan la longitud binaria de \(n\), generan la lista de coeficientes \(\delta_0,\dots,\delta_{L-1}\) y suman los valores absolutos para determinar el ancho del espacio de balances.
A continuación mantienen cuatro arreglos rodantes: conteos y sumas de valores para la capa de prefijos ya menores, y conteos y sumas de valores para la capa de prefijos todavía iguales. En cada posición de bit se crean arreglos nuevos para la siguiente capa, se aplican las decisiones permitidas y toda la aritmética se reduce módulo \(10^{16}\).
La implementación en C++ usa productos intermedios de 128 bits para que la multiplicación modular sea segura, la de Python se apoya en enteros de precisión arbitraria, y la de Java utiliza duplicación repetida para evitar desbordamientos en una multiplicación con enteros de 64 bits. Tras evaluar un par \((k,\ell)\), su contribución se añade al total acumulado y el resultado final se imprime como una cadena decimal de 16 dígitos.
Para valores fijos de \(n\), \(k\) y \(\ell\), definamos
$$L=\lfloor\log_2 n\rfloor+1,\qquad A=\sum_{p=0}^{L-1} |\delta_p|.$$
El DP usa dos capas de prefijo y \(2A+1\) estados de balance. Por tanto, el tiempo total es
$$O\bigl(L(2A+1)\bigr)=O(LA),$$
y la memoria con arreglos rodantes es
$$O(2A+1)=O(A).$$
En el problema real solo hay diez pares admisibles \((k,\ell)\), y la longitud binaria de \(10^{16}\) es pequeña, así que el método es más que suficiente en los tres lenguajes.
固定整数 \(k\) 和 \(\ell\)，其中 \(3 \le k \le 6\) 且 \(1 \le \ell \le k-2\)。把正整数 \(x\) 写成二进制展开
$$x=\sum_{p\ge 0} b_p 2^p,\qquad b_p\in\{0,1\}.$$
对任意周期 \(r\)，定义加权二进制位和
$$B_r(x)=\sum_{p\ge 0} b_p\,2^{p \bmod r}.$$
对于固定的 \((k,\ell)\)，需要计算
$$S_{k,\ell}(n)=\sum_{1\le x\le n,\ B_k(x)=B_\ell(x)} x \pmod{10^{16}}.$$
完整题目要求把所有允许参数对 \((k,\ell)\) 的 \(S_{k,\ell}(10^{16})\) 再求和。直接枚举显然不可行，因此解法必须把“两个加权位和相等”这个条件改写成适合动态规划处理的形式。
核心思路是把两个加权位和的相等条件，转化成一个单独的“平衡值为零”的条件。只要在扫描 \(n\) 的二进制位时持续维护这个平衡值，就能同时得到所有合法整数的个数与这些整数的总和，而不需要逐个枚举。
对每个二进制位位置 \(p\)，定义
$$\delta_p=2^{p \bmod k}-2^{p \bmod \ell}.$$
那么两个加权和之差就是
$$B_k(x)-B_\ell(x)=\sum_{p\ge 0} b_p\,\delta_p.$$
因此条件 \(B_k(x)=B_\ell(x)\) 与下面这个条件完全等价：
$$\sum_{p\ge 0} b_p\,\delta_p=0.$$
这表示：某一位取 \(1\) 时，会给累计平衡值增加一个固定的正数或负数；某一位取 \(0\) 时则没有贡献。由于 \(\delta_p\) 只依赖于 \(p \bmod k\) 和 \(p \bmod \ell\)，所以系数序列本身是周期性的。不过在实际计算里，只需要保留不超过 \(n\) 最高位的那些位置即可。
当 \(n>0\) 时，相关的二进制位数为
$$L=\lfloor\log_2 n\rfloor+1.$$
在这 \(L\) 个位置上，定义一个安全上界
$$A=\sum_{p=0}^{L-1} |\delta_p|.$$
无论是中间状态还是最终状态，累计平衡值都不可能超出区间
$$-A\le d\le A.$$
这一点非常重要，因为它说明状态空间是有限的。实现时只需用一个偏移量把区间 \([-A,A]\) 映射到普通数组下标上，数组总宽度就是
$$2A+1.$$
原本看起来像是“所有整数都要检查”的问题，就这样变成了一个有限状态的位 DP。
接下来从最高位到最低位依次处理 \(n\) 的二进制位。处理到某一层时，一个 DP 状态写成
$$\text{state}=(d,e),$$
其中 \(d\) 是当前累计平衡值，\(e\in\{0,1\}\) 是前缀是否仍与 \(n\) 完全相同的标志。若 \(e=1\)，说明已经构造出的前缀仍然等于 \(n\) 的对应前缀；若 \(e=0\)，说明当前构造出的数已经严格小于 \(n\)，后面的位就可以自由选择。
设 \(n\) 在位置 \(p\) 上的位是 \(n_p\in\{0,1\}\)，当前新选的位是 \(u\in\{0,1\}\)。当状态仍处于“前缀相等”层时，必须满足 \(u\le n_p\)。新的平衡值为
$$d'=d+u\,\delta_p.$$
新的前缀标志为
$$e'=\begin{cases} 1,& e=1\ \text{and}\ u=n_p,\\ 0,& \text{otherwise}. \end{cases}$$
这正是 digit DP 中常见的“tight”思想，只不过这里处理的是二进制位，并且状态里要跟踪的是上面定义的平衡值。
对每个可达状态，DP 不只保存“有多少种前缀到达这里”，还要保存“这些前缀代表的数值总和”。记为
$$C(d,e)=\text{count of prefixes},\qquad V(d,e)=\text{value sum}.$$
所有运算都按模 \(10^{16}\) 进行。若在位置 \(p\) 追加新位 \(u\)，则每个已有前缀的数值都会增加 \(u\,2^p\)。因此转移公式是
$$C'(d',e')\equiv C'(d',e')+C(d,e)\pmod{10^{16}},$$
$$V'(d',e')\equiv V'(d',e')+V(d,e)+u\,2^p\,C(d,e)\pmod{10^{16}}.$$
第二条公式是整套方法的关键。它说明一次状态转移就能把整批前缀的贡献一起加入，而不是先枚举出所有合法整数再求和。
当全部 \(L\) 个二进制位处理完之后，条件 \(B_k(x)=B_\ell(x)\) 等价于最终平衡值为零。所以固定 \((k,\ell)\) 时，答案就是
$$S_{k,\ell}(n)=V_{\mathrm{final}}(0,0)+V_{\mathrm{final}}(0,1)\pmod{10^{16}}.$$
这里同时读取“已经小于 \(n\)”和“恰好等于 \(n\)”两层。至于 \(x=0\) 这个状态，虽然它也会落在平衡值 \(0\) 上，但它贡献的数值是 \(0\)，因此不会影响对正整数的求和结果。
由于 \(10=1010_2\)，相关位位置是 \(p=0,1,2,3\)。又因为 \(p \bmod 1\) 永远等于 \(0\)，所以系数依次为
$$\delta_0=2^0-2^0=0,\qquad \delta_1=2^1-2^0=1,\qquad \delta_2=2^2-2^0=3,\qquad \delta_3=2^0-2^0=0.$$
这说明第 \(0\) 位和第 \(3\) 位不会改变平衡值，第 \(1\) 位若取 \(1\) 会增加 \(1\)，第 \(2\) 位若取 \(1\) 会增加 \(3\)。在 \(1\le x\le 10\) 中，只有下面三个数的总平衡值为 \(0\)：
$$1=0001_2,\qquad 8=1000_2,\qquad 9=1001_2.$$
它们的和是
$$1+8+9=18,$$
这恰好与 C++、Python 和 Java 实现中验证的第一个检查点一致。对于同一个参数对 \((3,1)\)，这些实现还验证了 \(n=100\) 时得到 \(292\)，\(n=10^6\) 时得到 \(19{,}173{,}952\)。
三个实现都会先处理 \(n=0\) 的特例。若 \(n>0\)，就先求出 \(n\) 的二进制位数，构造系数序列 \(\delta_0,\dots,\delta_{L-1}\)，再通过绝对值之和确定平衡值状态的总宽度。
随后实现维护四个滚动数组：较小前缀层的“数量”和“数值总和”，以及相等前缀层的“数量”和“数值总和”。每处理一位，就新建下一层数组，把允许的两种位选择写入对应位置，并始终把运算结果压到模 \(10^{16}\) 的范围内。
C++ 实现为了安全地进行模乘，使用了 128 位中间结果；Python 实现直接利用任意精度整数；Java 实现则采用重复加倍的方式完成模乘，从而避免 64 位带符号整数溢出。每算完一个 \((k,\ell)\) 参数对，就把该结果加入总答案，最后按 16 位十进制字符串格式输出。
对固定的 \(n\)、\(k\)、\(\ell\)，记
$$L=\lfloor\log_2 n\rfloor+1,\qquad A=\sum_{p=0}^{L-1} |\delta_p|.$$
DP 有两层前缀状态，每层有 \(2A+1\) 个可能的平衡值，因此总时间复杂度为
$$O\bigl(L(2A+1)\bigr)=O(LA),$$
使用滚动数组后的空间复杂度为
$$O(2A+1)=O(A).$$
在本题中，合法参数对只有十个，而 \(10^{16}\) 的二进制长度也不大，所以这种有界状态 DP 在三种语言里都完全足够快。
Зафиксируем целые \(k\) и \(\ell\), где \(3 \le k \le 6\) и \(1 \le \ell \le k-2\). Положительное число \(x\) записывается в двоичном виде как
$$x=\sum_{p\ge 0} b_p 2^p,\qquad b_p\in\{0,1\}.$$
Для каждого периода \(r\) определим взвешенную сумму двоичных цифр
$$B_r(x)=\sum_{p\ge 0} b_p\,2^{p \bmod r}.$$
Для фиксированной пары \((k,\ell)\) требуется найти величину
$$S_{k,\ell}(n)=\sum_{1\le x\le n,\ B_k(x)=B_\ell(x)} x \pmod{10^{16}}.$$
Полная задача затем суммирует \(S_{k,\ell}(10^{16})\) по всем допустимым парам \((k,\ell)\). Прямой перебор невозможен, поэтому решение переводит условие на цифры в динамическое программирование по битам с ограниченным числом состояний.
Главная идея состоит в том, чтобы заменить равенство двух взвешенных сумм одной балансной формулой со знаками. Если отслеживать этот баланс при просмотре битов числа \(n\), можно одновременно посчитать все допустимые числа и сумму их значений, не перечисляя их по одному.
Для каждой битовой позиции \(p\) положим
$$\delta_p=2^{p \bmod k}-2^{p \bmod \ell}.$$
Тогда разность двух взвешенных сумм равна
$$B_k(x)-B_\ell(x)=\sum_{p\ge 0} b_p\,\delta_p.$$
Следовательно, условие совпадения эквивалентно равенству
$$\sum_{p\ge 0} b_p\,\delta_p=0.$$
Каждый бит, равный \(1\), добавляет к текущему балансу фиксированный положительный или отрицательный вклад, а бит \(0\) не меняет баланс. Последовательность коэффициентов периодична, поскольку зависит только от \(p \bmod k\) и \(p \bmod \ell\), но на практике нужны лишь позиции до старшего бита числа \(n\).
Пусть
$$L=\lfloor\log_2 n\rfloor+1$$
обозначает число существенных битов при \(n>0\). На этих позициях введем безопасную оценку
$$A=\sum_{p=0}^{L-1} |\delta_p|.$$
Ни промежуточный, ни окончательный баланс не может выйти за пределы интервала
$$-A\le d\le A.$$
Именно это делает DP конечным. Реализация просто сдвигает интервал \([-A,A]\) на постоянный offset и использует обычные массивы ширины
$$2A+1.$$
Так глобальное ограничение на число превращается в компактное множество состояний.
Биты числа \(n\) обрабатываются от старшего к младшему. После выбора старших битов состояние DP имеет вид
$$\text{state}=(d,e),$$
где \(d\) — текущий баланс, а \(e\in\{0,1\}\) — флаг равенства префикса. Значение \(e=1\) означает, что построенный префикс пока совпадает с префиксом числа \(n\); значение \(e=0\) означает, что построенное число уже строго меньше, и оставшиеся биты можно выбирать свободно.
Пусть текущий бит числа \(n\) равен \(n_p\in\{0,1\}\), а мы выбираем новый бит \(u\in\{0,1\}\). В слое равного префикса требуется условие \(u\le n_p\). Новый баланс вычисляется по формуле
$$d'=d+u\,\delta_p.$$
Новый флаг равен
$$e'=\begin{cases} 1,& e=1\ \text{and}\ u=n_p,\\ 0,& \text{otherwise}. \end{cases}$$
Это стандартная идея tightness из digit DP, адаптированная к двоичным цифрам и к отслеживаемому балансу.
Для каждого достижимого состояния DP хранит две величины по модулю \(10^{16}\):
$$C(d,e)=\text{count of prefixes},\qquad V(d,e)=\text{value sum}.$$
Если в позиции \(p\) дописывается бит \(u\), то каждое представленное число увеличивается на \(u\,2^p\). Поэтому переходы имеют вид
$$C'(d',e')\equiv C'(d',e')+C(d,e)\pmod{10^{16}},$$
$$V'(d',e')\equiv V'(d',e')+V(d,e)+u\,2^p\,C(d,e)\pmod{10^{16}}.$$
Именно вторая формула делает метод быстрым: один переход сразу добавляет вклад целого семейства чисел.
После обработки всех \(L\) битов условие \(B_k(x)=B_\ell(x)\) выполняется тогда и только тогда, когда итоговый баланс равен нулю. Следовательно,
$$S_{k,\ell}(n)=V_{\mathrm{final}}(0,0)+V_{\mathrm{final}}(0,1)\pmod{10^{16}}.$$
Состояние, соответствующее \(x=0\), не мешает: оно тоже заканчивается с балансом \(0\), но вносит нулевой вклад в сумму.
Так как \(10=1010_2\), существенные позиции — это \(p=0,1,2,3\). Поскольку \(p \bmod 1=0\) всегда, коэффициенты равны
$$\delta_0=2^0-2^0=0,\qquad \delta_1=2^1-2^0=1,\qquad \delta_2=2^2-2^0=3,\qquad \delta_3=2^0-2^0=0.$$
Значит, биты в позициях \(0\) и \(3\) не меняют баланс, а биты в позициях \(1\) и \(2\) прибавляют \(1\) и \(3\). Среди чисел \(1\le x\le 10\) нулевой итоговый баланс имеют только
$$1=0001_2,\qquad 8=1000_2,\qquad 9=1001_2.$$
Их сумма равна
$$1+8+9=18,$$
что совпадает с первым контрольным значением в реализациях на C++, Python и Java. Для той же пары \((3,1)\) там также проверяются значения \(292\) при \(n=100\) и \(19{,}173{,}952\) при \(n=10^6\).
Во всех трех реализациях сначала обрабатывается тривиальный случай \(n=0\). Затем вычисляется двоичная длина числа \(n\), строится список коэффициентов \(\delta_0,\dots,\delta_{L-1}\), и по сумме абсолютных значений определяется ширина диапазона балансов.
После этого поддерживаются четыре скользящих массива: количество и сумма значений для слоя уже меньших префиксов, а также количество и сумма значений для слоя еще равных префиксов. На каждом битовом шаге создаются новые массивы следующего слоя, применяются допустимые выборы бита, а вся арифметика немедленно приводится по модулю \(10^{16}\).
Реализация на C++ использует 128-битные промежуточные произведения для безопасного модульного умножения, реализация на Python опирается на целые числа произвольной точности, а реализация на Java применяет повторяющееся удвоение, чтобы избежать переполнения 64-битного произведения. После вычисления очередной пары \((k,\ell)\) ее вклад добавляется к общему ответу, и в конце результат печатается как 16-значная десятичная строка.
Для фиксированных \(n\), \(k\) и \(\ell\) положим
$$L=\lfloor\log_2 n\rfloor+1,\qquad A=\sum_{p=0}^{L-1} |\delta_p|.$$
DP использует два префиксных слоя и \(2A+1\) состояний по значению баланса. Поэтому время работы равно
$$O\bigl(L(2A+1)\bigr)=O(LA),$$
а память при использовании скользящих массивов равна
$$O(2A+1)=O(A).$$
В реальной задаче допустимых пар \((k,\ell)\) всего десять, а двоичная длина числа \(10^{16}\) мала, так что этот метод с ограниченным числом состояний легко укладывается во все требования производительности.
لنثبت عددين صحيحين \(k\) و\(\ell\) بحيث \(3 \le k \le 6\) و\(1 \le \ell \le k-2\). نكتب العدد الموجب \(x\) بالصيغة الثنائية على صورة
$$x=\sum_{p\ge 0} b_p 2^p,\qquad b_p\in\{0,1\}.$$
ولكل فترة \(r\) نعرّف مجموعًا موزونًا لبتات التمثيل الثنائي:
$$B_r(x)=\sum_{p\ge 0} b_p\,2^{p \bmod r}.$$
بالنسبة إلى زوج ثابت \((k,\ell)\)، فالكمية المطلوبة هي
$$S_{k,\ell}(n)=\sum_{1\le x\le n,\ B_k(x)=B_\ell(x)} x \pmod{10^{16}}.$$
ثم تطلب المسألة الكاملة جمع \(S_{k,\ell}(10^{16})\) على جميع الأزواج المسموح بها. الفحص المباشر لجميع الأعداد حتى \(n\) غير ممكن، لذلك يحوّل الحل شرط تساوي المجموعين إلى برمجة ديناميكية على البتات ذات فضاء حالات محدود.
الفكرة الأساسية هي استبدال مساواة مجموعين موزونين بمعادلة توازن واحدة ذات إشارات موجبة وسالبة. وإذا تتبعنا هذا التوازن أثناء المرور على بتات \(n\)، أمكننا حساب جميع الأعداد الصحيحة الموافقة وجمع قيمها من غير تعداد صريح لكل عدد.
لكل موضع ثنائي \(p\) نعرّف
$$\delta_p=2^{p \bmod k}-2^{p \bmod \ell}.$$
وعندئذ يصبح فرق المجموعين الموزونين
$$B_k(x)-B_\ell(x)=\sum_{p\ge 0} b_p\,\delta_p.$$
إذن شرط التطابق يكافئ تمامًا
$$\sum_{p\ge 0} b_p\,\delta_p=0.$$
كل بت يساوي \(1\) يضيف مساهمة ثابتة ذات إشارة إلى رصيد جارٍ، أما البت الذي يساوي \(0\) فلا يضيف شيئًا. وتسلسل المعاملات دوري لأنه يعتمد فقط على \(p \bmod k\) و\(p \bmod \ell\)، لكن التنفيذ يحتاج عمليًا إلى المواضع الواقعة تحت أعلى بت في \(n\) فقط.
ليكن
$$L=\lfloor\log_2 n\rfloor+1$$
هو عدد البتات المهمة عندما \(n>0\). وعلى هذه المواضع نعرّف الحد الآمن
$$A=\sum_{p=0}^{L-1} |\delta_p|.$$
لا يمكن لأي رصيد جزئي أو نهائي أن يخرج عن المجال
$$-A\le d\le A.$$
هذه الملاحظة هي التي تجعل المسألة منتهية من ناحية الحالات. فبدلًا من تخزين الأرصدة في بنية مفتوحة، يقوم التنفيذ بإزاحة المجال باستخدام ثابت مناسب ويعمل على مصفوفات عادية عرضها
$$2A+1.$$
وبذلك يتحول الشرط العالمي على الأعداد إلى فضاء حالات صغير ومحدد.
تُعالَج بتات \(n\) من الأعلى إلى الأسفل. وبعد تثبيت البتات الأعلى، تمثل حالة البرمجة الديناميكية
$$\text{state}=(d,e),$$
حيث \(d\) هو الرصيد الحالي و\(e\in\{0,1\}\) هو علم يدل على ما إذا كانت البادئة المبنية ما تزال مساوية تمامًا لبادئة \(n\). إذا كان \(e=1\)، فهذا يعني أن البادئة الحالية لم تنخفض بعد عن \(n\). وإذا كان \(e=0\)، فهذا يعني أن العدد المبني أصبح أصغر من \(n\)، ومن ثم يمكن اختيار البتات اللاحقة بحرية.
إذا كان بت \(n\) في الموضع \(p\) هو \(n_p\in\{0,1\}\)، واخترنا البت الجديد \(u\in\{0,1\}\)، ففي طبقة التساوي يجب احترام الشرط \(u\le n_p\). وعندئذ يكون التحديث
$$d'=d+u\,\delta_p.$$
أما العلم الجديد فيصبح
$$e'=\begin{cases} 1,& e=1\ \text{and}\ u=n_p,\\ 0,& \text{otherwise}. \end{cases}$$
وهذه هي فكرة tight المعتادة في digit DP، ولكنها مطبقة هنا على البتات الثنائية وعلى رصيد التوازن المذكور.
لكل حالة قابلة للوصول، تحتفظ البرمجة الديناميكية بمقدارين بترديد \(10^{16}\):
$$C(d,e)=\text{count of prefixes},\qquad V(d,e)=\text{value sum}.$$
وعند إلحاق البت \(u\) في الموضع \(p\)، تزداد قيمة كل عدد ممثل بمقدار \(u\,2^p\). لذلك تكون الانتقالات
$$C'(d',e')\equiv C'(d',e')+C(d,e)\pmod{10^{16}},$$
$$V'(d',e')\equiv V'(d',e')+V(d,e)+u\,2^p\,C(d,e)\pmod{10^{16}}.$$
المعادلة الثانية هي لبّ الحل، لأنها تسمح بإضافة أثر عائلة كاملة من الأعداد عبر انتقال واحد فقط بدل تعداد الأعداد الصحيحة المسموح بها واحدًا واحدًا.
بعد معالجة جميع البتات \(L\)، يتحقق الشرط \(B_k(x)=B_\ell(x)\) إذا وفقط إذا كان الرصيد النهائي صفرًا. ولذلك فإن
$$S_{k,\ell}(n)=V_{\mathrm{final}}(0,0)+V_{\mathrm{final}}(0,1)\pmod{10^{16}}.$$
والحالة الموافقة للعدد \(x=0\) لا تسبب أي مشكلة، لأنها تنتهي أيضًا برصيد \(0\)، لكن قيمتها العددية صفر، فلا تؤثر في مجموع الأعداد الموجبة.
بما أن \(10=1010_2\)، فالمواضع المهمة هي \(p=0,1,2,3\). ولأن \(p \bmod 1=0\) دائمًا، نحصل على المعاملات
$$\delta_0=2^0-2^0=0,\qquad \delta_1=2^1-2^0=1,\qquad \delta_2=2^2-2^0=3,\qquad \delta_3=2^0-2^0=0.$$
إذن البتان في الموضعين \(0\) و\(3\) لا يغيران الرصيد، بينما يضيف البتان في الموضعين \(1\) و\(2\) القيمتين \(1\) و\(3\) على الترتيب. ضمن المجال \(1\le x\le 10\)، لا يحقق الرصيد الكلي \(0\) إلا الأعداد
$$1=0001_2,\qquad 8=1000_2,\qquad 9=1001_2.$$
ومجموعها
$$1+8+9=18,$$
وهو تمامًا أول اختبار تتحقق منه تطبيقات C++ وPython وJava. كما تتحقق هذه التطبيقات أيضًا من القيمتين \(292\) عندما \(n=100\) و\(19{,}173{,}952\) عندما \(n=10^6\) للزوج نفسه \((3,1)\).
تبدأ التطبيقات الثلاثة بمعالجة الحالة الخاصة \(n=0\). بعد ذلك تُحسب طول الكتابة الثنائية للعدد \(n\)، وتُبنى قائمة المعاملات \(\delta_0,\dots,\delta_{L-1}\)، ثم يُجمع مقدارها المطلق لتحديد عرض مجال الرصيد.
ثم تُدار أربع مصفوفات منزلقة: عدد الحالات ومجموع القيم لطبقة البوادئ التي أصبحت أصغر من \(n\)، وعدد الحالات ومجموع القيم لطبقة البوادئ التي ما تزال مساوية لبادئة \(n\). ومع كل موضع بت جديد، تُنشأ مصفوفات للطبقة التالية، وتُطبَّق اختيارات البت المسموح بها، وتُختزل الحسابات كلها بترديد \(10^{16}\).
تنفيذ C++ يستخدم ضربًا وسيطًا بعرض 128 بت لضمان سلامة الضرب المعياري، وتنفيذ Python يعتمد على الأعداد الصحيحة ذات الدقة غير المحدودة، أما تنفيذ Java فيستخدم أسلوب المضاعفة المتكررة لتجنب فيض الضرب على أعداد 64 بت. وبعد حساب مساهمة زوج واحد \((k,\ell)\)، تُضاف هذه المساهمة إلى المجموع الكلي، ثم يُطبع الناتج النهائي كسلسلة عشرية ذات 16 خانة.
للقيم الثابتة \(n\) و\(k\) و\(\ell\)، نضع
$$L=\lfloor\log_2 n\rfloor+1,\qquad A=\sum_{p=0}^{L-1} |\delta_p|.$$
تستخدم البرمجة الديناميكية طبقتين للبادئة و\(2A+1\) حالة ممكنة للرصيد. لذلك فإن التعقيد الزمني هو
$$O\bigl(L(2A+1)\bigr)=O(LA),$$
أما التعقيد المكاني مع المصفوفات المنزلقة فهو
$$O(2A+1)=O(A).$$
في المسألة الفعلية لا يوجد سوى عشرة أزواج مسموح بها \((k,\ell)\)، كما أن طول التمثيل الثنائي للعدد \(10^{16}\) صغير نسبيًا، ولهذا يكون هذا الأسلوب سريعًا بما يكفي بسهولة في اللغات الثلاث.