The side lengths are generated by
$$s_1=1,\quad s_2=2,\quad s_3=3,\quad s_n=s_{n-1}+s_{n-3}\quad (n\ge 4).$$
Because \(s_{n-3}\gt 0\), the sequence is strictly increasing, so every subset of \(\{s_1,\dots,s_n\}\) has a unique largest selected side. Let \(f(n)\) be the number of nonempty subsets that can be arranged into a nondegenerate polygon. The solver computes \(f(10^{18}) \bmod 10^9\).
For any finite set of positive side lengths, a polygon exists if and only if the largest side is smaller than the sum of all remaining sides. If a subset has largest side \(s_n\), then it is bad exactly when the other chosen sides have total length at most \(s_n\).
This immediately turns the geometric problem into a counting problem about subset sums.
Define \(b_n\) as the number of subsets of \(\{s_1,\dots,s_{n-1}\}\) whose sum is at most \(s_n\):
$$b_n=\#\left\{A\subseteq \{1,\dots,n-1\}:\sum_{i\in A}s_i\le s_n\right\}.$$
Every non-polygon subset of \(\{s_1,\dots,s_n\}\) has a unique largest element \(s_k\), and after removing that largest side the remaining subset contributes to \(b_k\). Therefore the bad subsets are counted exactly once by \(\sum_{k=1}^{n} b_k\), and
$$\boxed{f(n)=\left(2^n-1\right)-\sum_{k=1}^{n} b_k.}$$
This identity is the core formula used by all three implementations.
The C++ reference solution builds the first values of \(b_n\) with an exact memoized counter. Let
$$P_i=\sum_{k=1}^{i}s_k,\qquad C(i,L)=\#\left\{A\subseteq \{1,\dots,i\}:\sum_{k\in A}s_k\le L\right\}.$$
The recursion implemented in ExactCounter is
$$ C(i,L)= \begin{cases} 1, & i=0,\\ 2^i, & L\ge P_i,\\ C(i-1,L), & s_i\gt L,\\ C(i-1,L)+C(i-1,L-s_i), & s_i\le L. \end{cases} $$
Then \(b_n=C(n-1,s_n)\). The exact values produced by the local code are
$$ (b_1,b_2,b_3,b_4,b_5,b_6,b_7,b_8)=(1,2,4,6,11,20,36,67). $$
These eight terms form the base state for the fast solver.
From the exact sequence one obtains the linear recurrence embedded in all three source files:
$$ b_n=3b_{n-1}-2b_{n-2}+2b_{n-3}-5b_{n-4}+b_{n-5}+b_{n-6}+3b_{n-7}-2b_{n-8}, \qquad n\ge 9. $$
The C++ program does not merely assume this relation: it recomputes \(b_n\) exactly up to \(n=60\) and checks that the recurrence matches every term from \(n=9\) onward. That validation step is the reason the mathematical description should treat this recurrence as a verified fact coming from the local solution, not as an unsupported guess.
We need \(B_n=\sum_{k=1}^{n} b_k\), not just \(b_n\). So the solver stores the 9-component state
$$ v_n= \begin{bmatrix} b_n\\ b_{n-1}\\ b_{n-2}\\ b_{n-3}\\ b_{n-4}\\ b_{n-5}\\ b_{n-6}\\ b_{n-7}\\ B_n \end{bmatrix}. $$
With the recurrence coefficients in the first row, simple shifts in rows \(2\) through \(8\), and one extra cumulative row, we get
$$v_{n+1}=Tv_n,$$
where
$$ T= \begin{bmatrix} 3 & -2 & 2 & -5 & 1 & 1 & 3 & -2 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 3 & -2 & 2 & -5 & 1 & 1 & 3 & -2 & 1 \end{bmatrix}. $$
The starting vector is
$$ v_8= \begin{bmatrix} 67\\ 36\\ 20\\ 11\\ 6\\ 4\\ 2\\ 1\\ 147 \end{bmatrix}, \qquad 147=1+2+4+6+11+20+36+67. $$
For \(n\gt 8\), binary exponentiation gives \(v_n=T^{\,n-8}v_8\) modulo \(10^9\). The last component is \(B_n\).
Once \(B_n\) is known, the answer is
$$\boxed{f(n)\equiv 2^n-1-B_n \pmod{10^9}.}$$
A small example shows the decomposition clearly. For \(n=5\), the sequence is \((1,2,3,4,6)\), the exact counter gives
$$ (b_1,b_2,b_3,b_4,b_5)=(1,2,4,6,11), $$
and therefore
$$ f(5)=2^5-1-(1+2+4+6+11)=31-24=7. $$
The C++ validation also checks the Project Euler checkpoints
$$f(10)=501,\qquad f(25)=18635853.$$
Running the local solver for the target input yields
$$f(10^{18}) \equiv 697003956 \pmod{10^9}.$$
The C++ file contains both the exact validator and the fast solver. ExactCounter computes \(b_n\) by memoized subset-sum counting and confirms the recurrence on \(n\le 60\). The function prefix_sum_b_mod handles the eight base terms directly, then switches to 9 by 9 matrix exponentiation. Negative recurrence coefficients are normalized modulo \(10^9\) before being inserted into the transition matrix. Finally, solve_mod computes \(2^n \bmod 10^9\), subtracts \(1\) and the prefix sum \(B_n\), and normalizes the result.
The Python and Java files are compact translations of the same fast path: identical base values, identical recurrence coefficients, the same 9-state transition, and the same final congruence.
The exact subset-sum validator is used only on small \(n\), so it does not affect the asymptotic cost of the real computation. The production path performs binary exponentiation on a fixed \(9\times 9\) matrix, giving \(O(9^3\log n)\) time with dense multiplication and \(O(9^2)\) memory. Since \(9\) is constant, this is effectively \(O(\log n)\) time and constant auxiliary space.
solutionsCpp/Euler382.cppsolutionsPython/Euler382.py and solutionsJava/Euler382.javaDie Seitenlängen entstehen durch
$$s_1=1,\quad s_2=2,\quad s_3=3,\quad s_n=s_{n-1}+s_{n-3}\quad (n\ge 4).$$
Weil \(s_{n-3}\gt 0\) gilt, ist die Folge streng wachsend. Daher besitzt jede Teilmenge von \(\{s_1,\dots,s_n\}\) genau eine größte gewählte Seite. Sei \(f(n)\) die Anzahl der nichtleeren Teilmengen, die ein nichtentartetes Polygon bilden können. Gesucht ist \(f(10^{18}) \bmod 10^9\).
Für eine endliche Menge positiver Seitenlängen existiert genau dann ein Polygon, wenn die größte Seite kleiner ist als die Summe aller übrigen Seiten. Hat eine Teilmenge die größte Seite \(s_n\), dann ist sie genau dann schlecht, wenn die Summe der anderen gewählten Seiten höchstens \(s_n\) ist.
Damit wird die geometrische Frage zu einer reinen Teilmengen-Summen-Zählung.
Definiere \(b_n\) als die Anzahl der Teilmengen von \(\{s_1,\dots,s_{n-1}\}\), deren Summe höchstens \(s_n\) ist:
$$b_n=\#\left\{A\subseteq \{1,\dots,n-1\}:\sum_{i\in A}s_i\le s_n\right\}.$$
Jede nicht zulässige Teilmenge von \(\{s_1,\dots,s_n\}\) besitzt ein eindeutiges größtes Element \(s_k\). Entfernt man diese größte Seite, bleibt genau eine Teilmenge übrig, die zu \(b_k\) beiträgt. Also werden alle schlechten Teilmengen genau einmal durch \(\sum_{k=1}^{n} b_k\) erfasst, und damit gilt
$$\boxed{f(n)=\left(2^n-1\right)-\sum_{k=1}^{n} b_k.}$$
Genau diese Identität verwenden alle drei Implementierungen.
Die C++-Referenzlösung berechnet die ersten Werte von \(b_n\) mit einem exakten memoisierten Zähler. Setze
$$P_i=\sum_{k=1}^{i}s_k,\qquad C(i,L)=\#\left\{A\subseteq \{1,\dots,i\}:\sum_{k\in A}s_k\le L\right\}.$$
Die in ExactCounter implementierte Rekursion lautet
$$ C(i,L)= \begin{cases} 1, & i=0,\\ 2^i, & L\ge P_i,\\ C(i-1,L), & s_i\gt L,\\ C(i-1,L)+C(i-1,L-s_i), & s_i\le L. \end{cases} $$
Dann ist \(b_n=C(n-1,s_n)\). Die exakten Startwerte aus dem lokalen Code sind
$$ (b_1,b_2,b_3,b_4,b_5,b_6,b_7,b_8)=(1,2,4,6,11,20,36,67). $$
Diese acht Werte bilden den Basiszustand des schnellen Verfahrens.
Aus der exakten Folge erhält man die lineare Rekurrenz, die in allen drei Quelldateien hinterlegt ist:
$$ b_n=3b_{n-1}-2b_{n-2}+2b_{n-3}-5b_{n-4}+b_{n-5}+b_{n-6}+3b_{n-7}-2b_{n-8}, \qquad n\ge 9. $$
Das C++-Programm übernimmt diese Beziehung nicht blind: Es berechnet \(b_n\) bis \(n=60\) exakt nach und prüft, dass die Rekurrenz ab \(n=9\) jeden Term korrekt reproduziert. In der mathematischen Beschreibung sollte diese Rekurrenz deshalb als aus dem lokalen Solver verifizierte Tatsache behandelt werden.
Benötigt wird \(B_n=\sum_{k=1}^{n} b_k\), nicht nur \(b_n\). Deshalb speichert der Solver den 9-dimensionalen Zustand
$$ v_n= \begin{bmatrix} b_n\\ b_{n-1}\\ b_{n-2}\\ b_{n-3}\\ b_{n-4}\\ b_{n-5}\\ b_{n-6}\\ b_{n-7}\\ B_n \end{bmatrix}. $$
Mit den Rekurrenzkoeffizienten in der ersten Zeile, Verschiebungen in den Zeilen \(2\) bis \(8\) und einer zusätzlichen Summenzeile gilt
$$v_{n+1}=Tv_n,$$
wobei
$$ T= \begin{bmatrix} 3 & -2 & 2 & -5 & 1 & 1 & 3 & -2 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 3 & -2 & 2 & -5 & 1 & 1 & 3 & -2 & 1 \end{bmatrix} $$
ist. Der Startvektor lautet
$$ v_8= \begin{bmatrix} 67\\ 36\\ 20\\ 11\\ 6\\ 4\\ 2\\ 1\\ 147 \end{bmatrix}, \qquad 147=1+2+4+6+11+20+36+67. $$
Für \(n\gt 8\) liefert binäre Exponentiation \(v_n=T^{\,n-8}v_8 \pmod{10^9}\). Die letzte Komponente ist dann \(B_n\).
Sobald \(B_n\) bekannt ist, folgt
$$\boxed{f(n)\equiv 2^n-1-B_n \pmod{10^9}.}$$
Ein kleines Beispiel macht die Zerlegung sichtbar. Für \(n=5\) ist die Folge \((1,2,3,4,6)\), und der exakte Zähler gibt
$$ (b_1,b_2,b_3,b_4,b_5)=(1,2,4,6,11). $$
Daraus folgt
$$ f(5)=2^5-1-(1+2+4+6+11)=31-24=7. $$
Die C++-Validierung prüft außerdem die Euler-Kontrollwerte
$$f(10)=501,\qquad f(25)=18635853.$$
Für das eigentliche Ziel liefert der lokale Solver
$$f(10^{18}) \equiv 697003956 \pmod{10^9}.$$
Die C++-Datei enthält sowohl den exakten Prüfer als auch den schnellen Solver. ExactCounter berechnet \(b_n\) per memoisierter Teilmengen-Summen-Zählung und bestätigt die Rekurrenz für \(n\le 60\). Die Funktion prefix_sum_b_mod behandelt zunächst die acht Basiswerte direkt und wechselt dann zur Matrixpotenz \(9\times 9\). Negative Rekurrenzkoeffizienten werden vor dem Eintrag in die Übergangsmatrix modulo \(10^9\) normalisiert. Anschließend berechnet solve_mod den Wert \(2^n \bmod 10^9\), subtrahiert \(1\) sowie \(B_n\) und normiert das Ergebnis.
Die Python- und Java-Dateien sind kompakte Übersetzungen desselben schnellen Pfads: gleiche Basiswerte, gleiche Rekurrenz, derselbe 9-Zustands-Übergang und dieselbe Schlussformel.
Der exakte Teilmengen-Summen-Prüfer wird nur für kleine \(n\) verwendet und ändert die asymptotischen Kosten der eigentlichen Berechnung nicht. Der Produktionspfad führt binäre Exponentiation auf einer festen \(9\times 9\)-Matrix aus. Das ergibt \(O(9^3\log n)\) Zeit bei dichter Multiplikation und \(O(9^2)\) Speicher. Da \(9\) konstant ist, entspricht das praktisch \(O(\log n)\) Zeit bei konstantem Zusatzspeicher.
solutionsCpp/Euler382.cppsolutionsPython/Euler382.py und solutionsJava/Euler382.javaKenar uzunlukları şu kuralla üretilir:
$$s_1=1,\quad s_2=2,\quad s_3=3,\quad s_n=s_{n-1}+s_{n-3}\quad (n\ge 4).$$
\(s_{n-3}\gt 0\) olduğu için dizi sıkı biçimde artandır. Bu yüzden \(\{s_1,\dots,s_n\}\) kümesinin her alt kümesinde seçilmiş en büyük kenar tektir. \(f(n)\), boş olmayan alt kümeler içinde dejenere olmayan bir çokgen oluşturabilenlerin sayısıdır. Amaç \(f(10^{18}) \bmod 10^9\) değerini bulmaktır.
Pozitif kenar uzunluklarından oluşan sonlu bir küme, ancak ve ancak en büyük kenar diğer tüm kenarların toplamından küçükse çokgen oluşturabilir. Bir alt kümenin en büyük kenarı \(s_n\) ise, bu alt küme tam olarak diğer seçili kenarların toplamı \(s_n\)'den büyük değilse kötü sayılır.
Böylece geometrik koşul doğrudan bir alt küme-toplamı sayımına dönüşür.
\(b_n\), \(\{s_1,\dots,s_{n-1}\}\) içindeki toplamı en fazla \(s_n\) olan alt kümelerin sayısı olsun:
$$b_n=\#\left\{A\subseteq \{1,\dots,n-1\}:\sum_{i\in A}s_i\le s_n\right\}.$$
\(\{s_1,\dots,s_n\}\) içindeki her çokgen oluşturamayan alt kümenin tek bir en büyük elemanı \(s_k\) vardır. Bu en büyük kenar çıkarıldığında geriye tam olarak \(b_k\)'de sayılan bir alt küme kalır. Dolayısıyla kötü alt kümelerin toplam sayısı \(\sum_{k=1}^{n} b_k\) olur ve
$$\boxed{f(n)=\left(2^n-1\right)-\sum_{k=1}^{n} b_k.}$$
Üç çözüm dosyasının da dayandığı temel özdeşlik budur.
C++ referans çözümü, \(b_n\)'nin ilk değerlerini tam ve önbelleklemeli bir sayaçla üretir. Şunları tanımlayalım:
$$P_i=\sum_{k=1}^{i}s_k,\qquad C(i,L)=\#\left\{A\subseteq \{1,\dots,i\}:\sum_{k\in A}s_k\le L\right\}.$$
ExactCounter içinde kullanılan özyineleme şudur:
$$ C(i,L)= \begin{cases} 1, & i=0,\\ 2^i, & L\ge P_i,\\ C(i-1,L), & s_i\gt L,\\ C(i-1,L)+C(i-1,L-s_i), & s_i\le L. \end{cases} $$
Buna göre \(b_n=C(n-1,s_n)\). Yerel kodun ürettiği tam başlangıç değerleri
$$ (b_1,b_2,b_3,b_4,b_5,b_6,b_7,b_8)=(1,2,4,6,11,20,36,67) $$
şeklindedir. Hızlı çözücü bu sekiz değeri başlangıç durumu olarak kullanır.
Bu tam diziden, üç kaynak dosyanın da kullandığı lineer rekürans elde edilir:
$$ b_n=3b_{n-1}-2b_{n-2}+2b_{n-3}-5b_{n-4}+b_{n-5}+b_{n-6}+3b_{n-7}-2b_{n-8}, \qquad n\ge 9. $$
C++ programı bu bağıntıyı sorgusuz kabul etmez. \(b_n\) değerlerini \(n=60\)'a kadar tam hesaplar ve \(n=9\)'dan itibaren reküransın her terimi doğru verdiğini kontrol eder. Bu nedenle matematiksel açıklamada bu rekürans, yerel çözüm tarafından doğrulanmış bir olgu olarak ele alınmalıdır.
İhtiyacımız olan şey yalnızca \(b_n\) değil, \(B_n=\sum_{k=1}^{n} b_k\) değeridir. Bu yüzden çözücü şu 9 bileşenli durumu taşır:
$$ v_n= \begin{bmatrix} b_n\\ b_{n-1}\\ b_{n-2}\\ b_{n-3}\\ b_{n-4}\\ b_{n-5}\\ b_{n-6}\\ b_{n-7}\\ B_n \end{bmatrix}. $$
İlk satıra rekürans katsayıları, \(2\) ile \(8\). satırlara kaydırma işlemi ve son satıra da kümülatif güncelleme konulduğunda
$$v_{n+1}=Tv_n$$
olur; burada
$$ T= \begin{bmatrix} 3 & -2 & 2 & -5 & 1 & 1 & 3 & -2 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 3 & -2 & 2 & -5 & 1 & 1 & 3 & -2 & 1 \end{bmatrix} $$
matrisidir. Başlangıç vektörü
$$ v_8= \begin{bmatrix} 67\\ 36\\ 20\\ 11\\ 6\\ 4\\ 2\\ 1\\ 147 \end{bmatrix}, \qquad 147=1+2+4+6+11+20+36+67 $$
şeklindedir. \(n\gt 8\) için ikili üs alma ile \(v_n=T^{\,n-8}v_8 \pmod{10^9}\) bulunur; son bileşen \(B_n\)'dir.
\(B_n\) bulunduğunda cevap
$$\boxed{f(n)\equiv 2^n-1-B_n \pmod{10^9}.}$$
Küçük bir örnek ayrıştırmayı açıkça gösterir. \(n=5\) için dizi \((1,2,3,4,6)\) olur ve tam sayaç
$$ (b_1,b_2,b_3,b_4,b_5)=(1,2,4,6,11) $$
değerlerini verir. Buradan
$$ f(5)=2^5-1-(1+2+4+6+11)=31-24=7 $$
elde edilir. C++ doğrulaması ayrıca Euler kontrol noktalarını da sınar:
$$f(10)=501,\qquad f(25)=18635853.$$
Hedef giriş için yerel çözücü şu sonucu verir:
$$f(10^{18}) \equiv 697003956 \pmod{10^9}.$$
C++ dosyası hem tam doğrulayıcıyı hem de hızlı çözücüyü içerir. ExactCounter, önbelleklemeli alt küme-toplamı sayımıyla \(b_n\) değerlerini üretir ve reküransı \(n\le 60\) aralığında doğrular. prefix_sum_b_mod önce sekiz temel terimi doğrudan işler, sonra \(9\times 9\) matris üslemesine geçer. Negatif rekürans katsayıları geçiş matrisine konmadan önce \(10^9\) modunda normalize edilir. Son olarak solve_mod, \(2^n \bmod 10^9\) değerini hesaplar, \(1\) ve \(B_n\)'yi çıkarır, ardından sonucu tekrar normalize eder.
Python ve Java dosyaları aynı hızlı yolun kısa çevirileridir: aynı temel değerler, aynı rekürans katsayıları, aynı 9 durumlu geçiş ve aynı son eşitlik kullanılır.
Tam alt küme-toplamı doğrulayıcısı yalnızca küçük \(n\) için kullanılır; bu nedenle gerçek hesaplamanın asimptotik maliyetini etkilemez. Üretim yolu, sabit boyutlu \(9\times 9\) bir matris üzerinde ikili üs alma uygular. Yoğun matris çarpımıyla zaman karmaşıklığı \(O(9^3\log n)\), bellek karmaşıklığı \(O(9^2)\)'dir. \(9\) sabit olduğundan bu pratikte \(O(\log n)\) zaman ve sabit yardımcı bellek anlamına gelir.
solutionsCpp/Euler382.cppsolutionsPython/Euler382.py ve solutionsJava/Euler382.javaLas longitudes de lado se generan mediante
$$s_1=1,\quad s_2=2,\quad s_3=3,\quad s_n=s_{n-1}+s_{n-3}\quad (n\ge 4).$$
Como \(s_{n-3}\gt 0\), la sucesión es estrictamente creciente; por eso cada subconjunto de \(\{s_1,\dots,s_n\}\) tiene un lado máximo único. Sea \(f(n)\) el número de subconjuntos no vacíos que pueden formar un polígono no degenerado. El objetivo es calcular \(f(10^{18}) \bmod 10^9\).
Para un conjunto finito de longitudes positivas, existe un polígono si y solo si el lado mayor es menor que la suma de todos los demás. Si un subconjunto tiene lado máximo \(s_n\), entonces es malo exactamente cuando la suma de los otros lados elegidos es como mucho \(s_n\).
Así, el problema geométrico se convierte en contar subconjuntos con suma acotada.
Definimos \(b_n\) como el número de subconjuntos de \(\{s_1,\dots,s_{n-1}\}\) cuya suma no supera \(s_n\):
$$b_n=\#\left\{A\subseteq \{1,\dots,n-1\}:\sum_{i\in A}s_i\le s_n\right\}.$$
Cada subconjunto que no puede formar polígono dentro de \(\{s_1,\dots,s_n\}\) tiene un elemento máximo único \(s_k\). Si quitamos ese lado máximo, lo que queda es exactamente un subconjunto contado por \(b_k\). Por tanto, el número total de subconjuntos malos es \(\sum_{k=1}^{n} b_k\), y
$$\boxed{f(n)=\left(2^n-1\right)-\sum_{k=1}^{n} b_k.}$$
Esta es la identidad central usada por las tres implementaciones locales.
La solución de referencia en C++ obtiene los primeros valores de \(b_n\) con un contador exacto y memoizado. Definimos
$$P_i=\sum_{k=1}^{i}s_k,\qquad C(i,L)=\#\left\{A\subseteq \{1,\dots,i\}:\sum_{k\in A}s_k\le L\right\}.$$
La recurrencia implementada en ExactCounter es
$$ C(i,L)= \begin{cases} 1, & i=0,\\ 2^i, & L\ge P_i,\\ C(i-1,L), & s_i\gt L,\\ C(i-1,L)+C(i-1,L-s_i), & s_i\le L. \end{cases} $$
Entonces \(b_n=C(n-1,s_n)\). Los valores iniciales exactos producidos por el código local son
$$ (b_1,b_2,b_3,b_4,b_5,b_6,b_7,b_8)=(1,2,4,6,11,20,36,67). $$
Estos ocho términos forman el estado base del algoritmo rápido.
A partir de la secuencia exacta se obtiene la recurrencia lineal incluida en los tres archivos fuente:
$$ b_n=3b_{n-1}-2b_{n-2}+2b_{n-3}-5b_{n-4}+b_{n-5}+b_{n-6}+3b_{n-7}-2b_{n-8}, \qquad n\ge 9. $$
El programa en C++ no la toma como un acto de fe: recalcula \(b_n\) exactamente hasta \(n=60\) y comprueba que la recurrencia reproduce cada término desde \(n=9\). Por eso, en esta explicación debe tratarse como un hecho verificado por la solución local.
No basta con conocer \(b_n\); necesitamos \(B_n=\sum_{k=1}^{n} b_k\). Por eso el solver usa el estado de 9 componentes
$$ v_n= \begin{bmatrix} b_n\\ b_{n-1}\\ b_{n-2}\\ b_{n-3}\\ b_{n-4}\\ b_{n-5}\\ b_{n-6}\\ b_{n-7}\\ B_n \end{bmatrix}. $$
Con los coeficientes de la recurrencia en la primera fila, desplazamientos en las filas \(2\) a \(8\) y una fila acumulativa adicional, se obtiene
$$v_{n+1}=Tv_n,$$
donde
$$ T= \begin{bmatrix} 3 & -2 & 2 & -5 & 1 & 1 & 3 & -2 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 3 & -2 & 2 & -5 & 1 & 1 & 3 & -2 & 1 \end{bmatrix}. $$
El vector inicial es
$$ v_8= \begin{bmatrix} 67\\ 36\\ 20\\ 11\\ 6\\ 4\\ 2\\ 1\\ 147 \end{bmatrix}, \qquad 147=1+2+4+6+11+20+36+67. $$
Para \(n\gt 8\), la exponenciación binaria produce \(v_n=T^{\,n-8}v_8 \pmod{10^9}\). La última componente es \(B_n\).
Una vez conocido \(B_n\), la respuesta es
$$\boxed{f(n)\equiv 2^n-1-B_n \pmod{10^9}.}$$
Un ejemplo pequeño muestra bien la descomposición. Para \(n=5\), la sucesión es \((1,2,3,4,6)\) y el contador exacto devuelve
$$ (b_1,b_2,b_3,b_4,b_5)=(1,2,4,6,11). $$
Por tanto,
$$ f(5)=2^5-1-(1+2+4+6+11)=31-24=7. $$
La validación en C++ también comprueba los hitos del problema:
$$f(10)=501,\qquad f(25)=18635853.$$
Para la entrada objetivo, el solver local devuelve
$$f(10^{18}) \equiv 697003956 \pmod{10^9}.$$
El archivo en C++ contiene tanto el validador exacto como el solver rápido. ExactCounter calcula \(b_n\) mediante conteo memoizado de sumas de subconjuntos y confirma la recurrencia para \(n\le 60\). La función prefix_sum_b_mod trata de forma directa los ocho valores base y después pasa a exponenciación de matrices \(9\times 9\). Los coeficientes negativos de la recurrencia se normalizan módulo \(10^9\) antes de insertarlos en la matriz de transición. Finalmente, solve_mod calcula \(2^n \bmod 10^9\), resta \(1\) y \(B_n\), y vuelve a normalizar.
Los archivos Python y Java son traducciones compactas del mismo camino rápido: mismos valores base, misma recurrencia, misma transición de 9 estados y la misma congruencia final.
El validador exacto de sumas de subconjuntos solo se usa para valores pequeños de \(n\), así que no cambia el coste asintótico del cálculo real. La vía principal hace exponenciación binaria sobre una matriz fija de \(9\times 9\), con coste \(O(9^3\log n)\) usando multiplicación densa y memoria \(O(9^2)\). Como \(9\) es constante, en la práctica es un algoritmo \(O(\log n)\) en tiempo con espacio auxiliar constante.
solutionsCpp/Euler382.cppsolutionsPython/Euler382.py y solutionsJava/Euler382.java边长序列由下式生成：
$$s_1=1,\quad s_2=2,\quad s_3=3,\quad s_n=s_{n-1}+s_{n-3}\quad (n\ge 4).$$
由于 \(s_{n-3}\gt 0\)，该序列严格递增，因此 \(\{s_1,\dots,s_n\}\) 的每个子集都有唯一的最大边。记 \(f(n)\) 为所有非空子集中，能够组成非退化多边形的子集个数。目标是计算 \(f(10^{18}) \bmod 10^9\)。
对于有限个正边长，能构成多边形当且仅当最大边严格小于其余边之和。若某个子集的最大边为 \(s_n\)，那么它恰好在“其余被选边的总和不大于 \(s_n\)”时是一个坏子集。
这样，几何判定就变成了一个有界子集和计数问题。
定义 \(b_n\) 为从 \(\{s_1,\dots,s_{n-1}\}\) 中选取子集且其和不超过 \(s_n\) 的个数：
$$b_n=\#\left\{A\subseteq \{1,\dots,n-1\}:\sum_{i\in A}s_i\le s_n\right\}.$$
\(\{s_1,\dots,s_n\}\) 中每个不能成多边形的子集都有唯一的最大元素 \(s_k\)。去掉这条最大边后，剩余部分正好对应 \(b_k\) 中的一项。因此坏子集总数就是 \(\sum_{k=1}^{n} b_k\)，于是
$$\boxed{f(n)=\left(2^n-1\right)-\sum_{k=1}^{n} b_k.}$$
这就是三份本地实现共同使用的核心公式。
C++ 参考实现先用一个带记忆化的精确计数器生成 \(b_n\) 的前若干项。定义
$$P_i=\sum_{k=1}^{i}s_k,\qquad C(i,L)=\#\left\{A\subseteq \{1,\dots,i\}:\sum_{k\in A}s_k\le L\right\}.$$
ExactCounter 中实现的递推是
$$ C(i,L)= \begin{cases} 1, & i=0,\\ 2^i, & L\ge P_i,\\ C(i-1,L), & s_i\gt L,\\ C(i-1,L)+C(i-1,L-s_i), & s_i\le L. \end{cases} $$
于是 \(b_n=C(n-1,s_n)\)。本地代码给出的八个初始值为
$$ (b_1,b_2,b_3,b_4,b_5,b_6,b_7,b_8)=(1,2,4,6,11,20,36,67) $$
快速算法正是以这八项作为基状态。
由精确序列得到并写入三份源码中的递推关系是
$$ b_n=3b_{n-1}-2b_{n-2}+2b_{n-3}-5b_{n-4}+b_{n-5}+b_{n-6}+3b_{n-7}-2b_{n-8}, \qquad n\ge 9. $$
C++ 程序并不是无条件相信它，而是把 \(b_n\) 精确算到 \(n=60\)，然后逐项检查该递推从 \(n=9\) 起是否全部成立。因此这里应把它视为由本地解法验证过的事实，而不是没有支撑的猜测。
我们真正需要的是 \(B_n=\sum_{k=1}^{n} b_k\)，而不仅仅是 \(b_n\)。因此求解器维护如下 9 维状态：
$$ v_n= \begin{bmatrix} b_n\\ b_{n-1}\\ b_{n-2}\\ b_{n-3}\\ b_{n-4}\\ b_{n-5}\\ b_{n-6}\\ b_{n-7}\\ B_n \end{bmatrix}. $$
第一行放递推系数，第 \(2\) 到第 \(8\) 行负责平移，最后一行负责累计前缀和，于是有
$$v_{n+1}=Tv_n,$$
其中
$$ T= \begin{bmatrix} 3 & -2 & 2 & -5 & 1 & 1 & 3 & -2 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 3 & -2 & 2 & -5 & 1 & 1 & 3 & -2 & 1 \end{bmatrix}. $$
初始向量取为
$$ v_8= \begin{bmatrix} 67\\ 36\\ 20\\ 11\\ 6\\ 4\\ 2\\ 1\\ 147 \end{bmatrix}, \qquad 147=1+2+4+6+11+20+36+67. $$
当 \(n\gt 8\) 时，用二分幂得到 \(v_n=T^{\,n-8}v_8 \pmod{10^9}\)，其最后一个分量就是 \(B_n\)。
一旦求出 \(B_n\)，答案就是
$$\boxed{f(n)\equiv 2^n-1-B_n \pmod{10^9}.}$$
用一个小例子可以清楚看到这种拆分。对 \(n=5\)，序列为 \((1,2,3,4,6)\)，精确计数器给出
$$ (b_1,b_2,b_3,b_4,b_5)=(1,2,4,6,11) $$
因此
$$ f(5)=2^5-1-(1+2+4+6+11)=31-24=7 $$
C++ 验证代码还会检查题目中的两个已知值：
$$f(10)=501,\qquad f(25)=18635853$$
对目标输入，本地求解器输出
$$f(10^{18}) \equiv 697003956 \pmod{10^9}$$
C++ 文件同时包含精确验证器和快速求解器。ExactCounter 用带记忆化的子集和计数生成 \(b_n\)，并在 \(n\le 60\) 的范围内验证递推。prefix_sum_b_mod 先直接处理八个基值，然后切换到 \(9\times 9\) 矩阵快速幂。递推中的负系数在写入转移矩阵前会先按 \(10^9\) 取模归一化。最后，solve_mod 计算 \(2^n \bmod 10^9\)，减去 \(1\) 和 \(B_n\)，再做一次归一化。
Python 和 Java 文件是同一条快速路径的精简翻译：使用相同的基值、相同的递推系数、相同的 9 维状态转移以及相同的最终同余式。
精确子集和验证器只用于很小的 \(n\)，不会影响正式计算的渐近复杂度。主算法是在固定的 \(9\times 9\) 矩阵上做二分幂，采用稠密矩阵乘法时，时间复杂度为 \(O(9^3\log n)\)，空间复杂度为 \(O(9^2)\)。由于 \(9\) 是常数，实际效果就是 \(O(\log n)\) 时间和常数级辅助空间。
solutionsCpp/Euler382.cppsolutionsPython/Euler382.py 与 solutionsJava/Euler382.javaДлины сторон задаются рекуррентно:
$$s_1=1,\quad s_2=2,\quad s_3=3,\quad s_n=s_{n-1}+s_{n-3}\quad (n\ge 4).$$
Так как \(s_{n-3}\gt 0\), последовательность строго возрастает, а значит у любого подмножества \(\{s_1,\dots,s_n\}\) есть единственная наибольшая выбранная сторона. Пусть \(f(n)\) обозначает число непустых подмножеств, из которых можно составить невырожденный многоугольник. Требуется вычислить \(f(10^{18}) \bmod 10^9\).
Для конечного набора положительных длин многоугольник существует тогда и только тогда, когда наибольшая сторона меньше суммы всех остальных. Если в подмножестве максимальна сторона \(s_n\), то такое подмножество является плохим ровно в том случае, когда сумма остальных выбранных сторон не превосходит \(s_n\).
Тем самым геометрическая задача превращается в задачу подсчета подмножеств с ограниченной суммой.
Определим \(b_n\) как число подмножеств множества \(\{s_1,\dots,s_{n-1}\}\), сумма которых не превышает \(s_n\):
$$b_n=\#\left\{A\subseteq \{1,\dots,n-1\}:\sum_{i\in A}s_i\le s_n\right\}.$$
Каждое подмножество из \(\{s_1,\dots,s_n\}\), которое не образует многоугольник, имеет единственный максимальный элемент \(s_k\). Если убрать эту наибольшую сторону, останется ровно один набор, учитываемый в \(b_k\). Поэтому число всех плохих подмножеств равно \(\sum_{k=1}^{n} b_k\), и мы получаем
$$\boxed{f(n)=\left(2^n-1\right)-\sum_{k=1}^{n} b_k.}$$
Это и есть ключевая формула, на которой основаны все три локальные реализации.
Эталонная реализация на C++ строит первые значения \(b_n\) с помощью точного мемоизированного счетчика. Обозначим
$$P_i=\sum_{k=1}^{i}s_k,\qquad C(i,L)=\#\left\{A\subseteq \{1,\dots,i\}:\sum_{k\in A}s_k\le L\right\}.$$
Рекурсия, реализованная в ExactCounter, имеет вид
$$ C(i,L)= \begin{cases} 1, & i=0,\\ 2^i, & L\ge P_i,\\ C(i-1,L), & s_i\gt L,\\ C(i-1,L)+C(i-1,L-s_i), & s_i\le L. \end{cases} $$
Тогда \(b_n=C(n-1,s_n)\). Точные базовые значения из локального кода равны
$$ (b_1,b_2,b_3,b_4,b_5,b_6,b_7,b_8)=(1,2,4,6,11,20,36,67). $$
Именно эти восемь членов образуют начальное состояние быстрого алгоритма.
Из точной последовательности получается рекуррентность, встроенная во все три исходных файла:
$$ b_n=3b_{n-1}-2b_{n-2}+2b_{n-3}-5b_{n-4}+b_{n-5}+b_{n-6}+3b_{n-7}-2b_{n-8}, \qquad n\ge 9. $$
Программа на C++ не принимает ее на веру: она точно пересчитывает \(b_n\) вплоть до \(n=60\) и проверяет, что начиная с \(n=9\) рекуррентность воспроизводит каждый член. Поэтому в математическом описании ее корректно рассматривать как факт, подтвержденный локальным решением.
Нужен не только сам \(b_n\), но и \(B_n=\sum_{k=1}^{n} b_k\). Поэтому решатель хранит 9-компонентный вектор состояния
$$ v_n= \begin{bmatrix} b_n\\ b_{n-1}\\ b_{n-2}\\ b_{n-3}\\ b_{n-4}\\ b_{n-5}\\ b_{n-6}\\ b_{n-7}\\ B_n \end{bmatrix}. $$
Если в первую строку поместить коэффициенты рекуррентности, строки \(2\)–\(8\) использовать для сдвига, а последнюю строку сделать накопительной, то получаем
$$v_{n+1}=Tv_n,$$
где
$$ T= \begin{bmatrix} 3 & -2 & 2 & -5 & 1 & 1 & 3 & -2 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 3 & -2 & 2 & -5 & 1 & 1 & 3 & -2 & 1 \end{bmatrix}. $$
Начальный вектор равен
$$ v_8= \begin{bmatrix} 67\\ 36\\ 20\\ 11\\ 6\\ 4\\ 2\\ 1\\ 147 \end{bmatrix}, \qquad 147=1+2+4+6+11+20+36+67. $$
Для \(n\gt 8\) бинарное возведение в степень дает \(v_n=T^{\,n-8}v_8 \pmod{10^9}\). Последняя компонента этого вектора и есть \(B_n\).
Как только найдено \(B_n\), ответ записывается так:
$$\boxed{f(n)\equiv 2^n-1-B_n \pmod{10^9}.}$$
Небольшой пример показывает разложение явно. При \(n=5\) последовательность равна \((1,2,3,4,6)\), а точный счетчик дает
$$ (b_1,b_2,b_3,b_4,b_5)=(1,2,4,6,11). $$
Отсюда
$$ f(5)=2^5-1-(1+2+4+6+11)=31-24=7. $$
Кроме того, C++-валидация проверяет контрольные значения из условия:
$$f(10)=501,\qquad f(25)=18635853.$$
Для целевого входа локальный решатель возвращает
$$f(10^{18}) \equiv 697003956 \pmod{10^9}.$$
Файл на C++ содержит и точный валидатор, и быстрый решатель. ExactCounter вычисляет \(b_n\) через мемоизированный подсчет подмножеств и подтверждает рекуррентность на диапазоне \(n\le 60\). Функция prefix_sum_b_mod сначала обрабатывает восемь базовых значений напрямую, а затем переходит к возведению в степень матрицы \(9\times 9\). Отрицательные коэффициенты рекуррентности перед записью в матрицу перехода нормализуются по модулю \(10^9\). Наконец, solve_mod вычисляет \(2^n \bmod 10^9\), вычитает \(1\) и \(B_n\), а затем снова нормализует результат.
Файлы на Python и Java представляют собой компактные переводы той же быстрой части: те же базовые значения, те же коэффициенты, тот же 9-мерный переход и та же конечная конгруэнция.
Точный валидатор subset-sum используется только на малых \(n\), поэтому на асимптотику основной задачи он не влияет. Рабочий путь выполняет бинарное возведение в степень фиксированной матрицы \(9\times 9\), что дает \(O(9^3\log n)\) по времени при плотном умножении и \(O(9^2)\) по памяти. Поскольку \(9\) является константой, фактически это \(O(\log n)\) времени и постоянный дополнительный объем памяти.
solutionsCpp/Euler382.cppsolutionsPython/Euler382.py и solutionsJava/Euler382.javaتُولَّد أطوال الأضلاع وفق العلاقة
$$s_1=1,\quad s_2=2,\quad s_3=3,\quad s_n=s_{n-1}+s_{n-3}\quad (n\ge 4).$$
وبما أن \(s_{n-3}\gt 0\)، فإن المتتالية تزايدية تزايدًا صارمًا، ولذلك يملك كل جزء من \(\{s_1,\dots,s_n\}\) ضلعًا أعظم وحيدًا. نرمز بـ \(f(n)\) إلى عدد الأجزاء غير الفارغة التي يمكن أن تكوّن مضلعًا غير منعدم. المطلوب هو حساب \(f(10^{18}) \bmod 10^9\).
لمجموعة من الأطوال الموجبة، يوجد مضلع إذا وفقط إذا كان الضلع الأكبر أصغر من مجموع بقية الأضلاع. فإذا كان أكبر ضلع في جزء ما هو \(s_n\)، فإن هذا الجزء يكون سيئًا بالضبط عندما لا يزيد مجموع الأضلاع الأخرى المختارة على \(s_n\).
وهكذا تتحول المسألة الهندسية إلى مسألة عدّ لمجاميع الأجزاء.
نعرف \(b_n\) بأنه عدد الأجزاء من \(\{s_1,\dots,s_{n-1}\}\) التي لا يتجاوز مجموعها \(s_n\):
$$b_n=\#\left\{A\subseteq \{1,\dots,n-1\}:\sum_{i\in A}s_i\le s_n\right\}.$$
كل جزء غير صالح لتكوين مضلع داخل \(\{s_1,\dots,s_n\}\) يملك عنصرًا أعظم وحيدًا هو \(s_k\). وبعد حذف هذا الضلع الأعظم يتبقى جزء يُحسَب تمامًا داخل \(b_k\). لذلك فإن عدد الأجزاء السيئة يساوي \(\sum_{k=1}^{n} b_k\)، ومن ثم
$$\boxed{f(n)=\left(2^n-1\right)-\sum_{k=1}^{n} b_k.}$$
وهذه هي الهوية الأساسية المستخدمة في الملفات الثلاثة للحل.
يُولّد الحل المرجعي بلغة C++ القيم الأولى لـ \(b_n\) بواسطة عدّاد دقيق مع حفظ النتائج. لنعرّف
$$P_i=\sum_{k=1}^{i}s_k,\qquad C(i,L)=\#\left\{A\subseteq \{1,\dots,i\}:\sum_{k\in A}s_k\le L\right\}.$$
العلاقة التراجعية المطبقة في ExactCounter هي
$$ C(i,L)= \begin{cases} 1, & i=0,\\ 2^i, & L\ge P_i,\\ C(i-1,L), & s_i\gt L,\\ C(i-1,L)+C(i-1,L-s_i), & s_i\le L. \end{cases} $$
وعندئذٍ \(b_n=C(n-1,s_n)\). القيم الابتدائية الدقيقة التي ينتجها الكود المحلي هي
$$ (b_1,b_2,b_3,b_4,b_5,b_6,b_7,b_8)=(1,2,4,6,11,20,36,67). $$
وهذه القيم الثماني هي حالة البداية للمحلل السريع.
من السلسلة الدقيقة نحصل على العلاقة الخطية المضمّنة في جميع ملفات الحل:
$$ b_n=3b_{n-1}-2b_{n-2}+2b_{n-3}-5b_{n-4}+b_{n-5}+b_{n-6}+3b_{n-7}-2b_{n-8}, \qquad n\ge 9. $$
برنامج C++ لا يفترض هذه العلاقة افتراضًا مجردًا، بل يعيد حساب \(b_n\) بدقة حتى \(n=60\)، ثم يفحص أن العلاقة صحيحة لكل حد ابتداءً من \(n=9\). لذلك ينبغي التعامل معها هنا على أنها حقيقة موثقة بواسطة الحل المحلي.
نحن لا نحتاج إلى \(b_n\) فقط، بل إلى \(B_n=\sum_{k=1}^{n} b_k\) أيضًا. لذلك يخزن الحل الحالة ذات المركبات التسع
$$ v_n= \begin{bmatrix} b_n\\ b_{n-1}\\ b_{n-2}\\ b_{n-3}\\ b_{n-4}\\ b_{n-5}\\ b_{n-6}\\ b_{n-7}\\ B_n \end{bmatrix}. $$
بوضع معاملات العلاقة في الصف الأول، وإزاحات بسيطة في الصفوف من \(2\) إلى \(8\)، وصفّ تراكمي إضافي في الأسفل، نحصل على
$$v_{n+1}=Tv_n,$$
حيث
$$ T= \begin{bmatrix} 3 & -2 & 2 & -5 & 1 & 1 & 3 & -2 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 3 & -2 & 2 & -5 & 1 & 1 & 3 & -2 & 1 \end{bmatrix}. $$
ومتجه البداية هو
$$ v_8= \begin{bmatrix} 67\\ 36\\ 20\\ 11\\ 6\\ 4\\ 2\\ 1\\ 147 \end{bmatrix}, \qquad 147=1+2+4+6+11+20+36+67. $$
ولكل \(n\gt 8\)، تعطينا الرفعيات الثنائية \(v_n=T^{\,n-8}v_8 \pmod{10^9}\)، وتكون المركبة الأخيرة هي \(B_n\).
بعد معرفة \(B_n\) تصبح الإجابة
$$\boxed{f(n)\equiv 2^n-1-B_n \pmod{10^9}.}$$
ومثال صغير يوضح التفكيك بوضوح. عندما \(n=5\)، تكون المتتالية \((1,2,3,4,6)\)، ويعطي العدّاد الدقيق
$$ (b_1,b_2,b_3,b_4,b_5)=(1,2,4,6,11). $$
ومن ثم
$$ f(5)=2^5-1-(1+2+4+6+11)=31-24=7. $$
كما أن تحقق C++ يختبر قيم المسألة المعروفة
$$f(10)=501,\qquad f(25)=18635853.$$
أما للإدخال الهدف فإن المحلل المحلي يعيد
$$f(10^{18}) \equiv 697003956 \pmod{10^9}.$$
ملف C++ يحتوي على المتحقق الدقيق وعلى المحلل السريع معًا. يقوم ExactCounter بحساب \(b_n\) بواسطة عدّ مجموعات جزئية مع الحفظ، ثم يؤكد صحة العلاقة حتى \(n\le 60\). وتعالج الدالة prefix_sum_b_mod القيم الثماني الأساسية مباشرة، ثم تنتقل إلى رفع مصفوفة \(9\times 9\). وتُطبَّع معاملات العلاقة السالبة بترديد \(10^9\) قبل إدراجها في مصفوفة الانتقال. وفي النهاية تحسب solve_mod القيمة \(2^n \bmod 10^9\)، ثم تطرح \(1\) و\(B_n\)، وتطبّع الناتج.
أما ملفا Python وJava فهما ترجمتان مختصرتان للمسار السريع نفسه: القيم الأساسية نفسها، ومعاملات العلاقة نفسها، وحالة الانتقال ذات الأبعاد التسعة نفسها، والصيغة النهائية نفسها.
المتحقق الدقيق لمجاميع الأجزاء يُستخدم فقط عندما يكون \(n\) صغيرًا، ولذلك لا يغيّر التعقيد الأسيمبتوطي للحساب النهائي. المسار الفعلي ينفذ رفعًا ثنائيًا لمصفوفة ثابتة من الحجم \(9\times 9\)، وبالتالي يكون الزمن \(O(9^3\log n)\) مع ضرب مصفوفي كثيف، والذاكرة \(O(9^2)\). وبما أن \(9\) ثابت، فهذا يعادل عمليًا زمنًا من رتبة \(O(\log n)\) ومساحة مساعدة ثابتة.
solutionsCpp/Euler382.cppsolutionsPython/Euler382.py وsolutionsJava/Euler382.java