For each \(n=0,1,\dots,99\), the problem builds a 10-component bound vector from the recurrence
$$a_0=1,\qquad a_1=7,\qquad a_m \equiv 7a_{m-1}+a_{m-2}^2 \pmod{10^9+7}.$$
The block \((a_{10n},a_{10n+1},\dots,a_{10n+9})\) is attached to the 10 edges of the complete graph \(K_5\) in the order
$$ (0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4). $$
For one such block \(U=(U_e)_{e\in E(K_5)}\), we must evaluate
$$P(U)=\sum_{\substack{x_0,\dots,x_4\ge 0\\ x_u+x_v\le U_{uv}\ \forall\,0\le u<v\le 4}} 2^{x_0}3^{x_1}5^{x_2}7^{x_3}11^{x_4}\pmod{10^9+7},$$
and the final answer is
$$\sum_{n=0}^{99} P(a_{10n},a_{10n+1},\dots,a_{10n+9}) \pmod{10^9+7},$$
with the ten numbers interpreted in the fixed edge order above. The direct five-dimensional summation is only realistic for tiny bounds; the real inputs are large, so the solution rewrites the inequalities bit by bit and performs a digit DP on carry states.
The key observation is that every constraint is of the form \(x_u+x_v\le U_{uv}\). In binary, such an inequality can be checked locally: at bit \(k\), only the two chosen bits, the \(k\)-th bit of the bound, and one small carry value matter. Once that is done simultaneously on all 10 edges, the original 5D sum becomes a finite-state weighted DP.
The five variables are the vertices of \(K_5\), and every edge \(\{u,v\}\) contributes one upper bound \(U_{uv}\). The term attached to a feasible point \((x_0,\dots,x_4)\) is multiplicative:
$$2^{x_0}3^{x_1}5^{x_2}7^{x_3}11^{x_4}=\prod_{i=0}^{4} p_i^{x_i},\qquad (p_0,p_1,p_2,p_3,p_4)=(2,3,5,7,11).$$
So the job is not just to count feasible 5-tuples, but to sum a geometric weight over all of them.
The outer problem does not use one bound vector but 100 of them. The recurrence produces 1000 values, and each consecutive block of 10 values becomes one complete set of pairwise bounds. Because each block is independent of the others once the sequence has been generated, the total answer is simply the sum of 100 values of \(P(U)\).
This is an important structural simplification: all difficult mathematics is concentrated in evaluating one generic quantity \(P(U)\). After that, the final Euler sum is just an outer aggregation over 100 instances.
Fix one edge \(e=\{u,v\}\). Write
$$x_i=\sum_{k\ge 0} b_{i,k}2^k,\qquad b_{i,k}\in\{0,1\}.$$
After bits \(0,1,\dots,k-1\) have been decided, define the remaining upper parts
$$y_i^{(k)}=\left\lfloor \frac{x_i}{2^k}\right\rfloor.$$
For the edge \(e\), keep a nonnegative integer \(c_{e,k}\) such that the unfinished higher bits must satisfy
$$y_u^{(k)}+y_v^{(k)}+c_{e,k}\le \left\lfloor \frac{U_e}{2^k}\right\rfloor.$$
This carry is the amount of excess forced upward by the lower bits already chosen. At the start, no lower bits have been processed, so \(c_{e,0}=0\) for every edge.
Let \(u_{e,k}\in\{0,1\}\) be the \(k\)-th binary digit of \(U_e\). Since
$$y_u^{(k)}=b_{u,k}+2y_u^{(k+1)},\qquad y_v^{(k)}=b_{v,k}+2y_v^{(k+1)},$$
substituting into the invariant gives
$$b_{u,k}+b_{v,k}+c_{e,k}+2\bigl(y_u^{(k+1)}+y_v^{(k+1)}\bigr)\le u_{e,k}+2\left\lfloor \frac{U_e}{2^{k+1}}\right\rfloor.$$
The smallest carry that makes the same statement true one level higher is therefore
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{b_{u,k}+b_{v,k}+c_{e,k}-u_{e,k}}{2}\right\rceil\right).$$
This is the core recurrence of the whole method. It says that an edge transition depends only on the two chosen vertex bits, the incoming carry on that edge, and the current bit of the bound.
For one edge, the pair bit sum \(b_{u,k}+b_{v,k}\) is in \(\{0,1,2\}\), the bound bit \(u_{e,k}\) is in \(\{0,1\}\), and if the incoming carry is already in \(\{0,1,2\}\), then
$$b_{u,k}+b_{v,k}+c_{e,k}-u_{e,k}\in\{-1,0,1,2,3,4\}.$$
Applying the formula above shows that the next carry also lies in \(\{0,1,2\}\). So each edge has exactly three possible carry states, and the full DP state space is
$$\{0,1,2\}^{10},\qquad |\{0,1,2\}^{10}|=3^{10}=59049.$$
At bit \(k\), choose the 5 binary digits \((b_{0,k},\dots,b_{4,k})\). It is convenient to regard them as a 5-bit mask \(m\in\{0,1\}^5\). That mask immediately determines the pair sums \(b_{u,k}+b_{v,k}\) on all 10 edges, so it also determines the next carry vector once the current state and the bound bits are known.
If the carry vector at level \(k\) is \(c^{(k)}\in\{0,1,2\}^{10}\), then for a fixed bound vector \(U\) the transition map \(T_k\) is defined edgewise by
$$\bigl(T_k(c^{(k)},m)\bigr)_e=\max\left(0,\left\lceil \frac{s_e(m)+c^{(k)}_e-u_{e,k}}{2}\right\rceil\right),$$
where \(s_e(m)\in\{0,1,2\}\) is the pair bit sum on edge \(e\) induced by the mask.
The exponential weight also factorizes over the binary digits. Since \(x_i=\sum_k b_{i,k}2^k\),
$$\prod_{i=0}^{4} p_i^{x_i}=\prod_{k\ge 0}\prod_{i=0}^{4} p_i^{\,b_{i,k}2^k}.$$
So one mask \(m\) chosen at bit \(k\) contributes the multiplicative factor
$$W_k(m)=\prod_{i=0}^{4}\left(p_i^{2^k}\right)^{b_{i,k}}\pmod{10^9+7}.$$
This is why the implementations precompute the 32 mask weights for each bit position: once those numbers are available, each DP transition only performs a table lookup and one modular multiplication.
Suppose that on one particular edge the incoming carry is \(c_{e,k}=1\), the bound bit is \(u_{e,k}=0\), and the current mask sets \(b_{u,k}=1\) and \(b_{v,k}=0\). Then
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{1+0+1-0}{2}\right\rceil\right)=1.$$
So the excess created by the lower bits is still large enough that one unit must be carried to the next binary level. If instead both endpoint bits were 1, then
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{1+1+1-0}{2}\right\rceil\right)=2,$$
which shows why carry value 2 really can occur and must be represented in the state space.
As a concrete full-instance checkpoint, when all ten bounds are equal to 2, the digit DP gives
$$P(2,2,\dots,2)=7120,$$
exactly matching brute force. The method is not approximate; it is an exact reformulation of the original summation.
Let \(D_k(c)\) be the total weight of all assignments to the first \(k\) bits whose carry vector after those bits is \(c\). Then
$$D_{k+1}(c')=\sum_{\substack{c\in\{0,1,2\}^{10}\\ m\in\{0,1\}^5\\ T_k(c,m)=c'}} D_k(c)\,W_k(m)\pmod{10^9+7},$$
with initial condition \(D_0(\mathbf 0)=1\) and \(D_0(c)=0\) for \(c\ne \mathbf 0\).
The implementations process 31 bit positions. That is enough because every bound produced by the recurrence lies below \(10^9+7<2^{30}\), and one extra zero bit safely flushes any residual carry. A 5-tuple \((x_0,\dots,x_4)\) is feasible exactly when all carries are zero after the final round, so
$$P(U)=D_{31}(\mathbf 0).$$
The C++, Python, and Java implementations all rely on the same mathematical ingredients. They precompute the 1000-term recurrence sequence, decode every one of the \(3^{10}\) carry states into its 10 ternary digits, build the pair-bit table for all 32 masks on the 10 edges, and precompute the 32 weight factors for each of the 31 bit positions.
The Python implementation is a thin wrapper around the compiled solver, so the heavy computation is the same carry-based digit DP used by the compiled versions. The Java implementation reproduces the same recurrence and transition logic directly.
For a single instance \(U\), the implementation first extracts the 31 binary columns of the 10 bounds. Then it runs the DP with two rolling layers: the current layer stores the values \(D_k(c)\), and the next layer accumulates \(D_{k+1}(c')\). The process starts from the all-zero carry vector and tries all 32 masks at each step.
A practical optimization is to track only active states, meaning states whose current DP value is nonzero. In the worst case the state space has 59049 elements, but in many layers only a fraction of them are reachable, so this sparse traversal saves time without changing the recurrence.
The reference implementation checks the DP against brute force on small cases. In particular, it verifies the exact values \(P(2,\dots,2)=7120\) and \(P(1,2,\dots,10)=799809376\), and it also tests random small bound vectors. Those checks confirm that the carry recurrence reproduces the original five-dimensional sum exactly.
After that, the 100 problem instances are independent: for each \(n\), take the block \((a_{10n},\dots,a_{10n+9})\), evaluate \(P(U)\), and add it to the total modulo \(10^9+7\). The compiled implementations parallelize this outer loop because each block can be solved independently.
For one bound vector, the worst-case DP cost is
$$O\!\left(31\cdot 3^{10}\cdot 2^5\cdot 10\right),$$
because there are 31 bit levels, at most \(3^{10}\) carry states, 32 masks per state, and 10 edges to update in one transition. The actual runtime is usually lower because the active-state optimization avoids scanning states with zero weight.
The memory usage is \(O(3^{10})\) for the two rolling DP layers, plus the precomputed state-decoding, mask, and weight tables. The outer summation over 100 instances multiplies the total amount of work by 100, but those 100 calls are independent and therefore parallel-friendly.
A naive brute-force approach would require iterating over five nested loops up to bounds near \(10^9\), which is completely infeasible. The digit-DP succeeds because it replaces huge numeric ranges by a tiny per-edge carry alphabet \(\{0,1,2\}\).
Für \(n=0,1,\dots,99\) erzeugt die Aufgabe zunächst mit der Rekursion
$$a_0=1,\qquad a_1=7,\qquad a_m \equiv 7a_{m-1}+a_{m-2}^2 \pmod{10^9+7}$$
einen Vektor aus 10 Schranken. Der Block \((a_{10n},a_{10n+1},\dots,a_{10n+9})\) wird in der festen Reihenfolge
$$ (0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4) $$
den 10 Kanten des vollständigen Graphen \(K_5\) zugeordnet. Für einen solchen Vektor \(U=(U_e)_{e\in E(K_5)}\) ist zu berechnen
$$P(U)=\sum_{\substack{x_0,\dots,x_4\ge 0\\ x_u+x_v\le U_{uv}\ \forall\,0\le u<v\le 4}} 2^{x_0}3^{x_1}5^{x_2}7^{x_3}11^{x_4}\pmod{10^9+7}.$$
Die gesuchte Endgröße ist dann
$$\sum_{n=0}^{99} P(a_{10n},a_{10n+1},\dots,a_{10n+9}) \pmod{10^9+7},$$
wobei die 10 Zahlen jeweils in derselben Kantenreihenfolge gelesen werden. Ein direkter fünfdimensionaler Schleifenansatz funktioniert nur für winzige Testfälle; für die echten Eingaben braucht man eine bitweise Dynamik mit Überträgen.
Der zentrale Punkt ist, dass jede Nebenbedingung die Form \(x_u+x_v\le U_{uv}\) hat. In Binärdarstellung lässt sich eine solche Ungleichung lokal prüfen: Auf Bit-Ebene genügen die beiden aktuellen Bits, das passende Schrankenbit und ein kleiner Übertragswert. Wenn man dieses Prinzip gleichzeitig auf allen 10 Kanten anwendet, wird die ursprüngliche 5D-Summe zu einer endlichen, gewichteten Zustands-DP.
Die fünf Variablen sind die fünf Ecken von \(K_5\), und jede Kante \(\{u,v\}\) trägt genau eine obere Schranke \(U_{uv}\). Das Gewicht eines zulässigen Punkts \((x_0,\dots,x_4)\) ist multiplikativ:
$$2^{x_0}3^{x_1}5^{x_2}7^{x_3}11^{x_4}=\prod_{i=0}^{4} p_i^{x_i},\qquad (p_0,p_1,p_2,p_3,p_4)=(2,3,5,7,11).$$
Man zählt also nicht nur zulässige 5-Tupel, sondern summiert über ihnen eine echte geometrische Gewichtung.
Das Euler-Problem verlangt nicht nur eine einzige Auswertung \(P(U)\), sondern 100 davon. Die Rekursion liefert 1000 Zahlen; jede Folge von 10 aufeinanderfolgenden Zahlen bildet einen vollständigen Schrankenvektor für alle Kanten. Sobald die Folge erzeugt ist, sind diese 100 Blöcke voneinander unabhängig.
Genau deshalb reicht es mathematisch, eine generische Auswertung von \(P(U)\) zu verstehen. Die endgültige Antwort ist danach nur noch die Summe über 100 voneinander getrennte Instanzen.
Fixiere eine Kante \(e=\{u,v\}\). Schreibe
$$x_i=\sum_{k\ge 0} b_{i,k}2^k,\qquad b_{i,k}\in\{0,1\}.$$
Nachdem die Bits \(0,1,\dots,k-1\) festgelegt wurden, betrachten wir die oberen Restteile
$$y_i^{(k)}=\left\lfloor \frac{x_i}{2^k}\right\rfloor.$$
Für die Kante \(e\) speichert man einen nichtnegativen Übertrag \(c_{e,k}\) mit der Bedeutung
$$y_u^{(k)}+y_v^{(k)}+c_{e,k}\le \left\lfloor \frac{U_e}{2^k}\right\rfloor.$$
Dieser Übertrag ist genau der Überschuss, den die bereits gewählten unteren Bits in die höheren Bits hineinschieben. Anfangs gilt für alle Kanten \(c_{e,0}=0\).
Sei \(u_{e,k}\in\{0,1\}\) das \(k\)-te Bit von \(U_e\). Wegen
$$y_u^{(k)}=b_{u,k}+2y_u^{(k+1)},\qquad y_v^{(k)}=b_{v,k}+2y_v^{(k+1)}$$
erhält man aus der Invariante
$$b_{u,k}+b_{v,k}+c_{e,k}+2\bigl(y_u^{(k+1)}+y_v^{(k+1)}\bigr)\le u_{e,k}+2\left\lfloor \frac{U_e}{2^{k+1}}\right\rfloor.$$
Der kleinste Übertrag, der dieselbe Aussage eine Ebene höher korrekt weiterträgt, ist daher
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{b_{u,k}+b_{v,k}+c_{e,k}-u_{e,k}}{2}\right\rceil\right).$$
Genau diese Rekurrenz ist das Herzstück der Lösung.
Auf einer Kante liegt die Bit-Summe \(b_{u,k}+b_{v,k}\) in \(\{0,1,2\}\), das Schrankenbit \(u_{e,k}\) in \(\{0,1\}\), und wenn der eingehende Übertrag bereits in \(\{0,1,2\}\) liegt, dann gilt
$$b_{u,k}+b_{v,k}+c_{e,k}-u_{e,k}\in\{-1,0,1,2,3,4\}.$$
Die Übergangsformel liefert also wieder nur \(0,1\) oder \(2\). Deshalb hat jede Kante genau drei Zustände, und der gesamte Zustandsraum ist
$$\{0,1,2\}^{10},\qquad |\{0,1,2\}^{10}|=3^{10}=59049.$$
Auf Ebene \(k\) wählt man die fünf Bits \((b_{0,k},\dots,b_{4,k})\). Man kann sie als 5-Bit-Maske \(m\in\{0,1\}^5\) auffassen. Diese Maske bestimmt sofort für jede Kante die Summe der beiden Endpunktbits und damit auch den nächsten Übertragszustand.
Wenn \(c^{(k)}\in\{0,1,2\}^{10}\) der aktuelle Vektor aller Kantenüberträge ist, dann lautet der Übergang zu Bit \(k+1\) komponentenweise
$$\bigl(T_k(c^{(k)},m)\bigr)_e=\max\left(0,\left\lceil \frac{s_e(m)+c^{(k)}_e-u_{e,k}}{2}\right\rceil\right),$$
wobei \(s_e(m)\in\{0,1,2\}\) die von der Maske induzierte Bit-Summe auf Kante \(e\) ist.
Da \(x_i=\sum_k b_{i,k}2^k\) gilt, faktorisiert das Gewicht als
$$\prod_{i=0}^{4} p_i^{x_i}=\prod_{k\ge 0}\prod_{i=0}^{4} p_i^{\,b_{i,k}2^k}.$$
Eine Maske \(m\) auf Bit \(k\) trägt also den Faktor
$$W_k(m)=\prod_{i=0}^{4}\left(p_i^{2^k}\right)^{b_{i,k}}\pmod{10^9+7}.$$
Darum werden in den Implementierungen für jedes Bit alle 32 Maskengewichte vorab berechnet.
Nehmen wir auf einer Kante den eingehenden Übertrag \(c_{e,k}=1\), das Schrankenbit \(u_{e,k}=0\) und die Endpunktbits \(b_{u,k}=1\), \(b_{v,k}=0\). Dann ist
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{1+0+1-0}{2}\right\rceil\right)=1.$$
Der Überschuss verschwindet also nicht, sondern wird in gleicher Größe nach oben weitergereicht. Wenn beide Endpunktbits 1 sind, erhält man
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{1+1+1-0}{2}\right\rceil\right)=2,$$
und genau daran sieht man, warum der Zustand 2 unverzichtbar ist.
Ein vollständiger Testfall mit allen zehn Schranken gleich 2 liefert
$$P(2,2,\dots,2)=7120,$$
und dieser Wert stimmt exakt mit vollständigem Brute Force überein.
Sei \(D_k(c)\) die Gesamtgewichtung aller Belegungen der ersten \(k\) Bits, deren Übertragsvektor nach diesen Bits \(c\) ist. Dann gilt
$$D_{k+1}(c')=\sum_{\substack{c\in\{0,1,2\}^{10}\\ m\in\{0,1\}^5\\ T_k(c,m)=c'}} D_k(c)\,W_k(m)\pmod{10^9+7},$$
mit \(D_0(\mathbf 0)=1\) und \(D_0(c)=0\) für \(c\ne \mathbf 0\).
Die Implementierungen verarbeiten 31 Bitpositionen. Das reicht, weil alle Schranken aus der Rekursion kleiner als \(10^9+7<2^{30}\) sind und ein zusätzliches Null-Bit am Ende jeden Restübertrag sichtbar macht. Genau dann, wenn nach der letzten Runde alle Kantenüberträge 0 sind, ist das 5-Tupel zulässig. Also gilt
$$P(U)=D_{31}(\mathbf 0).$$
Die C++-, Python- und Java-Implementierungen beruhen auf denselben mathematischen Tabellen. Vorab erzeugen sie die 1000 Rekursionswerte, dekodieren alle \(3^{10}\) Zustände in ihre 10 ternären Kantenüberträge, bestimmen für jede der 32 Bitmasken die Bit-Summen auf allen 10 Kanten und berechnen für jede Bitposition die 32 Übergangsgewichte.
Die Python-Variante ist dabei nur ein dünner Einstiegspunkt, der die kompilierte Berechnung verwendet; die eigentliche Rechenarbeit ist dieselbe Digit-DP wie in den kompilierten Versionen. Die Java-Version setzt dieselbe Übergangslogik direkt nach.
Für ein festes \(U\) werden zuerst die 31 Bitspalten der 10 Schranken extrahiert. Danach läuft eine DP mit zwei rollierenden Ebenen: Die aktuelle Ebene speichert \(D_k(c)\), die nächste Ebene sammelt \(D_{k+1}(c')\). Gestartet wird immer im Nullzustand, und auf jeder Ebene werden alle 32 Masken ausprobiert.
Wichtig für die Praxis ist die Behandlung nur aktiver Zustände, also solcher Zustände mit momentan von Null verschiedenem DP-Wert. Der theoretische Raum enthält 59049 Zustände, aber in vielen Ebenen ist nur ein Teil davon überhaupt erreichbar.
Die Referenzimplementierung prüft die DP zusätzlich gegen Brute Force auf kleinen Fällen. Unter anderem werden die exakten Werte \(P(2,\dots,2)=7120\) und \(P(1,2,\dots,10)=799809376\) verifiziert, außerdem mehrere zufällige kleine Schrankenvektoren. Diese Tests bestätigen, dass die Übertragsrekurrenz die ursprüngliche 5D-Summe exakt wiedergibt.
Danach sind die 100 Problemblöcke unabhängig: Für jedes \(n\) wird der Block \((a_{10n},\dots,a_{10n+9})\) zu \(P(U)\) ausgewertet und zum Gesamtwert addiert. Die kompilierten Implementierungen parallelisieren genau diese äußere Schleife.
Für einen einzigen Schrankenvektor beträgt die DP-Kostenobergrenze
$$O\!\left(31\cdot 3^{10}\cdot 2^5\cdot 10\right),$$
denn es gibt 31 Bitstufen, höchstens \(3^{10}\) Zustände, 32 Masken je Zustand und 10 Kantenaktualisierungen pro Übergang. Durch die Beschränkung auf aktive Zustände ist die praktische Laufzeit meist deutlich kleiner.
Der Speicherbedarf ist \(O(3^{10})\) für die zwei DP-Ebenen sowie zusätzlich die vorberechneten Zustands-, Masken- und Gewichtstabellen. Die äußere Summe über 100 Instanzen vervielfacht die Gesamtarbeit mit dem Faktor 100, verändert aber die innere Struktur der Methode nicht.
Ein naiver Ansatz mit fünf geschachtelten Schleifen müsste Bereiche bis nahe \(10^9\) durchlaufen und ist deshalb aussichtslos. Die Bit-DP funktioniert, weil sie riesige Wertebereiche durch das winzige Kantenalphabet \(\{0,1,2\}\) ersetzt.
Soruda \(n=0,1,\dots,99\) için önce şu özyineleme kullanılıyor:
$$a_0=1,\qquad a_1=7,\qquad a_m \equiv 7a_{m-1}+a_{m-2}^2 \pmod{10^9+7}.$$
Her \((a_{10n},a_{10n+1},\dots,a_{10n+9})\) bloğu, tam graf \(K_5\)'in 10 kenarına şu sabit sırayla yerleştiriliyor:
$$ (0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4). $$
Bir \(U=(U_e)_{e\in E(K_5)}\) kenar sınır vektörü için hesaplanan miktar
$$P(U)=\sum_{\substack{x_0,\dots,x_4\ge 0\\ x_u+x_v\le U_{uv}\ \forall\,0\le u<v\le 4}} 2^{x_0}3^{x_1}5^{x_2}7^{x_3}11^{x_4}\pmod{10^9+7}$$
oluyor. Son cevap ise
$$\sum_{n=0}^{99} P(a_{10n},a_{10n+1},\dots,a_{10n+9}) \pmod{10^9+7}$$
şeklinde, yine aynı kenar sırası kullanılarak elde ediliyor. Gerçek girdilerde sınırlar çok büyük olduğu için beş iç içe döngüyle doğrudan toplama yapmak mümkün değil; çözüm, eşitsizlikleri bit düzeyinde işleyen bir digit DP kuruyor.
Esas fikir şu: her kısıt \(x_u+x_v\le U_{uv}\) biçiminde. Bu tür bir eşitsizlik, ikilik tabanda yukarı doğru taşınan küçük bir artık bilgisiyle kontrol edilebilir. Bunu 10 kenarın tamamında aynı anda yaptığımızda, 5 boyutlu toplam dev bir arama olmaktan çıkıp sonlu durumlu ağırlıklı bir DP'ye dönüşüyor.
Beş değişken \(K_5\)'in köşeleri gibi düşünülüyor ve her \(\{u,v\}\) kenarı bir üst sınır \(U_{uv}\) taşıyor. Uygun bir \((x_0,\dots,x_4)\) noktası için ağırlık çarpımsal:
$$2^{x_0}3^{x_1}5^{x_2}7^{x_3}11^{x_4}=\prod_{i=0}^{4} p_i^{x_i},\qquad (p_0,p_1,p_2,p_3,p_4)=(2,3,5,7,11).$$
Dolayısıyla amaç yalnızca kaç tane çözüm olduğunu saymak değil; her çözümün bu üstel ağırlığını da toplamak.
Problem tek bir \(P(U)\) değeri istemiyor. Özyineleme 1000 sayı üretiyor ve ardışık her 10'lu blok, 10 kenarın tamamı için bir sınır kümesi oluşturuyor. Dizi üretildikten sonra bu 100 blok birbirinden bağımsız hale geliyor.
Bu yüzden matematiksel yükün tamamı tek bir genel \(P(U)\) hesabında toplanıyor. Onu çözdükten sonra Euler toplamı sadece 100 bağımsız değeri mod altında toplamak oluyor.
Bir \(e=\{u,v\}\) kenarını sabitleyelim. Her değişkeni
$$x_i=\sum_{k\ge 0} b_{i,k}2^k,\qquad b_{i,k}\in\{0,1\}$$
şeklinde ikilik açalım. Alt taraftaki \(0,1,\dots,k-1\) bitleri belirledikten sonra üst kalan parçayı
$$y_i^{(k)}=\left\lfloor \frac{x_i}{2^k}\right\rfloor$$
ile gösterelim. Bu kenar için \(c_{e,k}\) adlı negatif olmayan bir taşıma tutup
$$y_u^{(k)}+y_v^{(k)}+c_{e,k}\le \left\lfloor \frac{U_e}{2^k}\right\rfloor$$
eşitsizliğinin sağlanmasını isteriz. Buradaki taşıma, seçilmiş alt bitlerin üst bitlere zorladığı fazlalığı temsil eder. Başlangıçta bütün kenarlar için \(c_{e,0}=0\) alınır.
\(U_e\)'nin \(k\)-inci biti \(u_{e,k}\in\{0,1\}\) olsun. Ayrıca
$$y_u^{(k)}=b_{u,k}+2y_u^{(k+1)},\qquad y_v^{(k)}=b_{v,k}+2y_v^{(k+1)}$$
yazılırsa, değişmezden
$$b_{u,k}+b_{v,k}+c_{e,k}+2\bigl(y_u^{(k+1)}+y_v^{(k+1)}\bigr)\le u_{e,k}+2\left\lfloor \frac{U_e}{2^{k+1}}\right\rfloor$$
elde edilir. Bir üst seviyede aynı anlamı taşıyan en küçük yeni taşıma tam olarak
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{b_{u,k}+b_{v,k}+c_{e,k}-u_{e,k}}{2}\right\rceil\right)$$
olur. Çözümün temel reküransı budur.
Bir kenarda \(b_{u,k}+b_{v,k}\) toplamı yalnızca \(\{0,1,2\}\) içindedir. Sınır biti \(u_{e,k}\) ya 0 ya 1'dir. Giriş taşımasının da \(\{0,1,2\}\) içinde kaldığını varsayarsak
$$b_{u,k}+b_{v,k}+c_{e,k}-u_{e,k}\in\{-1,0,1,2,3,4\}$$
olur. Buradan yeni taşımanın da yine \(\{0,1,2\}\) içinde kaldığı görülür. Böylece her kenarın yalnızca üç durumu vardır ve tüm durum uzayı
$$\{0,1,2\}^{10},\qquad |\{0,1,2\}^{10}|=3^{10}=59049$$
olur.
\(k\)-inci bitte \((b_{0,k},\dots,b_{4,k})\) seçimi yapıyoruz. Bunu \(m\in\{0,1\}^5\) biçiminde 5 bitlik bir maske olarak düşünebiliriz. Bu maske, 10 kenarın her biri için uç bitlerin toplamını belirlediği için bütün yeni taşımaları da belirler.
Eğer o anda tüm kenarların taşıma vektörü \(c^{(k)}\in\{0,1,2\}^{10}\) ise, geçiş fonksiyonu kenar bazında
$$\bigl(T_k(c^{(k)},m)\bigr)_e=\max\left(0,\left\lceil \frac{s_e(m)+c^{(k)}_e-u_{e,k}}{2}\right\rceil\right)$$
şeklinde tanımlanır. Burada \(s_e(m)\), maskenin kenar \(e\) üzerinde ürettiği \(\{0,1,2\}\) değerli uç-bit toplamıdır.
\(x_i=\sum_k b_{i,k}2^k\) olduğu için ağırlık
$$\prod_{i=0}^{4} p_i^{x_i}=\prod_{k\ge 0}\prod_{i=0}^{4} p_i^{\,b_{i,k}2^k}$$
şeklinde çarpanlara ayrılır. Bu nedenle \(k\)-inci bitte seçilen maskenin katkısı
$$W_k(m)=\prod_{i=0}^{4}\left(p_i^{2^k}\right)^{b_{i,k}}\pmod{10^9+7}$$
olur. Uygulamalar her bit için 32 maske ağırlığını önceden hesaplayarak geçişleri ucuz hale getirir.
Diyelim ki belli bir kenarda giriş taşıması \(c_{e,k}=1\), sınır biti \(u_{e,k}=0\) ve o bitte seçilen uç bitler \(b_{u,k}=1\), \(b_{v,k}=0\) olsun. O zaman
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{1+0+1-0}{2}\right\rceil\right)=1$$
elde edilir; yani alttan gelen fazlalık yukarı aynen taşınır. Eğer iki uç bit de 1 olsaydı
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{1+1+1-0}{2}\right\rceil\right)=2$$
olurdu. Bu da neden taşıma değeri 2'nin gerçekten gerekli olduğunu açıkça gösterir.
Tam bir kontrol örneği olarak tüm 10 sınır 2 olduğunda digit DP
$$P(2,2,\dots,2)=7120$$
sonucunu verir ve bu değer brute force ile birebir aynıdır.
\(D_k(c)\), ilk \(k\) bit için yapılmış bütün seçimlerin toplam ağırlığı olsun; burada bu seçimlerden sonra taşıma vektörü \(c\) olsun. O zaman
$$D_{k+1}(c')=\sum_{\substack{c\in\{0,1,2\}^{10}\\ m\in\{0,1\}^5\\ T_k(c,m)=c'}} D_k(c)\,W_k(m)\pmod{10^9+7}$$
reküransı geçerlidir. Başlangıç koşulu \(D_0(\mathbf 0)=1\), diğer tüm durumlar için \(D_0(c)=0\)'dır.
Uygulamalar 31 bit seviyesi işler. Bunun nedeni, özyinelemeden gelen tüm sınırların \(10^9+7<2^{30}\) olması ve en sonda fazladan bir sıfır bit işleyerek kalan taşımanın temizlenebilmesidir. Son turdan sonra bütün kenar taşıma değerleri 0 ise ve ancak o zaman 5'li seçim gerçekten uygundur. Dolayısıyla
$$P(U)=D_{31}(\mathbf 0)$$
olur.
C++, Python ve Java uygulamaları aynı matematiksel tabloları kullanır. Önce 1000 terimli dizi üretilir, sonra \(3^{10}\) durumun her biri 10 tane üçlü basamağa ayrıştırılır, 32 maskenin her birinin 10 kenarda oluşturduğu uç-bit toplamları çıkarılır ve 31 bit düzeyi için 32 geçiş ağırlığı önceden hesaplanır.
Python sürümü, derlenmiş çözücüyü çağıran ince bir kabuktur; ağır hesap aynı taşıma tabanlı digit DP'dir. Java sürümü ise aynı bit geçişlerini doğrudan kendi içinde uygular.
Sabit bir \(U\) verildiğinde önce 10 sınırın 31 bit sütunu çıkarılır. Ardından iki katmanlı kayan bir DP yürütülür: mevcut katmanda \(D_k(c)\), sonraki katmanda \(D_{k+1}(c')\) tutulur. Başlangıç durumu tüm kenarlarda sıfır taşımadır ve her adımda 32 maskenin tamamı denenir.
Pratik hız için yalnızca aktif durumlar dolaşılır; yani mevcut DP değeri sıfır olmayan durumlar. Teorik olarak 59049 durum vardır ama birçok katmanda bunların ancak bir kısmı erişilebilir.
Başvuru niteliğindeki uygulama, küçük örneklerde DP sonucunu brute force ile karşılaştırır. Özellikle \(P(2,\dots,2)=7120\) ve \(P(1,2,\dots,10)=799809376\) değerleri doğrulanır; ayrıca rastgele küçük sınırlarla da test yapılır. Böylece taşıma reküransının özgün 5 boyutlu toplamı tam olarak verdiği kontrol edilir.
Daha sonra 100 problem örneği bağımsızdır: her \(n\) için \((a_{10n},\dots,a_{10n+9})\) bloğu alınır, \(P(U)\) hesaplanır ve toplam mod altında güncellenir. Derlenmiş uygulamalar bu dış döngüyü paralelleştirir.
Tek bir sınır vektörü için en kötü durumdaki maliyet
$$O\!\left(31\cdot 3^{10}\cdot 2^5\cdot 10\right)$$
şeklindedir. Çünkü 31 bit seviyesi vardır, en fazla \(3^{10}\) taşıma durumu bulunur, her durumda 32 maske denenir ve her geçişte 10 kenar güncellenir. Aktif durum optimizasyonu nedeniyle gerçek çalışma süresi genellikle bundan küçüktür.
Bellek kullanımı iki DP katmanı için \(O(3^{10})\), ayrıca durum, maske ve ağırlık tabloları kadardır. Dıştaki 100 örnek toplam işi 100 ile çarpar ama bunlar birbirinden bağımsız olduğu için paralelleştirmeye çok uygundur.
Naif brute-force yaklaşımı, sınırlar \(10^9\) mertebesindeyken beş iç içe döngü gerektirirdi ve tamamen kullanışsız olurdu. Digit DP'nin başarısı, dev aralıkları kenar başına yalnızca \(\{0,1,2\}\) kümesine indirmesinden gelir.
Para cada \(n=0,1,\dots,99\), el problema genera primero un bloque de 10 cotas mediante la recurrencia
$$a_0=1,\qquad a_1=7,\qquad a_m \equiv 7a_{m-1}+a_{m-2}^2 \pmod{10^9+7}.$$
El bloque \((a_{10n},a_{10n+1},\dots,a_{10n+9})\) se asigna a las 10 aristas del grafo completo \(K_5\) en el orden fijo
$$ (0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4). $$
Para un vector de cotas \(U=(U_e)_{e\in E(K_5)}\), hay que evaluar
$$P(U)=\sum_{\substack{x_0,\dots,x_4\ge 0\\ x_u+x_v\le U_{uv}\ \forall\,0\le u<v\le 4}} 2^{x_0}3^{x_1}5^{x_2}7^{x_3}11^{x_4}\pmod{10^9+7}.$$
La respuesta final es
$$\sum_{n=0}^{99} P(a_{10n},a_{10n+1},\dots,a_{10n+9}) \pmod{10^9+7},$$
leyendo siempre las diez entradas en ese mismo orden de aristas. Un barrido directo con cinco bucles solo sirve para casos diminutos; con cotas reales tan grandes, la solución útil tiene que trabajar bit a bit.
La observación decisiva es que todas las restricciones son del tipo \(x_u+x_v\le U_{uv}\). En base 2, una desigualdad así se controla localmente: en cada bit solo importan los dos bits elegidos, el bit correspondiente de la cota y un pequeño valor de acarreo. Aplicando esa idea a las 10 aristas a la vez, la suma 5D se convierte en una DP ponderada de estados finitos.
Las cinco variables se interpretan como los vértices de \(K_5\), y cada arista \(\{u,v\}\) aporta una cota superior \(U_{uv}\). El peso de un punto factible \((x_0,\dots,x_4)\) es multiplicativo:
$$2^{x_0}3^{x_1}5^{x_2}7^{x_3}11^{x_4}=\prod_{i=0}^{4} p_i^{x_i},\qquad (p_0,p_1,p_2,p_3,p_4)=(2,3,5,7,11).$$
Por eso no basta con contar soluciones: hay que sumar una contribución geométrica distinta para cada 5-tupla admisible.
El problema exterior no pide una sola evaluación de \(P(U)\), sino 100. La recurrencia produce 1000 términos y cada bloque consecutivo de 10 se usa como conjunto completo de cotas. Una vez generada la sucesión, esos 100 bloques son independientes entre sí.
Eso concentra toda la dificultad matemática en entender cómo calcular una sola vez \(P(U)\). Después, la respuesta total se obtiene sumando 100 evaluaciones del mismo mecanismo.
Fijemos una arista \(e=\{u,v\}\). Escribimos
$$x_i=\sum_{k\ge 0} b_{i,k}2^k,\qquad b_{i,k}\in\{0,1\}.$$
Después de decidir los bits \(0,1,\dots,k-1\), definimos las partes altas restantes
$$y_i^{(k)}=\left\lfloor \frac{x_i}{2^k}\right\rfloor.$$
Para esa arista guardamos un entero no negativo \(c_{e,k}\) tal que las partes aún no procesadas tengan que satisfacer
$$y_u^{(k)}+y_v^{(k)}+c_{e,k}\le \left\lfloor \frac{U_e}{2^k}\right\rfloor.$$
Ese acarreo representa el exceso que los bits bajos ya fijados obligan a compensar en niveles superiores. Inicialmente vale \(c_{e,0}=0\).
Sea \(u_{e,k}\in\{0,1\}\) el bit \(k\)-ésimo de \(U_e\). Como
$$y_u^{(k)}=b_{u,k}+2y_u^{(k+1)},\qquad y_v^{(k)}=b_{v,k}+2y_v^{(k+1)},$$
la desigualdad anterior se transforma en
$$b_{u,k}+b_{v,k}+c_{e,k}+2\bigl(y_u^{(k+1)}+y_v^{(k+1)}\bigr)\le u_{e,k}+2\left\lfloor \frac{U_e}{2^{k+1}}\right\rfloor.$$
El menor acarreo que transmite exactamente la misma información al siguiente nivel es
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{b_{u,k}+b_{v,k}+c_{e,k}-u_{e,k}}{2}\right\rceil\right).$$
Esa es la recurrencia central de toda la solución.
En una arista, la suma \(b_{u,k}+b_{v,k}\) solo puede ser \(0,1\) o \(2\). El bit de la cota es \(0\) o \(1\), y si el acarreo de entrada ya está en \(\{0,1,2\}\), entonces
$$b_{u,k}+b_{v,k}+c_{e,k}-u_{e,k}\in\{-1,0,1,2,3,4\}.$$
La fórmula de transición devuelve de nuevo un valor en \(\{0,1,2\}\). Así, cada arista tiene exactamente tres estados posibles y el espacio total es
$$\{0,1,2\}^{10},\qquad |\{0,1,2\}^{10}|=3^{10}=59049.$$
En el bit \(k\) se eligen los cinco bits \((b_{0,k},\dots,b_{4,k})\). Conviene verlos como una máscara \(m\in\{0,1\}^5\). Esa máscara fija automáticamente las sumas de bits en las 10 aristas y, por tanto, fija también el siguiente vector de acarreos.
Si el estado actual es \(c^{(k)}\in\{0,1,2\}^{10}\), la transición viene dada por
$$\bigl(T_k(c^{(k)},m)\bigr)_e=\max\left(0,\left\lceil \frac{s_e(m)+c^{(k)}_e-u_{e,k}}{2}\right\rceil\right),$$
donde \(s_e(m)\in\{0,1,2\}\) es la suma de bits de los dos extremos de la arista \(e\) inducida por la máscara.
Como \(x_i=\sum_k b_{i,k}2^k\), el peso se factoriza así:
$$\prod_{i=0}^{4} p_i^{x_i}=\prod_{k\ge 0}\prod_{i=0}^{4} p_i^{\,b_{i,k}2^k}.$$
Por lo tanto, la máscara \(m\) elegida en el bit \(k\) aporta el factor
$$W_k(m)=\prod_{i=0}^{4}\left(p_i^{2^k}\right)^{b_{i,k}}\pmod{10^9+7}.$$
Eso explica por qué las implementaciones precomputan los 32 pesos de máscara para cada nivel binario.
Supongamos que, en una arista concreta, el acarreo de entrada es \(c_{e,k}=1\), el bit de la cota es \(u_{e,k}=0\) y la máscara elige \(b_{u,k}=1\), \(b_{v,k}=0\). Entonces
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{1+0+1-0}{2}\right\rceil\right)=1.$$
El exceso no desaparece: sigue habiendo una unidad que debe transmitirse al siguiente nivel. Si ambos bits fueran 1, obtendríamos
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{1+1+1-0}{2}\right\rceil\right)=2,$$
y eso muestra por qué el valor 2 es realmente necesario en el espacio de estados.
Como control completo, cuando las 10 cotas son iguales a 2 se obtiene
$$P(2,2,\dots,2)=7120,$$
exactamente el mismo valor que produce la enumeración exhaustiva.
Sea \(D_k(c)\) el peso total de todas las asignaciones a los primeros \(k\) bits cuyo vector de acarreos después de esos bits es \(c\). Entonces
$$D_{k+1}(c')=\sum_{\substack{c\in\{0,1,2\}^{10}\\ m\in\{0,1\}^5\\ T_k(c,m)=c'}} D_k(c)\,W_k(m)\pmod{10^9+7},$$
con condición inicial \(D_0(\mathbf 0)=1\) y \(D_0(c)=0\) para \(c\ne \mathbf 0\).
Las implementaciones procesan 31 posiciones binarias. Eso basta porque todas las cotas generadas por la recurrencia son menores que \(10^9+7<2^{30}\), y una ronda adicional con bit cero permite vaciar cualquier acarreo residual. La 5-tupla es válida exactamente cuando el estado final es el vector nulo, así que
$$P(U)=D_{31}(\mathbf 0).$$
Las implementaciones en C++, Python y Java se apoyan en la misma estructura matemática. Primero generan los 1000 términos de la recurrencia, después descodifican cada uno de los \(3^{10}\) estados en sus 10 dígitos ternarios de acarreo, construyen para las 32 máscaras las sumas de bits en las 10 aristas y precalculan los 32 factores de peso para cada una de las 31 posiciones de bit.
La versión en Python es un punto de entrada ligero que delega el cálculo pesado en el solucionador compilado, mientras que Java implementa directamente la misma DP por bits y el mismo esquema de transiciones.
Dado un \(U\) fijo, la implementación extrae primero las 31 columnas binarias de las 10 cotas. Luego ejecuta una DP con dos capas rodantes: una capa almacena \(D_k(c)\) y la otra acumula \(D_{k+1}(c')\). El proceso arranca en el vector de acarreos todo cero y prueba las 32 máscaras en cada paso.
Para acelerar la práctica, solo se recorren los estados activos, es decir, aquellos cuyo valor actual en la DP no es cero. El peor caso sigue teniendo 59049 estados, pero muchas capas son bastante más dispersas.
La implementación de referencia contrasta la DP con fuerza bruta en casos pequeños. En particular, verifica \(P(2,\dots,2)=7120\), \(P(1,2,\dots,10)=799809376\) y varios ejemplos aleatorios de tamaño pequeño. Así se confirma que la recurrencia de acarreos reproduce exactamente la suma original de cinco variables.
Después, las 100 instancias del problema son independientes: para cada \(n\) se toma el bloque \((a_{10n},\dots,a_{10n+9})\), se evalúa \(P(U)\) y se añade al total módulo \(10^9+7\). Las implementaciones compiladas paralelizan precisamente esa capa exterior.
Para un solo vector de cotas, el coste máximo es
$$O\!\left(31\cdot 3^{10}\cdot 2^5\cdot 10\right),$$
porque hay 31 niveles de bits, hasta \(3^{10}\) estados de acarreo, 32 máscaras por estado y 10 aristas que actualizar en cada transición. En la práctica suele ser menor gracias al tratamiento disperso de estados activos.
La memoria es \(O(3^{10})\) para las dos capas de la DP, además de las tablas precomputadas de estados, máscaras y pesos. La suma exterior sobre 100 instancias multiplica el trabajo total por 100, aunque esas 100 evaluaciones son totalmente independientes.
Un método ingenuo con cinco bucles anidados tendría que recorrer rangos cercanos a \(10^9\) y sería inviable. La ganancia esencial de la digit DP es reemplazar esos rangos gigantes por el alfabeto diminuto \(\{0,1,2\}\) en cada arista.
对每个 \(n=0,1,\dots,99\)，题目先用递推式
$$a_0=1,\qquad a_1=7,\qquad a_m \equiv 7a_{m-1}+a_{m-2}^2 \pmod{10^9+7}$$
生成一段长度为 10 的上界数据。区块 \((a_{10n},a_{10n+1},\dots,a_{10n+9})\) 按固定顺序
$$ (0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4) $$
对应到完全图 \(K_5\) 的 10 条边。对某个边界向量 \(U=(U_e)_{e\in E(K_5)}\)，需要计算
$$P(U)=\sum_{\substack{x_0,\dots,x_4\ge 0\\ x_u+x_v\le U_{uv}\ \forall\,0\le u<v\le 4}} 2^{x_0}3^{x_1}5^{x_2}7^{x_3}11^{x_4}\pmod{10^9+7}.$$
最终答案是
$$\sum_{n=0}^{99} P(a_{10n},a_{10n+1},\dots,a_{10n+9}) \pmod{10^9+7},$$
其中 10 个数始终按上面的边顺序解释。真正困难的地方不在于外层有 100 组数据，而在于单个 \(P(U)\) 本身是一个带 10 个两两约束的五维加权求和。若直接枚举 \(x_0,\dots,x_4\)，面对接近 \(10^9\) 的上界几乎没有任何可能性，因此必须把约束改写成逐二进制位处理的动态规划。
核心观察是：每条约束都只有 \(x_u+x_v\le U_{uv}\) 这一种形式。把变量写成二进制后，这类不等式可以在每一位上局部维护，只需要知道当前这两个点取了哪个 bit、上界在该位是什么、以及从更低位传上来的一个很小的“进位/欠账”值。对 10 条边同时这样做，原来的五维求和就变成了一个有限状态的加权 digit DP。
五个变量可以看成 \(K_5\) 的五个顶点，每条边 \(\{u,v\}\) 都带着一个上界 \(U_{uv}\)。可行点 \((x_0,\dots,x_4)\) 的权重不是 1，而是
$$2^{x_0}3^{x_1}5^{x_2}7^{x_3}11^{x_4}=\prod_{i=0}^{4} p_i^{x_i},\qquad (p_0,p_1,p_2,p_3,p_4)=(2,3,5,7,11).$$
因此这不是普通的计数问题，而是对所有满足约束的五元组做一次几何级数式的加权求和。
整个 Euler 题目并不是求一个 \(P(U)\)，而是先生成 1000 个数，再把它们切成 100 个长度为 10 的区块。每个区块都给出一整套 10 条边界。也就是说，难点完全浓缩在“怎样高效求一个 \(P(U)\)”这件事上；一旦这个子问题解决，最外层只剩下 100 次独立调用再求和。
这种结构也解释了为什么编译版实现会并行化外层循环：因为不同区块之间没有任何状态共享。
固定一条边 \(e=\{u,v\}\)。把每个变量写成
$$x_i=\sum_{k\ge 0} b_{i,k}2^k,\qquad b_{i,k}\in\{0,1\}.$$
当低位 \(0,1,\dots,k-1\) 已经决定之后，定义剩余高位部分
$$y_i^{(k)}=\left\lfloor \frac{x_i}{2^k}\right\rfloor.$$
对边 \(e\) 维护一个非负整数 \(c_{e,k}\)，含义是：尚未处理的高位必须满足
$$y_u^{(k)}+y_v^{(k)}+c_{e,k}\le \left\lfloor \frac{U_e}{2^k}\right\rfloor.$$
这里的 \(c_{e,k}\) 表示低位已经产生了多少“超额”，这些超额必须由更高位去吸收。开始时还没有处理任何位，所以所有边都从 \(c_{e,0}=0\) 出发。
记 \(u_{e,k}\in\{0,1\}\) 为 \(U_e\) 的第 \(k\) 个二进制位。又因为
$$y_u^{(k)}=b_{u,k}+2y_u^{(k+1)},\qquad y_v^{(k)}=b_{v,k}+2y_v^{(k+1)},$$
把它们代回不变量，得到
$$b_{u,k}+b_{v,k}+c_{e,k}+2\bigl(y_u^{(k+1)}+y_v^{(k+1)}\bigr)\le u_{e,k}+2\left\lfloor \frac{U_e}{2^{k+1}}\right\rfloor.$$
要让同样的意义在下一层继续成立，需要选择最小的新的进位值，于是得到
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{b_{u,k}+b_{v,k}+c_{e,k}-u_{e,k}}{2}\right\rceil\right).$$
这就是整个算法真正的核心递推式。它把一个看似全局的不等式，压缩成了单条边上的局部更新。
在一条边上，端点 bit 之和 \(b_{u,k}+b_{v,k}\) 只能是 \(0,1,2\)，上界 bit \(u_{e,k}\) 只能是 \(0\) 或 \(1\)。如果归纳地假设输入进位已经在 \(\{0,1,2\}\) 中，那么
$$b_{u,k}+b_{v,k}+c_{e,k}-u_{e,k}\in\{-1,0,1,2,3,4\}.$$
带入上式后，新的进位仍然只能是 \(0,1,2\)。所以单条边的状态空间只有 3 个值，而 10 条边合起来的总状态数为
$$\{0,1,2\}^{10},\qquad |\{0,1,2\}^{10}|=3^{10}=59049.$$
在 bit \(k\) 上，我们其实只是在选择 \((b_{0,k},\dots,b_{4,k})\) 这 5 个 0 或 1，可以把它看成一个 5 位掩码 \(m\in\{0,1\}^5\)。一旦掩码确定，每条边两个端点的 bit 和也就确定了，因此所有边的新进位都被同时确定。
如果第 \(k\) 层的进位向量是 \(c^{(k)}\in\{0,1,2\}^{10}\)，那么转移函数可写成
$$\bigl(T_k(c^{(k)},m)\bigr)_e=\max\left(0,\left\lceil \frac{s_e(m)+c^{(k)}_e-u_{e,k}}{2}\right\rceil\right),$$
其中 \(s_e(m)\in\{0,1,2\}\) 表示掩码在边 \(e\) 上产生的两端 bit 之和。
因为 \(x_i=\sum_k b_{i,k}2^k\)，所以权重自然分解为
$$\prod_{i=0}^{4} p_i^{x_i}=\prod_{k\ge 0}\prod_{i=0}^{4} p_i^{\,b_{i,k}2^k}.$$
因此在第 \(k\) 位选择掩码 \(m\) 时，只会引入一个局部乘子
$$W_k(m)=\prod_{i=0}^{4}\left(p_i^{2^k}\right)^{b_{i,k}}\pmod{10^9+7}.$$
这一步说明为什么实现会预先把每一位的 32 个掩码权重全部算好：之后的 DP 转移只需查表乘一下即可。
假设某条边当前的输入进位是 \(c_{e,k}=1\)，这一位的上界 bit 是 \(u_{e,k}=0\)，而掩码在这条边两端选择了 \(b_{u,k}=1\)、\(b_{v,k}=0\)。那么
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{1+0+1-0}{2}\right\rceil\right)=1.$$
也就是说，低位累积出来的超额并没有消失，而是继续向更高一位传递。如果两端都选 1，则
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{1+1+1-0}{2}\right\rceil\right)=2,$$
这正好说明状态值 2 不是多余设计，而是真会出现。
作为完整实例的检验，当 10 个上界全都等于 2 时，digit DP 得到
$$P(2,2,\dots,2)=7120,$$
与暴力枚举完全一致。
定义 \(D_k(c)\) 为：前 \(k\) 个二进制位已经决定后，进位向量等于 \(c\) 的所有方案权重总和。那么有
$$D_{k+1}(c')=\sum_{\substack{c\in\{0,1,2\}^{10}\\ m\in\{0,1\}^5\\ T_k(c,m)=c'}} D_k(c)\,W_k(m)\pmod{10^9+7},$$
初始条件是 \(D_0(\mathbf 0)=1\)，其余状态都为 0。
实现一共处理 31 个 bit 层次。这是足够的，因为递推生成的所有上界都满足 \(U_e<10^9+7<2^{30}\)，再多做一轮全 0 的最高位就能把任何残余进位彻底暴露出来。最后只有当所有边的进位都回到 0 时，该五元组才真正满足全部不等式，因此
$$P(U)=D_{31}(\mathbf 0).$$
C++、Python 和 Java 三个实现使用的是同一套数学结构。它们会先生成 1000 项递推数列，再把全部 \(3^{10}\) 个状态拆成 10 位三进制进位，预先计算 32 个掩码在 10 条边上的端点 bit 和，并为 31 个 bit 位置准备好对应的 32 个权重乘子。
其中 Python 版本并不是单独再写一份纯 Python digit DP，而是作为轻量入口去调用编译后的求解器；Java 版本则直接实现了相同的状态转移和外层求和。
给定某个边界向量 \(U\) 后，程序先提取 10 个上界的 31 列二进制位，然后用两个滚动数组做 DP：当前层表示 \(D_k(c)\)，下一层累加 \(D_{k+1}(c')\)。起点永远是全零进位状态，每一层对 32 个掩码全部尝试。
实际运行时只遍历“活跃状态”，也就是当前 DP 值非零的状态。虽然理论上总状态数是 59049，但很多层只会访问其中一部分，因此速度会明显好于密集枚举。
参考实现会在小规模数据上用暴力枚举校验 digit DP，具体包括 \(P(2,\dots,2)=7120\)、\(P(1,2,\dots,10)=799809376\) 以及若干随机小样例。这样就能确认进位递推没有丢失任何原始约束信息。
之后的最外层部分非常直接：对每个 \(n\)，取出 \((a_{10n},\dots,a_{10n+9})\) 这一组 10 个上界，求出对应的 \(P(U)\)，再把 100 个结果在模 \(10^9+7\) 下相加。编译版实现会把这 100 个独立任务分配到多个工作线程上。
对于单个边界向量，最坏情况下的时间复杂度为
$$O\!\left(31\cdot 3^{10}\cdot 2^5\cdot 10\right),$$
因为共有 31 层 bit，最多 \(3^{10}\) 个进位状态，每个状态尝试 32 个掩码，每次转移还要更新 10 条边。由于实现只扫描活跃状态，实际耗时通常比这个上界更低。
空间复杂度是 \(O(3^{10})\)，主要来自两层滚动 DP，再加上一些预处理表。外层 100 个实例会把总工作量乘以 100，但这些实例彼此独立，因此非常适合并行。
如果采用朴素的五重循环，就必须在接近 \(10^9\) 的范围上枚举变量，根本不可行。digit DP 之所以有效，正是因为它把巨大的数值空间压缩成了每条边仅有 \(\{0,1,2\}\) 三种进位状态。
Для каждого \(n=0,1,\dots,99\) задача сначала строит блок из 10 ограничений по рекуррентной формуле
$$a_0=1,\qquad a_1=7,\qquad a_m \equiv 7a_{m-1}+a_{m-2}^2 \pmod{10^9+7}.$$
Набор \((a_{10n},a_{10n+1},\dots,a_{10n+9})\) прикрепляется к 10 рёбрам полного графа \(K_5\) в фиксированном порядке
$$ (0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4). $$
Для такого вектора границ \(U=(U_e)_{e\in E(K_5)}\) нужно вычислить
$$P(U)=\sum_{\substack{x_0,\dots,x_4\ge 0\\ x_u+x_v\le U_{uv}\ \forall\,0\le u<v\le 4}} 2^{x_0}3^{x_1}5^{x_2}7^{x_3}11^{x_4}\pmod{10^9+7}.$$
Искомый результат равен
$$\sum_{n=0}^{99} P(a_{10n},a_{10n+1},\dots,a_{10n+9}) \pmod{10^9+7},$$
где десять чисел каждый раз читаются в одном и том же порядке рёбер. Прямой перебор по пяти переменным пригоден только для игрушечных примеров; для реальных ограничений требуется двоичная DP по разрядам.
Ключевое наблюдение состоит в том, что каждое ограничение имеет вид \(x_u+x_v\le U_{uv}\). В двоичной записи такую проверку можно выполнять локально: на каждом разряде нужны лишь два выбранных бита, бит соответствующей границы и маленькое значение переноса. Если делать это одновременно на всех 10 рёбрах, исходная 5D-сумма превращается в конечную взвешенную динамику по состояниям.
Пять переменных играют роль вершин \(K_5\), а каждое ребро \(\{u,v\}\) несёт верхнюю границу \(U_{uv}\). Вес допустимой точки \((x_0,\dots,x_4)\) равен
$$2^{x_0}3^{x_1}5^{x_2}7^{x_3}11^{x_4}=\prod_{i=0}^{4} p_i^{x_i},\qquad (p_0,p_1,p_2,p_3,p_4)=(2,3,5,7,11).$$
Значит, нужно не просто посчитать количество допустимых 5-кортежей, а просуммировать по ним геометрические веса.
Внешняя часть задачи требует не одного значения \(P(U)\), а ста. Рекурсия порождает 1000 чисел, после чего каждые подряд идущие 10 чисел образуют полный набор ограничений для одного экземпляра. После построения последовательности эти 100 блоков полностью независимы.
Поэтому вся содержательная математика сосредоточена в вычислении одного типового \(P(U)\). Общий ответ затем получается простым суммированием 100 независимых результатов.
Зафиксируем ребро \(e=\{u,v\}\). Запишем
$$x_i=\sum_{k\ge 0} b_{i,k}2^k,\qquad b_{i,k}\in\{0,1\}.$$
После того как биты \(0,1,\dots,k-1\) уже выбраны, введём оставшиеся старшие части
$$y_i^{(k)}=\left\lfloor \frac{x_i}{2^k}\right\rfloor.$$
Для ребра \(e\) храним неотрицательное число \(c_{e,k}\) со смыслом
$$y_u^{(k)}+y_v^{(k)}+c_{e,k}\le \left\lfloor \frac{U_e}{2^k}\right\rfloor.$$
Этот перенос показывает, какой избыток уже создан младшими битами и должен быть погашен на более высоких разрядах. В начале обработки \(c_{e,0}=0\) для всех рёбер.
Пусть \(u_{e,k}\in\{0,1\}\) обозначает \(k\)-й бит числа \(U_e\). Так как
$$y_u^{(k)}=b_{u,k}+2y_u^{(k+1)},\qquad y_v^{(k)}=b_{v,k}+2y_v^{(k+1)},$$
подстановка в инвариант даёт
$$b_{u,k}+b_{v,k}+c_{e,k}+2\bigl(y_u^{(k+1)}+y_v^{(k+1)}\bigr)\le u_{e,k}+2\left\lfloor \frac{U_e}{2^{k+1}}\right\rfloor.$$
Минимальный перенос, который передаёт ту же информацию на следующий уровень, равен
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{b_{u,k}+b_{v,k}+c_{e,k}-u_{e,k}}{2}\right\rceil\right).$$
Это и есть главная рекуррентная формула решения.
На одном ребре сумма битов концов \(b_{u,k}+b_{v,k}\) принимает только значения \(0,1,2\), бит ограничения \(u_{e,k}\) равен \(0\) или \(1\), а если входной перенос уже лежит в \(\{0,1,2\}\), то
$$b_{u,k}+b_{v,k}+c_{e,k}-u_{e,k}\in\{-1,0,1,2,3,4\}.$$
Следовательно, и следующий перенос снова принадлежит \(\{0,1,2\}\). Поэтому для одной грани есть лишь три состояния, а полный набор состояний имеет размер
$$\{0,1,2\}^{10},\qquad |\{0,1,2\}^{10}|=3^{10}=59049.$$
На разряде \(k\) выбираются пять битов \((b_{0,k},\dots,b_{4,k})\). Удобно рассматривать их как маску \(m\in\{0,1\}^5\). Эта маска мгновенно задаёт суммы битов на всех 10 рёбрах, а значит, и следующий вектор переносов.
Если текущий вектор переносов равен \(c^{(k)}\in\{0,1,2\}^{10}\), то переход определяется покомпонентно формулой
$$\bigl(T_k(c^{(k)},m)\bigr)_e=\max\left(0,\left\lceil \frac{s_e(m)+c^{(k)}_e-u_{e,k}}{2}\right\rceil\right),$$
где \(s_e(m)\in\{0,1,2\}\) обозначает сумму битов на ребре \(e\), задаваемую маской.
Так как \(x_i=\sum_k b_{i,k}2^k\), можно записать
$$\prod_{i=0}^{4} p_i^{x_i}=\prod_{k\ge 0}\prod_{i=0}^{4} p_i^{\,b_{i,k}2^k}.$$
Значит, выбор маски \(m\) на разряде \(k\) даёт локальный множитель
$$W_k(m)=\prod_{i=0}^{4}\left(p_i^{2^k}\right)^{b_{i,k}}\pmod{10^9+7}.$$
Именно поэтому реализации заранее вычисляют 32 веса масок для каждого разряда.
Пусть на некотором ребре входной перенос равен \(c_{e,k}=1\), текущий бит ограничения равен \(u_{e,k}=0\), а маска выбирает \(b_{u,k}=1\) и \(b_{v,k}=0\). Тогда
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{1+0+1-0}{2}\right\rceil\right)=1.$$
То есть младшие биты создали избыток, который и дальше обязан компенсироваться старшими разрядами. Если оба бита концов равны 1, получится
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{1+1+1-0}{2}\right\rceil\right)=2,$$
и это наглядно показывает, почему значение 2 действительно необходимо.
В качестве полного контрольного примера, при всех десяти ограничениях, равных 2, получаем
$$P(2,2,\dots,2)=7120,$$
в точном совпадении с полным перебором.
Пусть \(D_k(c)\) обозначает суммарный вес всех назначений первых \(k\) битов, для которых после этих битов вектор переносов равен \(c\). Тогда выполняется
$$D_{k+1}(c')=\sum_{\substack{c\in\{0,1,2\}^{10}\\ m\in\{0,1\}^5\\ T_k(c,m)=c'}} D_k(c)\,W_k(m)\pmod{10^9+7},$$
а начальное условие имеет вид \(D_0(\mathbf 0)=1\), \(D_0(c)=0\) при \(c\ne \mathbf 0\).
Реализации обрабатывают 31 двоичный разряд. Этого достаточно, потому что все ограничения из рекурсии удовлетворяют \(U_e<10^9+7<2^{30}\), а дополнительный нулевой разряд в конце гарантированно выталкивает любой остаточный перенос. Следовательно, допустимыми остаются ровно те наборы, для которых после последнего шага все переносы равны нулю, то есть
$$P(U)=D_{31}(\mathbf 0).$$
Реализации на C++, Python и Java опираются на одну и ту же математическую схему. Сначала строится 1000-членная рекуррентная последовательность, затем каждый из \(3^{10}\) состояний раскладывается на 10 троичных цифр переноса, для всех 32 масок вычисляются суммы битов на 10 рёбрах, и для каждого из 31 разрядов заранее считаются 32 весовых множителя.
Python-версия служит лёгкой оболочкой вокруг скомпилированного решателя, поэтому вся тяжёлая арифметика выполняется тем же самым digit DP. Java-реализация воспроизводит те же переходы напрямую.
Для фиксированного \(U\) код сначала извлекает 31 битовую колонку из 10 ограничений. Затем запускается DP на двух перекатывающихся слоях: один слой хранит значения \(D_k(c)\), другой накапливает \(D_{k+1}(c')\). Старт всегда происходит из нулевого вектора переносов, а на каждом шаге перебираются все 32 маски.
На практике просматриваются только активные состояния, то есть состояния с ненулевым текущим DP-значением. Теоретический максимум по-прежнему равен 59049 состояниям, но реально достижимых состояний на многих уровнях заметно меньше.
Эталонная реализация сравнивает DP с полным перебором на маленьких данных. В частности, проверяются точные значения \(P(2,\dots,2)=7120\), \(P(1,2,\dots,10)=799809376\), а также несколько случайных малых наборов ограничений. Это подтверждает, что рекурсия по переносам полностью эквивалентна исходной 5D-сумме.
После этого внешняя часть тривиальна: для каждого \(n\) берётся блок \((a_{10n},\dots,a_{10n+9})\), вычисляется соответствующее \(P(U)\), и все 100 результатов суммируются по модулю \(10^9+7\). Скомпилированные реализации распараллеливают именно этот внешний уровень.
Для одного вектора ограничений верхняя оценка времени равна
$$O\!\left(31\cdot 3^{10}\cdot 2^5\cdot 10\right),$$
потому что есть 31 разряд, до \(3^{10}\) состояний переноса, 32 маски на состояние и 10 рёбер, обновляемых в каждом переходе. Благодаря хранению только активных состояний фактическое время обычно меньше этой грубой оценки.
Память составляет \(O(3^{10})\) для двух слоёв DP плюс таблицы предварительных вычислений. Внешняя сумма по 100 экземплярам просто умножает общий объём работы на 100, но не меняет внутренней структуры алгоритма.
Наивный подход с пятью вложенными циклами потребовал бы перебирать диапазоны порядка \(10^9\), что абсолютно нереалистично. Эффективность digit DP обеспечивается тем, что огромные числовые диапазоны заменяются крошечным алфавитом переносов \(\{0,1,2\}\) на каждом ребре.
لكل \(n=0,1,\dots,99\) تبني المسألة أولًا كتلة من 10 حدود عليا باستخدام العلاقة التراجعية
$$a_0=1,\qquad a_1=7,\qquad a_m \equiv 7a_{m-1}+a_{m-2}^2 \pmod{10^9+7}.$$
ثم تُسنَد الكتلة \((a_{10n},a_{10n+1},\dots,a_{10n+9})\) إلى أضلاع الرسم الكامل \(K_5\) وفق الترتيب الثابت
$$ (0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4). $$
ولمتجه حدود \(U=(U_e)_{e\in E(K_5)}\) نحسب
$$P(U)=\sum_{\substack{x_0,\dots,x_4\ge 0\\ x_u+x_v\le U_{uv}\ \forall\,0\le u<v\le 4}} 2^{x_0}3^{x_1}5^{x_2}7^{x_3}11^{x_4}\pmod{10^9+7}.$$
أما الجواب النهائي فهو
$$\sum_{n=0}^{99} P(a_{10n},a_{10n+1},\dots,a_{10n+9}) \pmod{10^9+7},$$
مع تفسير العناصر العشرة دائمًا وفق ترتيب الأضلاع نفسه. التعداد المباشر بخمسة متغيرات لا يصلح إلا لحالات صغيرة جدًا؛ أمّا في الحالة الحقيقية فالقيم كبيرة، ولذلك تُعاد صياغة القيود على مستوى البتات باستعمال برمجة ديناميكية مع حالات حمل.
الفكرة الحاسمة هي أن كل قيد له الصورة \(x_u+x_v\le U_{uv}\). وعندما نكتب الأعداد بالثنائي يمكن التعامل مع هذا النوع من المتراجحات محليًا: في كل بت يكفي معرفة بتّي الطرفين، وبتّ الحد الأعلى الموافق، وقيمة حمل صغيرة قادمة من البتات الأدنى. وعند تنفيذ هذا بالتوازي على الأضلاع العشرة كلها تتحول المسألة من مجموع خماسي الأبعاد إلى digit DP محدود الحالات وموزون.
تمثل المتغيرات الخمسة رؤوس \(K_5\)، وكل ضلع \(\{u,v\}\) يحمل حدًا أعلى \(U_{uv}\). ووزن النقطة المسموح بها \((x_0,\dots,x_4)\) هو
$$2^{x_0}3^{x_1}5^{x_2}7^{x_3}11^{x_4}=\prod_{i=0}^{4} p_i^{x_i},\qquad (p_0,p_1,p_2,p_3,p_4)=(2,3,5,7,11).$$
إذن المطلوب ليس مجرد عدّ الحلول، بل جمع أوزان أسية مختلفة فوق جميع الخماسيات التي تحقق القيود.
الجزء الخارجي من المسألة لا يطلب قيمة واحدة من \(P(U)\)، بل 100 قيمة. فالعلاقة التراجعية تولد 1000 حد، ثم تُقسَّم إلى 100 كتل متتالية طول كل منها 10. وكل كتلة تعطي مجموعة كاملة من حدود الأضلاع. بعد تكوين المتتالية تصبح هذه الكتل مستقلة عن بعضها بعضًا.
لهذا يتركز جوهر البرهان كله في حساب \(P(U)\) لحالة عامة واحدة. وبعد ذلك يصبح جواب Euler مجرد جمع 100 نتيجة من النوع نفسه.
لنثبت ضلعًا واحدًا \(e=\{u,v\}\). نكتب
$$x_i=\sum_{k\ge 0} b_{i,k}2^k,\qquad b_{i,k}\in\{0,1\}.$$
وبعد حسم البتات \(0,1,\dots,k-1\) نعرّف الأجزاء العليا المتبقية
$$y_i^{(k)}=\left\lfloor \frac{x_i}{2^k}\right\rfloor.$$
وعلى هذا الضلع نحفظ عددًا غير سالب \(c_{e,k}\) بحيث تحقق البتات غير المعالجة بعد الشرط
$$y_u^{(k)}+y_v^{(k)}+c_{e,k}\le \left\lfloor \frac{U_e}{2^k}\right\rfloor.$$
هذا الحمل يمثل مقدار الزيادة التي فرضتها البتات الدنيا بالفعل ويجب على البتات الأعلى امتصاصها. في البداية يكون \(c_{e,0}=0\) على جميع الأضلاع.
ليكن \(u_{e,k}\in\{0,1\}\) هو البت رقم \(k\) في \(U_e\). وبما أن
$$y_u^{(k)}=b_{u,k}+2y_u^{(k+1)},\qquad y_v^{(k)}=b_{v,k}+2y_v^{(k+1)},$$
فإن التعويض في الثابت السابق يعطي
$$b_{u,k}+b_{v,k}+c_{e,k}+2\bigl(y_u^{(k+1)}+y_v^{(k+1)}\bigr)\le u_{e,k}+2\left\lfloor \frac{U_e}{2^{k+1}}\right\rfloor.$$
أصغر حمل جديد ينقل المعلومة نفسها إلى المستوى التالي هو
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{b_{u,k}+b_{v,k}+c_{e,k}-u_{e,k}}{2}\right\rceil\right).$$
وهذه هي العلاقة الأساسية التي يقوم عليها الحل كله.
على أي ضلع، مجموع بتّي الطرفين \(b_{u,k}+b_{v,k}\) لا يمكن أن يتجاوز \(2\)، وبت الحد الأعلى \(u_{e,k}\) يساوي \(0\) أو \(1\). وإذا افترضنا بالاستقراء أن الحمل الداخل ينتمي إلى \(\{0,1,2\}\)، فإن
$$b_{u,k}+b_{v,k}+c_{e,k}-u_{e,k}\in\{-1,0,1,2,3,4\}.$$
وعند تطبيق صيغة الانتقال نحصل مرة أخرى على قيمة ضمن \(\{0,1,2\}\). لذلك لكل ضلع ثلاث حالات فقط، والحالة الكاملة للنظام تقع في الفضاء
$$\{0,1,2\}^{10},\qquad |\{0,1,2\}^{10}|=3^{10}=59049.$$
في البت \(k\) نختار القيم \((b_{0,k},\dots,b_{4,k})\)، ومن المناسب النظر إليها على أنها قناع ثنائي \(m\in\{0,1\}^5\). هذا القناع يحدد فورًا مجموع البتين على كل ضلع، ومن ثم يحدد متجه الحمل الجديد كله.
إذا كان متجه الحمل الحالي هو \(c^{(k)}\in\{0,1,2\}^{10}\)، فإن الانتقال يُكتب مركبة بمركبة على الشكل
$$\bigl(T_k(c^{(k)},m)\bigr)_e=\max\left(0,\left\lceil \frac{s_e(m)+c^{(k)}_e-u_{e,k}}{2}\right\rceil\right),$$
حيث \(s_e(m)\in\{0,1,2\}\) هو مجموع بتّي طرفي الضلع \(e\) الناتج عن القناع.
بما أن \(x_i=\sum_k b_{i,k}2^k\)، فإن الوزن يتفكك إلى
$$\prod_{i=0}^{4} p_i^{x_i}=\prod_{k\ge 0}\prod_{i=0}^{4} p_i^{\,b_{i,k}2^k}.$$
ولهذا فإن اختيار القناع \(m\) عند المستوى \(k\) يضيف عاملًا محليًا
$$W_k(m)=\prod_{i=0}^{4}\left(p_i^{2^k}\right)^{b_{i,k}}\pmod{10^9+7}.$$
ومن هنا جاءت فكرة الحساب المسبق للأوزان الـ32 الممكنة في كل مستوى ثنائي.
افترض أن الحمل الداخل على ضلع ما هو \(c_{e,k}=1\)، وأن بت الحد الأعلى في هذا المستوى هو \(u_{e,k}=0\)، وأن القناع اختار \(b_{u,k}=1\) و\(b_{v,k}=0\). عندئذ
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{1+0+1-0}{2}\right\rceil\right)=1.$$
أي إن الزيادة المتراكمة من المستويات الدنيا لم تختف، بل استمرت إلى المستوى التالي. وإذا كان البتان كلاهما يساوي 1 فسنحصل على
$$c_{e,k+1}=\max\left(0,\left\lceil \frac{1+1+1-0}{2}\right\rceil\right)=2,$$
وهذا يوضح مباشرة لماذا لا بد من تمثيل الحالة 2 في فضاء الحالات.
وكاختبار كامل، عندما تكون الحدود العشرة كلها مساوية لـ2، فإن digit DP تعطي
$$P(2,2,\dots,2)=7120,$$
وهو نفس الناتج الذي يعطيه الفحص الشامل تمامًا.
لتكن \(D_k(c)\) مجموع أوزان جميع التعيينات للبتات الأولى \(k\) التي يكون متجه حملها بعد هذه البتات هو \(c\). عندئذ
$$D_{k+1}(c')=\sum_{\substack{c\in\{0,1,2\}^{10}\\ m\in\{0,1\}^5\\ T_k(c,m)=c'}} D_k(c)\,W_k(m)\pmod{10^9+7},$$
مع شرط بدئي \(D_0(\mathbf 0)=1\) وجميع الحالات الأخرى صفر.
تقوم التطبيقات بمعالجة 31 مستوى ثنائيًا. وهذا يكفي لأن جميع الحدود الناتجة من العلاقة التراجعية تحقق \(U_e<10^9+7<2^{30}\)، كما أن مستوىً إضافيًا صفريًا في الأعلى يكشف أي حمل متبقٍ. لذلك فإن الخماسي يكون مقبولًا بالضبط عندما ينتهي المسار في متجه الصفر، ومن ثم
$$P(U)=D_{31}(\mathbf 0).$$
تعتمد تطبيقات C++ وPython وJava على البنية الرياضية نفسها. فهي تولد أولًا حدود المتتالية الألف، ثم تفك كل حالة من الحالات \(3^{10}\) إلى 10 أرقام ثلاثية تمثل أحمال الأضلاع، وتبني جدول مجموعات البتات على الأضلاع لكل قناع من الأقنعة الـ32، وتحسب مسبقًا الأوزان الـ32 لكل واحد من المستويات الثنائية الـ31.
نسخة Python ليست إعادة كتابة مستقلة للحل العددي، بل مدخل خفيف يفوض العمل الحقيقي إلى الحل المترجم. أمّا نسخة Java فتطبق الانتقالات نفسها مباشرة.
لكتلة حدود ثابتة \(U\)، تستخرج الشيفرة أولًا الأعمدة الثنائية الـ31 للحدود العشرة. بعد ذلك تُشغَّل DP بطبقتين متناوبتين: الطبقة الحالية تمثل \(D_k(c)\)، والطبقة التالية تجمع \(D_{k+1}(c')\). البداية دائمًا من متجه الحمل الصفري، وفي كل خطوة تُجرَّب جميع الأقنعة الـ32.
ولأجل الكفاءة العملية لا تُزار إلا الحالات النشطة، أي الحالات ذات القيمة غير الصفرية في الطبقة الحالية. نظريًا يوجد 59049 حالة، لكن عدد الحالات القابلة للوصول في كثير من المستويات أصغر من ذلك بكثير.
التنفيذ المرجعي يقارن digit DP مع الفحص الشامل على أمثلة صغيرة، ومنها \(P(2,\dots,2)=7120\) و\(P(1,2,\dots,10)=799809376\) وعدة متجهات صغيرة عشوائية. بهذه الطريقة يتأكد أن علاقة الحمل تكافئ تمامًا المجموع الأصلي ذي الأبعاد الخمسة.
بعد ذلك تصبح الخطوة الخارجية بسيطة: لكل \(n\) نأخذ الكتلة \((a_{10n},\dots,a_{10n+9})\)، نحسب \(P(U)\)، ثم نجمع النتائج المئة بترديد \(10^9+7\). وتقوم النسخ المترجمة بتوزيع هذه الأعمال المستقلة على عدة خيوط تنفيذ.
لكتلة حدود واحدة، فإن حد الزمن في أسوأ الأحوال هو
$$O\!\left(31\cdot 3^{10}\cdot 2^5\cdot 10\right),$$
لأن لدينا 31 مستوى ثنائيًا، وبحد أقصى \(3^{10}\) حالة حمل، و32 قناعًا لكل حالة، و10 أضلاع تُحدَّث في كل انتقال. في الواقع يكون الزمن أقل غالبًا بسبب الاكتفاء بالحالات النشطة.
أما الذاكرة فهي \(O(3^{10})\) لطبقتي DP، إضافة إلى جداول التهيئة المسبقة. ويزيد الجمع الخارجي على 100 حالة كمية العمل الكلية بمقدار 100 مرة، لكنه لا يغيّر طبيعة الخوارزمية الداخلية.
المنهج الساذج بخمس حلقات متداخلة سيتطلب المرور على مجالات قريبة من \(10^9\)، وهذا غير عملي تمامًا. قوة digit DP هنا أنها تستبدل هذه المجالات الهائلة بأبجدية صغيرة جدًا من الأحمال هي \(\{0,1,2\}\) على كل ضلع.