We consider hexadecimal integers with at most 16 digits, written in the usual way with no leading zero. The task is to count how many of them contain each of the three distinguished symbols \(0\), \(1\), and \(A\) at least once.
The counting is done length by length. If \(C_n\) denotes the number of valid \(n\)-digit hexadecimal numbers, then the Project Euler instance asks for
$$S=\sum_{n=1}^{16} C_n,$$
and the result is finally displayed in base 16. The main mathematical issue is that the first digit is restricted, so the digits \(0\), \(1\), and \(A\) do not play perfectly symmetric roles.
For a fixed length \(n\), let the universe be all hexadecimal strings of length \(n\) whose first digit is nonzero. Among them we want exactly those that contain all three required symbols. This is a clean inclusion-exclusion problem, but the leading-digit rule changes several of the set sizes and must be handled explicitly.
The first digit can be any of \(1,2,\dots,9,A,\dots,F\), so it has 15 choices. Every remaining position has 16 choices. Therefore
$$T_n = 15 \cdot 16^{n-1}$$
counts all admissible \(n\)-digit hexadecimal numbers before we impose the requirement that \(0\), \(1\), and \(A\) all appear.
Define three events:
$$E_0=\{\text{the digit }0\text{ never appears}\},\qquad E_1=\{\text{the digit }1\text{ never appears}\},\qquad E_A=\{\text{the digit }A\text{ never appears}\}.$$
Then \(C_n\) is the number of elements of the universe that avoid none of these events, so
$$C_n = T_n - |E_0 \cup E_1 \cup E_A|.$$
Inclusion-exclusion expands this into single omissions, double omissions, and the triple omission.
This is the key asymmetry in the problem. If \(0\) is forbidden everywhere, then the leading-digit rule becomes irrelevant, because \(0\) could not have appeared in the first position anyway. But if \(1\) or \(A\) is forbidden, the first digit still cannot be \(0\), so the first position and the later positions must be counted separately.
That gives
$$|E_0| = 15^n,$$
because every position may use any hexadecimal symbol except \(0\). On the other hand,
$$|E_1| = 14 \cdot 15^{n-1},\qquad |E_A| = 14 \cdot 15^{n-1},$$
because the first digit may use any nonzero hexadecimal symbol except the forbidden one, giving 14 choices, while each later position may use any symbol except that forbidden one, giving 15 choices.
Now count numbers missing two of the required symbols at once.
If both \(0\) and \(1\) are absent, the available alphabet has 14 symbols and none of them is zero, so again the leading-digit restriction disappears:
$$|E_0 \cap E_1| = 14^n.$$
Exactly the same reasoning gives
$$|E_0 \cap E_A| = 14^n.$$
If instead \(1\) and \(A\) are absent, zero is still available in later positions but not at the front, so
$$|E_1 \cap E_A| = 13 \cdot 14^{n-1}.$$
Finally, if all three symbols \(0\), \(1\), and \(A\) are absent, only 13 symbols remain and none of them is zero, hence
$$|E_0 \cap E_1 \cap E_A| = 13^n.$$
Substituting all pieces into the inclusion-exclusion formula gives
$$C_n = T_n - (|E_0| + |E_1| + |E_A|) + (|E_0 \cap E_1| + |E_0 \cap E_A| + |E_1 \cap E_A|) - |E_0 \cap E_1 \cap E_A|,$$
so
$$C_n = 15 \cdot 16^{n-1} - \bigl(15^n + 14 \cdot 15^{n-1} + 14 \cdot 15^{n-1}\bigr) + \bigl(14^n + 14^n + 13 \cdot 14^{n-1}\bigr) - 13^n.$$
Combining like terms produces the compact equivalent form
$$C_n = 15 \cdot 16^{n-1} - 43 \cdot 15^{n-1} + 41 \cdot 14^{n-1} - 13^n.$$
Either version is mathematically identical. The implementations follow the unsimplified inclusion-exclusion pieces directly, which keeps the combinatorial meaning visible.
The smallest interesting length is \(n=3\), because a string cannot contain \(0\), \(1\), and \(A\) all at least once unless it has at least three positions. Plugging \(n=3\) into the formula gives
$$C_3 = 15 \cdot 16^2 - 15^3 - 2 \cdot 14 \cdot 15^2 + 2 \cdot 14^3 + 13 \cdot 14^2 - 13^3 = 4.$$
There is also a direct sanity check: with three positions, the digits must be exactly \(0\), \(1\), and \(A\) in some order. There are \(3! = 6\) permutations, but the two starting with \(0\) are invalid, leaving exactly four valid numbers:
$$10A,\qquad 1A0,\qquad A01,\qquad A10.$$
This agrees with the formula and is used by one implementation as a checkpoint.
Different lengths describe disjoint sets of hexadecimal integers, so the final answer is just
$$S = \sum_{n=1}^{16} C_n.$$
Notice that \(C_1=C_2=0\), which the formula automatically reproduces. Because the target bound is only 16 digits, there is no need for a more elaborate recurrence or dynamic program: a short exact sum is already sufficient.
The C++, Python, and Java implementations all evaluate the same length-by-length inclusion-exclusion formula. They iterate over \(n=1,2,\dots,16\), compute the seven ingredient counts for that length, and accumulate the contribution \(C_n\) into a running total.
For each \(n\), the implementation computes the total number of \(n\)-digit hexadecimal numbers, then the counts missing \(0\), missing \(1\), missing \(A\), missing each pair, and missing all three. No search tree, digit DP, or memoization is needed; everything comes from direct power expressions such as \(16^{n-1}\), \(15^n\), \(14^n\), and \(13^n\).
The three language versions differ only in the integer type used for exact arithmetic. Python relies on built-in arbitrary precision, Java uses arbitrary-precision integers explicitly, and C++ uses a fixed-width integer type large enough for this range.
After summing all \(C_n\), the implementation converts the final integer to uppercase hexadecimal for printing. One version also verifies the small fact \(C_3=4\) before producing the answer, which is a useful check that the inclusion-exclusion terms were assembled correctly.
Conceptually, the code is just a faithful transcription of the mathematical formula: count each forbidden pattern, combine them with signs \(+\,-\,+\,-\), then add the lengths together.
For each length \(n\), the solver performs a constant amount of arithmetic, so if the maximum length is \(L\), the running time is \(O(L)\). In the Project Euler instance \(L=16\), this is effectively constant time.
The memory usage is \(O(1)\) beyond the storage required by the final integer itself. There are no large tables, no recursion stack, and no dependence on the number of valid hexadecimal strings. The only growth comes from exact integer arithmetic, which remains very small for this problem size.
Gesucht ist die Anzahl der Hexadezimalzahlen mit höchstens 16 Stellen, die keine führende Null besitzen und die Ziffern beziehungsweise Symbole \(0\), \(1\) und \(A\) jeweils mindestens einmal enthalten.
Die Zählung wird nach Stellenlängen getrennt durchgeführt. Bezeichnet \(C_n\) die Zahl der gültigen \(n\)-stelligen Hexadezimalzahlen, dann lautet die gesuchte Größe
$$S=\sum_{n=1}^{16} C_n.$$
Am Ende wird das Ergebnis selbst wieder im Hexadezimalsystem ausgegeben. Der eigentliche mathematische Kern ist die asymmetrische Rolle der ersten Stelle: Wegen des Verbots führender Nullen verhalten sich \(0\), \(1\) und \(A\) beim Zählen nicht völlig gleich.
Für eine feste Länge \(n\) betrachten wir alle Hexadezimalstrings der Länge \(n\), deren erste Stelle ungleich Null ist. Unter diesen wollen wir genau die zählen, in denen alle drei geforderten Symbole vorkommen. Das ist ein klassisches Inklusions-Exklusions-Problem, aber die erste Stelle muss ausdrücklich mitbehandelt werden.
Für die erste Stelle sind nur die 15 nichtnulligen Hexadezimalsymbole erlaubt. Jede weitere Stelle hat 16 Möglichkeiten. Daher ist die Gesamtzahl aller zulässigen \(n\)-stelligen Hexadezimalzahlen
$$T_n = 15 \cdot 16^{n-1}.$$
Das ist die Ausgangsmenge, bevor wir verlangen, dass \(0\), \(1\) und \(A\) tatsächlich auftreten.
Wir definieren
$$E_0=\{\text{\(0\) kommt gar nicht vor}\},\qquad E_1=\{\text{\(1\) kommt gar nicht vor}\},\qquad E_A=\{\text{\(A\) kommt gar nicht vor}\}.$$
Dann zählt \(C_n\) genau die Elemente der Grundmenge, die in keinem dieser drei Ereignisse liegen. Also gilt
$$C_n = T_n - |E_0 \cup E_1 \cup E_A|.$$
Inklusions-Exklusions zerlegt diesen Ausdruck in Beiträge, bei denen ein Symbol fehlt, zwei Symbole fehlen oder alle drei fehlen.
Hier steckt die eigentliche Feinheit. Wenn \(0\) an allen Stellen verboten ist, dann spielt die Regel „keine führende Null“ keine zusätzliche Rolle mehr, denn \(0\) dürfte ohnehin nirgendwo stehen. Wenn dagegen \(1\) oder \(A\) verboten ist, bleibt \(0\) in den späteren Stellen erlaubt, aber nicht an erster Stelle. Deshalb muss man Anfangsposition und Restpositionen unterscheiden.
Man erhält damit
$$|E_0| = 15^n,$$
denn an jeder Stelle darf jedes Hexadezimalsymbol außer \(0\) stehen. Dagegen gilt
$$|E_1| = 14 \cdot 15^{n-1},\qquad |E_A| = 14 \cdot 15^{n-1},$$
weil die erste Stelle jedes von Null verschiedene Symbol außer dem verbotenen wählen darf, also 14 Möglichkeiten besitzt, während jede spätere Stelle 15 Möglichkeiten hat.
Jetzt zählen wir die Schnittmengen der verbotenen Ereignisse.
Wenn sowohl \(0\) als auch \(1\) fehlen, bleiben 14 Symbole übrig und keines davon ist Null. Damit verschwindet die Führungsbeschränkung erneut:
$$|E_0 \cap E_1| = 14^n.$$
Analog folgt
$$|E_0 \cap E_A| = 14^n.$$
Wenn hingegen \(1\) und \(A\) fehlen, bleibt \(0\) für spätere Stellen erlaubt, aber nicht für die erste. Deshalb
$$|E_1 \cap E_A| = 13 \cdot 14^{n-1}.$$
Fehlen schließlich alle drei Symbole \(0\), \(1\) und \(A\), so bleiben 13 Symbole übrig und keines ist Null, also
$$|E_0 \cap E_1 \cap E_A| = 13^n.$$
Durch Einsetzen ergibt sich
$$C_n = T_n - (|E_0| + |E_1| + |E_A|) + (|E_0 \cap E_1| + |E_0 \cap E_A| + |E_1 \cap E_A|) - |E_0 \cap E_1 \cap E_A|,$$
also konkret
$$C_n = 15 \cdot 16^{n-1} - \bigl(15^n + 14 \cdot 15^{n-1} + 14 \cdot 15^{n-1}\bigr) + \bigl(14^n + 14^n + 13 \cdot 14^{n-1}\bigr) - 13^n.$$
Zusammengefasst ist das äquivalent zu
$$C_n = 15 \cdot 16^{n-1} - 43 \cdot 15^{n-1} + 41 \cdot 14^{n-1} - 13^n.$$
Die Implementierungen verwenden die ungekürzte Form, weil dort unmittelbar sichtbar bleibt, welcher Term welchem verbotenen Ereignis entspricht.
Die kleinste nichttriviale Länge ist \(n=3\), denn erst ab drei Stellen können \(0\), \(1\) und \(A\) überhaupt alle vorkommen. Die Formel liefert
$$C_3 = 15 \cdot 16^2 - 15^3 - 2 \cdot 14 \cdot 15^2 + 2 \cdot 14^3 + 13 \cdot 14^2 - 13^3 = 4.$$
Man kann das direkt kontrollieren: Bei drei Stellen müssen die Symbole genau \(0\), \(1\) und \(A\) in irgendeiner Reihenfolge sein. Von den \(3! = 6\) Permutationen beginnen zwei mit \(0\) und sind damit ungültig. Übrig bleiben genau
$$10A,\qquad 1A0,\qquad A01,\qquad A10.$$
Diese Viererprobe eignet sich hervorragend als Plausibilitätskontrolle und wird in einer der Implementierungen auch tatsächlich verwendet.
Unterschiedliche Stellenlängen beschreiben disjunkte Mengen von Zahlen. Daher erhält man die Gesamtlösung einfach durch
$$S = \sum_{n=1}^{16} C_n.$$
Dabei gilt automatisch \(C_1=C_2=0\). Weil die Obergrenze nur 16 beträgt, braucht man weder eine Rekursion noch ein aufwendiges dynamisches Programm; die exakte direkte Summe ist bereits vollständig ausreichend.
Die C++-, Python- und Java-Implementierungen setzen genau diese Inklusions-Exklusions-Zählung um. Sie laufen die Längen \(n=1,2,\dots,16\) nacheinander durch, berechnen für jede Länge die sieben Grundterme und addieren den jeweiligen Beitrag \(C_n\) zu einer Gesamtsumme.
Für jedes \(n\) werden zuerst die Potenzen \(16^{n-1}\), \(15^n\), \(15^{n-1}\), \(14^n\), \(14^{n-1}\) und \(13^n\) ausgewertet. Daraus entstehen unmittelbar die Gesamtzahl, die drei Einzelverbote, die drei Doppelverbote und das Dreifachverbot. Es gibt also weder Backtracking noch Digit-DP noch Zustandsgraphen; die gesamte Arbeit ist reine exakte Ganzzahlarithmetik.
Die drei Sprachen unterscheiden sich nur in der Wahl des Zahlentyps. Python benutzt eingebaute beliebig große Ganzzahlen, Java verwendet explizit Ganzzahlen mit beliebiger Präzision, und C++ nutzt einen festen breiten Ganzzahltyp, der für diesen Wertebereich ausreicht.
Nachdem alle \(C_n\) addiert wurden, wird die Gesamtsumme als Hexadezimalzahl in Großbuchstaben ausgegeben. Eine Implementierung prüft vorher noch den bekannten Spezialfall \(C_3=4\), um sicherzustellen, dass die Vorzeichen und Teilmengen korrekt zusammengesetzt wurden.
Inhaltlich ist der Code damit fast eine wörtliche Übersetzung der Herleitung: Zähle die verbotenen Fälle, kombiniere sie mit dem Muster \(+\,-\,+\,-\), und summiere anschließend über alle Stellenlängen.
Für jede Länge wird nur eine konstante Anzahl arithmetischer Operationen durchgeführt. Bei einer maximalen Länge \(L\) beträgt die Laufzeit also \(O(L)\). Für die konkrete Aufgabenstellung mit \(L=16\) ist das faktisch konstante Zeit.
Der Speicherverbrauch ist \(O(1)\), abgesehen von dem Platz, den die exakte Ganzzahldarstellung der Endsumme selbst benötigt. Es werden keine großen Tabellen gespeichert und keine rekursiven Zwischenzustände aufgebaut. Der Ansatz ist deshalb sowohl mathematisch sauber als auch implementatorisch äußerst direkt.
En fazla 16 basamaklı, başında sıfır bulunmayan onaltılık sayılar içinde \(0\), \(1\) ve \(A\) sembollerinin her birini en az bir kez içerenlerin sayısı aranıyor.
Uzunluğu tam \(n\) olan geçerli sayıların sayısını \(C_n\) ile gösterirsek istenen toplam
$$S=\sum_{n=1}^{16} C_n$$
olur. Sonuç onaltılık tabanda yazdırılır. Matematiksel açıdan belirleyici nokta, ilk basamağın sıfır olamaması yüzünden \(0\), \(1\) ve \(A\) için eksik olma durumlarının aynı biçimde sayılmamasıdır.
Sabit bir \(n\) için evreni, ilk basamağı sıfır olmayan bütün \(n\) basamaklı onaltılık diziler olarak alalım. Bu evrenden, üç zorunlu sembolün de en az bir kez göründüğü dizileri seçmek istiyoruz. Tam olarak buna uygun araç dahil etme-çıkarma ilkesidir; ancak ilk basamak kısıtı yüzünden terimleri dikkatle saymak gerekir.
İlk basamak için sıfır dışındaki 15 onaltılık sembolden biri seçilebilir. Geri kalan her basamak için 16 seçenek vardır. Dolayısıyla toplam aday sayısı
$$T_n = 15 \cdot 16^{n-1}$$
olur. Bu, henüz \(0\), \(1\) ve \(A\)'nın görünmesini zorlamadan önceki başlangıç sayımıdır.
Şimdi şu olayları tanımlayalım:
$$E_0=\{\text{\(0\) hiç görünmüyor}\},\qquad E_1=\{\text{\(1\) hiç görünmüyor}\},\qquad E_A=\{\text{\(A\) hiç görünmüyor}\}.$$
Aradığımız \(C_n\), bu üç olayın hiçbirine düşmeyen dizilerin sayısıdır. Bu yüzden
$$C_n = T_n - |E_0 \cup E_1 \cup E_A|$$
yazılır. Dahil etme-çıkarma ilkesi bunu tek tek eksik olma, iki sembolün birlikte eksik olması ve üçünün birden eksik olması şeklinde açar.
Problemin asıl inceliği budur. Eğer \(0\) tamamen yasaksa, “ilk basamak sıfır olamaz” şartı artık ekstra bir kısıt getirmez; çünkü \(0\) zaten hiçbir yerde kullanılamaz. Fakat \(1\) ya da \(A\) yasak olduğunda, \(0\) sonraki basamaklarda hâlâ kullanılabilir ama ilk basamakta kullanılamaz. Bu yüzden ilk konum ile diğer konumları ayırmak gerekir.
Böylece
$$|E_0| = 15^n$$
elde edilir; çünkü her basamakta \(0\) dışındaki 15 sembolden biri seçilir. Buna karşılık
$$|E_1| = 14 \cdot 15^{n-1},\qquad |E_A| = 14 \cdot 15^{n-1}$$
olur; çünkü ilk basamak için sıfır dışındaki 15 sembolden yasak olan çıkarılınca 14 seçenek kalır, geri kalan her yerde ise yasak sembol dışındaki 15 seçenek kullanılabilir.
Şimdi kesişim terimlerini sayalım.
Eğer hem \(0\) hem \(1\) yoksa geriye 14 sembol kalır ve bunların hiçbiri sıfır değildir; bu nedenle baştaki sıfır yasağı otomatik olarak sağlanır:
$$|E_0 \cap E_1| = 14^n.$$
Aynı mantıkla
$$|E_0 \cap E_A| = 14^n$$
bulunur. Ama \(1\) ve \(A\) birlikte eksikse \(0\) hâlâ vardır; yalnızca ilk basamakta kullanılamaz. Dolayısıyla
$$|E_1 \cap E_A| = 13 \cdot 14^{n-1}$$
olur. Son olarak üç sembolün de hiç görünmediği durumda sadece 13 sembol kalır ve bunların içinde \(0\) da bulunmaz:
$$|E_0 \cap E_1 \cap E_A| = 13^n.$$
Bu sayımları yerleştirince
$$C_n = T_n - (|E_0| + |E_1| + |E_A|) + (|E_0 \cap E_1| + |E_0 \cap E_A| + |E_1 \cap E_A|) - |E_0 \cap E_1 \cap E_A|$$
elde edilir. Açık yazarsak
$$C_n = 15 \cdot 16^{n-1} - \bigl(15^n + 14 \cdot 15^{n-1} + 14 \cdot 15^{n-1}\bigr) + \bigl(14^n + 14^n + 13 \cdot 14^{n-1}\bigr) - 13^n.$$
İstenirse bu ifade
$$C_n = 15 \cdot 16^{n-1} - 43 \cdot 15^{n-1} + 41 \cdot 14^{n-1} - 13^n$$
şeklinde sadeleştirilebilir. Fakat uygulamalar, kombinatoryal anlam daha açık kalsın diye terimleri ayrı ayrı hesaplar.
İlk anlamlı uzunluk \(n=3\)'tür; çünkü üç farklı zorunlu sembolün hepsi ancak üç veya daha fazla basamakta yer alabilir. Formüle \(n=3\) koyarsak
$$C_3 = 15 \cdot 16^2 - 15^3 - 2 \cdot 14 \cdot 15^2 + 2 \cdot 14^3 + 13 \cdot 14^2 - 13^3 = 4$$
çıkar. Bu sonuç elle de görülebilir: üç basamaklı bir sayıda \(0\), \(1\) ve \(A\) her biri en az bir kez bulunacaksa, basamaklar tam olarak bu üç sembolün bir permütasyonu olmalıdır. Toplam \(3! = 6\) permütasyon vardır; başta \(0\) olan iki tanesi geçersizdir. Geriye tam olarak
$$10A,\qquad 1A0,\qquad A01,\qquad A10$$
kalır. Bir uygulamanın kullandığı küçük doğrulama da tam olarak bu örnektir.
Farklı basamak sayıları ayrık sayı kümeleri verdiği için toplam çözüm doğrudan
$$S = \sum_{n=1}^{16} C_n$$
şeklindedir. Burada \(C_1=C_2=0\) olması formülden zaten otomatik çıkar. Üst sınır yalnızca 16 olduğu için ayrıca bir özyineleme ya da durum tabanlı dinamik program kurmaya gerek yoktur; kısa ve tam bir toplam yeterlidir.
C++, Python ve Java uygulamaları aynı uzunluk-bazlı dahil etme-çıkarma hesabını yapar. Her biri \(n=1\)'den \(16\)'ya kadar gider, ilgili uzunluk için toplam aday sayısını ve tüm yasak olay sayılarını hesaplar, sonra bunları doğru işaretlerle birleştirip \(C_n\)'yi genel toplama ekler.
Her adımda \(16^{n-1}\), \(15^n\), \(15^{n-1}\), \(14^n\), \(14^{n-1}\) ve \(13^n\) gibi kuvvetler hesaplanır. Ardından bunlardan tek tek eksik durumlar, ikili eksik durumlar ve üçlü eksik durum kurulup dahil etme-çıkarma uygulanır. Yani çözümde arama, geri izleme, dijit DP ya da durum geçiş tablosu yoktur; yalnızca doğrudan tam sayı aritmetiği vardır.
Diller arasındaki fark sadece sayısal gösterimdedir. Python yerleşik büyük tamsayıları kullanır, Java keyfi hassasiyetli tamsayılarla çalışır, C++ ise bu aralık için yeterli genişlikte sabit boyutlu bir tamsayı türü kullanır.
Bütün \(C_n\) terimleri toplandıktan sonra sonuç büyük harfli onaltılık biçime çevrilir ve yazdırılır. Sürümlerden biri ayrıca \(C_3=4\) bilgisini kontrol ederek küçük bir güven testi yapar; bu, işaretlerin ve terimlerin doğru kurulduğunu gösterir.
Özetle kod, matematiksel türetmenin neredeyse doğrudan bir tercümesidir: yasak durumları say, dahil etme-çıkarma ile birleştir, sonra bütün uzunluklar için topla.
Maksimum uzunluk \(L\) ise her uzunluk için sabit sayıda işlem yapıldığından çalışma süresi \(O(L)\) olur. Bu problemde \(L=16\) olduğundan pratikte sabit zamanlıdır.
Bellek kullanımı, sonucun kendisini tutmak için gereken tam sayı saklama maliyeti dışında \(O(1)\)'dir. Büyük tablolar, önbellek yapıları veya derin özyineleme yoktur. Bu nedenle çözüm hem yalın hem de son derece doğrudandır.
Se quiere contar cuántos enteros hexadecimales de hasta 16 dígitos, escritos sin cero inicial, contienen cada uno de los símbolos \(0\), \(1\) y \(A\) al menos una vez.
Si \(C_n\) representa la cantidad de números hexadecimales válidos con exactamente \(n\) dígitos, entonces el valor buscado es
$$S=\sum_{n=1}^{16} C_n.$$
El resultado final se muestra en hexadecimal. La dificultad combinatoria real está en que la primera posición tiene una restricción especial, de modo que “falta \(0\)” no se cuenta igual que “falta \(1\)” o “falta \(A\)”.
Para una longitud fija \(n\), tomamos como universo todas las cadenas hexadecimales de longitud \(n\) cuya primera cifra no es cero. Dentro de ese universo queremos las que contienen los tres símbolos obligatorios. La herramienta natural es el principio de inclusión-exclusión, pero hay que aplicarlo teniendo en cuenta la asimetría de la primera posición.
La primera posición admite cualquiera de los 15 símbolos hexadecimales no nulos. Cada posición restante admite 16 símbolos. Por tanto, el número total de candidatos es
$$T_n = 15 \cdot 16^{n-1}.$$
Ese es el conjunto de partida antes de exigir la presencia de \(0\), \(1\) y \(A\).
Definimos
$$E_0=\{\text{no aparece el dígito }0\},\qquad E_1=\{\text{no aparece el dígito }1\},\qquad E_A=\{\text{no aparece el dígito }A\}.$$
Entonces \(C_n\) es el número de elementos del universo que no pertenecen a ninguno de esos eventos. En consecuencia,
$$C_n = T_n - |E_0 \cup E_1 \cup E_A|.$$
Ahora expandimos esa unión con inclusión-exclusión.
Si el símbolo prohibido es \(0\), la restricción de “no empezar con cero” deja de importar, porque el \(0\) ya está excluido en todas las posiciones. En cambio, si el símbolo prohibido es \(1\) o \(A\), el \(0\) sigue siendo válido en posiciones internas pero no en la primera. Por eso esas cuentas no tienen la misma forma.
Obtenemos
$$|E_0| = 15^n,$$
ya que en cada posición puede elegirse cualquiera de los 15 símbolos distintos de \(0\). Por otra parte,
$$|E_1| = 14 \cdot 15^{n-1},\qquad |E_A| = 14 \cdot 15^{n-1},$$
porque en la primera posición se puede usar cualquier símbolo no nulo salvo el prohibido, es decir 14 opciones, mientras que en las demás hay 15 opciones.
Pasemos a las intersecciones.
Si faltan \(0\) y \(1\), el alfabeto disponible tiene 14 símbolos y ninguno es cero, así que la condición del primer dígito ya está incorporada:
$$|E_0 \cap E_1| = 14^n.$$
Del mismo modo,
$$|E_0 \cap E_A| = 14^n.$$
Si faltan \(1\) y \(A\), el cero sigue disponible fuera de la primera posición, por lo que
$$|E_1 \cap E_A| = 13 \cdot 14^{n-1}.$$
Por último, si faltan a la vez \(0\), \(1\) y \(A\), quedan 13 símbolos y ninguno es cero:
$$|E_0 \cap E_1 \cap E_A| = 13^n.$$
Sustituyendo todo en la identidad general obtenemos
$$C_n = T_n - (|E_0| + |E_1| + |E_A|) + (|E_0 \cap E_1| + |E_0 \cap E_A| + |E_1 \cap E_A|) - |E_0 \cap E_1 \cap E_A|,$$
es decir,
$$C_n = 15 \cdot 16^{n-1} - \bigl(15^n + 14 \cdot 15^{n-1} + 14 \cdot 15^{n-1}\bigr) + \bigl(14^n + 14^n + 13 \cdot 14^{n-1}\bigr) - 13^n.$$
Al simplificar los coeficientes se obtiene la forma compacta
$$C_n = 15 \cdot 16^{n-1} - 43 \cdot 15^{n-1} + 41 \cdot 14^{n-1} - 13^n.$$
Las implementaciones prefieren la forma expandida porque refleja de manera directa qué término corresponde a qué conjunto prohibido.
La primera longitud no trivial es \(n=3\), ya que antes no caben los tres símbolos obligatorios. Sustituyendo \(n=3\) en la fórmula:
$$C_3 = 15 \cdot 16^2 - 15^3 - 2 \cdot 14 \cdot 15^2 + 2 \cdot 14^3 + 13 \cdot 14^2 - 13^3 = 4.$$
También puede verse sin fórmulas: con tres posiciones, la cadena debe ser exactamente una permutación de \(0\), \(1\) y \(A\). Hay \(3! = 6\) permutaciones, pero dos empiezan con \(0\) y no representan un número hexadecimal válido. Quedan exactamente
$$10A,\qquad 1A0,\qquad A01,\qquad A10.$$
Ese ejemplo concreto es una comprobación excelente y una de las implementaciones lo usa como verificación.
Las colecciones de números con distinta longitud son disjuntas, así que la respuesta total es simplemente
$$S = \sum_{n=1}^{16} C_n.$$
De hecho, la fórmula ya produce \(C_1=C_2=0\). Como el límite superior es sólo 16, no hace falta recurrencia ni programación dinámica compleja: una suma exacta de 16 términos basta por completo.
Las implementaciones en C++, Python y Java evalúan exactamente la misma fórmula de inclusión-exclusión. Recorren \(n=1,2,\dots,16\), calculan para cada longitud el total y los siete conteos auxiliares, y luego añaden la contribución correspondiente a la suma acumulada.
En cada iteración se evalúan potencias como \(16^{n-1}\), \(15^n\), \(14^n\) y \(13^n\), de las cuales salen los conteos de números que omiten uno, dos o los tres símbolos requeridos. No hay exploración de casos dígito por dígito ni tablas de estados; el algoritmo es enteramente algebraico.
La única diferencia práctica entre lenguajes es el tipo numérico. Python usa enteros de precisión arbitraria incorporados, Java emplea enteros arbitrariamente grandes, y C++ usa un entero fijo suficientemente amplio para este rango.
Al final se suma todo y se convierte el total a hexadecimal en mayúsculas para imprimirlo. Una de las versiones comprueba antes el caso pequeño \(C_3=4\), lo cual ayuda a confirmar que las señales de inclusión-exclusión y las potencias asociadas son correctas.
Desde el punto de vista conceptual, el programa es una traducción directa de la derivación matemática: contar eventos prohibidos, combinarlos con los signos adecuados y sumar sobre las longitudes.
Si la longitud máxima es \(L\), el tiempo de ejecución es \(O(L)\), porque para cada \(n\) sólo se hace una cantidad constante de operaciones aritméticas. En este problema concreto, con \(L=16\), eso equivale a tiempo esencialmente constante.
El uso de memoria es \(O(1)\), salvo el espacio necesario para almacenar el entero final con exactitud. No se construyen tablas grandes ni estructuras auxiliares proporcionales al número de casos válidos.
题目要求统计所有长度不超过 16 位、首位不能为 \(0\) 的十六进制整数，其中必须至少各出现一次符号 \(0\)、\(1\) 和 \(A\)。
设恰好有 \(n\) 位的合法十六进制数个数为 \(C_n\)，那么目标就是计算
$$S=\sum_{n=1}^{16} C_n.$$
最后答案以十六进制形式输出。真正的数学难点在于首位限制打破了对称性：缺少 \(0\) 的情况，与缺少 \(1\) 或缺少 \(A\) 的情况，并不能用完全相同的公式来数。
固定一个长度 \(n\)。我们先看所有首位非零的 \(n\) 位十六进制串，然后从中挑出同时包含 \(0\)、\(1\)、\(A\) 的那些。这个结构非常适合用容斥原理处理，但必须把“首位不能为零”这一条件完整地带进每个子计数中。
第一位只能从 15 个非零十六进制符号中选择，即 \(1\) 到 \(9\) 以及 \(A\) 到 \(F\)。后面的每一位都有 16 种选择。因此总数为
$$T_n = 15 \cdot 16^{n-1}.$$
这只是候选集合，还没有要求 \(0\)、\(1\)、\(A\) 必须出现。
定义三个坏事件：
$$E_0=\{\text{数字 }0\text{ 从未出现}\},\qquad E_1=\{\text{数字 }1\text{ 从未出现}\},\qquad E_A=\{\text{数字 }A\text{ 从未出现}\}.$$
我们要求的 \(C_n\)，就是候选集合中不落入这三个坏事件并集的元素个数，也就是
$$C_n = T_n - |E_0 \cup E_1 \cup E_A|.$$
接下来用容斥原理把这个并集拆开。
这是整道题最关键的细节。如果 \(0\) 在所有位置都不允许出现，那么“首位不能为 \(0\)”这个限制就自动满足了，因为 \(0\) 压根不在可选字符中。可是如果禁止的是 \(1\) 或 \(A\)，那么 \(0\) 仍然可以出现在后续位置，只是首位依然不能取 \(0\)。因此首位和后面的位数目必须分开处理。
由此得到
$$|E_0| = 15^n,$$
因为每一位都可以从除 \(0\) 以外的 15 个符号中选。另一方面，
$$|E_1| = 14 \cdot 15^{n-1},\qquad |E_A| = 14 \cdot 15^{n-1},$$
因为首位既不能是 \(0\)，也不能是被禁止的那个符号，所以只有 14 种选择；其余位置只需要避开被禁止的符号，因此有 15 种选择。
现在计算交集项。
如果 \(0\) 和 \(1\) 都没有出现，那么可用字符只剩 14 个，而且这些字符里没有 \(0\)，所以首位限制再次自动满足：
$$|E_0 \cap E_1| = 14^n.$$
同理，
$$|E_0 \cap E_A| = 14^n.$$
如果缺少的是 \(1\) 和 \(A\)，那么 \(0\) 仍然可以出现在后面的位，但首位依旧不能为 \(0\)，于是
$$|E_1 \cap E_A| = 13 \cdot 14^{n-1}.$$
最后，如果 \(0\)、\(1\)、\(A\) 三个符号都完全没有出现，那么只剩下 13 个可用符号，且其中没有 \(0\)，因此
$$|E_0 \cap E_1 \cap E_A| = 13^n.$$
把这些项全部代入容斥原理，得到
$$C_n = T_n - (|E_0| + |E_1| + |E_A|) + (|E_0 \cap E_1| + |E_0 \cap E_A| + |E_1 \cap E_A|) - |E_0 \cap E_1 \cap E_A|.$$
展开后就是
$$C_n = 15 \cdot 16^{n-1} - \bigl(15^n + 14 \cdot 15^{n-1} + 14 \cdot 15^{n-1}\bigr) + \bigl(14^n + 14^n + 13 \cdot 14^{n-1}\bigr) - 13^n.$$
如果把同类项合并，也可以写成更紧凑的形式
$$C_n = 15 \cdot 16^{n-1} - 43 \cdot 15^{n-1} + 41 \cdot 14^{n-1} - 13^n.$$
两种写法完全等价。实现中保留展开式，是因为那样更容易看出每一项对应哪一种“缺少某些符号”的情况。
最小的非平凡长度是 \(n=3\)，因为只有 3 个位置或更多时，\(0\)、\(1\)、\(A\) 才可能都至少出现一次。把 \(n=3\) 代入公式，得到
$$C_3 = 15 \cdot 16^2 - 15^3 - 2 \cdot 14 \cdot 15^2 + 2 \cdot 14^3 + 13 \cdot 14^2 - 13^3 = 4.$$
这个结果也可以直接手算。三位数若要同时含有 \(0\)、\(1\)、\(A\)，那么三位只能恰好是这三个符号的一个排列。总共有 \(3! = 6\) 个排列，其中两种以 \(0\) 开头，不是合法的三位十六进制整数，因此只剩下
$$10A,\qquad 1A0,\qquad A01,\qquad A10.$$
这四个例子既说明公式是对的，也说明了为什么代码里有一个很小的校验点可以选在这里。
不同位数的十六进制整数彼此不重叠，所以总答案只是简单求和：
$$S = \sum_{n=1}^{16} C_n.$$
其中 \(C_1=C_2=0\)，公式会自动给出这个结果。由于上界只有 16，这里根本不需要复杂递推、状态压缩或数位 DP；直接逐个长度精确相加已经足够。
C++、Python 和 Java 实现都严格按照上面的容斥公式逐长度计算。它们从 \(n=1\) 循环到 \(16\)，在每一步求出总候选数、缺少单个符号的数量、缺少两个符号的数量，以及缺少三个符号的数量，然后组合成 \(C_n\) 并累加到总和中。
实现里真正做的事情，就是计算若干个幂：例如 \(16^{n-1}\)、\(15^n\)、\(15^{n-1}\)、\(14^n\)、\(14^{n-1}\)、\(13^n\)。这些值一旦得到，所有容斥项都能直接写出来。整个算法没有搜索过程，没有记忆化递归，也没有状态转移表；它是纯粹的精确整数运算。
三种语言之间的差别只在数值类型上。Python 直接使用内建大整数，Java 使用任意精度整数类，C++ 则使用对本题范围足够宽的定长整数类型。
所有 \(C_n\) 相加完成后，最终总数会被转成大写十六进制字符串输出。其中一个实现还会先检查小规模事实 \(C_3=4\)，用来确认容斥项及其正负号没有写错。
因此，从概念上说，代码几乎就是数学推导的直接翻译：先数坏事件，再按容斥原理合并，最后对所有长度求和。
若最大位数为 \(L\)，则总时间复杂度是 \(O(L)\)，因为每个 \(n\) 只做常数次幂运算和加减法。对本题的 \(L=16\) 来说，这实际上就是常数时间。
空间复杂度是 \(O(1)\)，除了保存最终整数本身所需要的空间之外，不需要任何与 \(L\) 或合法数字总数成比例的大型数据结构。整个方法既短小又非常稳定。
Нужно посчитать все шестнадцатеричные числа длины не более 16 символов без ведущего нуля, в записи которых символы \(0\), \(1\) и \(A\) встречаются хотя бы по одному разу.
Если через \(C_n\) обозначить число допустимых шестнадцатеричных чисел ровно из \(n\) разрядов, то искомая величина равна
$$S=\sum_{n=1}^{16} C_n.$$
В конце результат выводится в шестнадцатеричной форме. Главная тонкость задачи в том, что ограничение на первый символ разрушает симметрию: отсутствие \(0\) считается иначе, чем отсутствие \(1\) или \(A\).
Зафиксируем длину \(n\). Рассмотрим все шестнадцатеричные строки длины \(n\), у которых первый символ не равен нулю. Среди них нужно оставить только те, где присутствуют все три обязательных символа. Это естественно решается принципом включения-исключения, но первый разряд нужно учитывать явно во всех подзадачах подсчета.
В первом разряде можно поставить любой из 15 ненулевых шестнадцатеричных символов. В каждом последующем разряде возможно 16 вариантов. Поэтому
$$T_n = 15 \cdot 16^{n-1}$$
есть общее число допустимых \(n\)-разрядных записей до наложения условия о наличии \(0\), \(1\) и \(A\).
Введем события
$$E_0=\{\text{символ }0\text{ вообще не встречается}\},\qquad E_1=\{\text{символ }1\text{ вообще не встречается}\},\qquad E_A=\{\text{символ }A\text{ вообще не встречается}\}.$$
Тогда \(C_n\) равно числу элементов универсального множества, не попавших ни в одно из этих событий. Следовательно,
$$C_n = T_n - |E_0 \cup E_1 \cup E_A|.$$
Остается раскрыть объединение по формуле включения-исключения.
Это центральный комбинаторный момент. Если цифра \(0\) запрещена во всех позициях, то условие «нет ведущего нуля» автоматически выполняется и отдельно учитывать первую позицию уже не нужно. Но если запрещена цифра \(1\) или \(A\), то ноль по-прежнему разрешен во внутренних позициях, хотя на первом месте он все равно невозможен. Поэтому первая позиция и остальные позиции считаютcя по-разному.
Отсюда
$$|E_0| = 15^n,$$
поскольку в каждой позиции можно выбрать любой из 15 символов, кроме нуля. А для двух других событий получаем
$$|E_1| = 14 \cdot 15^{n-1},\qquad |E_A| = 14 \cdot 15^{n-1},$$
потому что в первом разряде доступны 14 ненулевых символов, кроме запрещенного, а в каждом последующем разряде доступны 15 символов.
Теперь рассмотрим пересечения.
Если отсутствуют и \(0\), и \(1\), то остается 14 символов, среди которых нет нуля, поэтому ограничение на первый разряд снова исчезает:
$$|E_0 \cap E_1| = 14^n.$$
Точно так же
$$|E_0 \cap E_A| = 14^n.$$
Если же отсутствуют \(1\) и \(A\), то ноль еще может стоять в хвосте, но не в начале, значит
$$|E_1 \cap E_A| = 13 \cdot 14^{n-1}.$$
Наконец, при отсутствии \(0\), \(1\) и \(A\) одновременно остается 13 символов, и нуля среди них нет, поэтому
$$|E_0 \cap E_1 \cap E_A| = 13^n.$$
Подставляя все подсчитанные мощности, получаем
$$C_n = T_n - (|E_0| + |E_1| + |E_A|) + (|E_0 \cap E_1| + |E_0 \cap E_A| + |E_1 \cap E_A|) - |E_0 \cap E_1 \cap E_A|,$$
то есть
$$C_n = 15 \cdot 16^{n-1} - \bigl(15^n + 14 \cdot 15^{n-1} + 14 \cdot 15^{n-1}\bigr) + \bigl(14^n + 14^n + 13 \cdot 14^{n-1}\bigr) - 13^n.$$
После объединения подобных членов получается компактная эквивалентная форма
$$C_n = 15 \cdot 16^{n-1} - 43 \cdot 15^{n-1} + 41 \cdot 14^{n-1} - 13^n.$$
В реализациях используется развернутая версия, потому что в ней проще увидеть связь каждого слагаемого с конкретным запрещенным событием.
Минимальная нетривиальная длина равна \(3\), так как только в трех или более позициях могут одновременно появиться \(0\), \(1\) и \(A\). Подстановка дает
$$C_3 = 15 \cdot 16^2 - 15^3 - 2 \cdot 14 \cdot 15^2 + 2 \cdot 14^3 + 13 \cdot 14^2 - 13^3 = 4.$$
Это легко проверить вручную. При трех позициях запись должна быть просто перестановкой символов \(0\), \(1\) и \(A\). Всего есть \(3! = 6\) перестановок, но две из них начинаются с нуля и потому не являются допустимыми числами. Остаются ровно
$$10A,\qquad 1A0,\qquad A01,\qquad A10.$$
Этот пример особенно полезен как контрольная точка; одна из реализаций действительно проверяет именно этот факт.
Числа разной длины принадлежат непересекающимся множествам, поэтому итоговый ответ выражается простой суммой
$$S = \sum_{n=1}^{16} C_n.$$
Заметим, что формула автоматически дает \(C_1=C_2=0\). Так как верхняя граница всего 16, никакая более сложная рекурсия или цифровая динамика здесь не нужна: достаточно прямого точного суммирования.
Реализации на C++, Python и Java вычисляют одну и ту же формулу включения-исключения по всем длинам от 1 до 16. Для каждого \(n\) они получают общее число кандидатов, затем все односимвольные, двусимвольные и трехсимвольные исключения, после чего складывают их с правильными знаками и добавляют результат к общей сумме.
На каждом шаге вычисляются степени \(16^{n-1}\), \(15^n\), \(15^{n-1}\), \(14^n\), \(14^{n-1}\) и \(13^n\). Этого достаточно, чтобы сразу построить все необходимые комбинаторные слагаемые. В алгоритме нет перебора по цифрам, нет мемоизации и нет автомата состояний; он целиком состоит из точной целочисленной арифметики.
Практическая разница между версиями сводится к типу целых чисел. Python использует встроенные большие целые, Java работает с целыми произвольной точности, а C++ применяет фиксированный широкий тип, достаточный для этого диапазона.
После сложения всех значений \(C_n\) итог переводится в шестнадцатеричную запись в верхнем регистре и печатается. Одна из версий дополнительно проверяет малый случай \(C_3=4\), чтобы убедиться, что формула собрана без ошибок знаков и коэффициентов.
По сути, код представляет собой почти дословный перенос математического вывода в программу: посчитать запрещенные случаи, объединить их по включению-исключению и затем просуммировать по длинам.
Если максимальная длина равна \(L\), то время работы составляет \(O(L)\), поскольку для каждого \(n\) выполняется лишь постоянное число арифметических операций. В задаче с \(L=16\) это фактически константное время.
Память равна \(O(1)\), если не считать место под само итоговое число. Никаких больших таблиц, стеков рекурсии или структур, растущих вместе с количеством допустимых чисел, здесь не требуется.
المطلوب هو عدّ جميع الأعداد الست عشرية التي لا يزيد طولها على 16 خانة، ولا تبدأ بصفر، وتحتوي الرموز \(0\) و\(1\) و\(A\) كلًّا منها مرة واحدة على الأقل.
إذا رمزنا بعدد الأعداد الصحيحة الست عشرية الصحيحة ذات الطول \(n\) التي تحقق الشرط بالرمز \(C_n\)، فإن الكمية المطلوبة هي
$$S=\sum_{n=1}^{16} C_n.$$
وفي النهاية يُعرض الناتج نفسه بصيغة ست عشرية. النقطة الرياضية المهمة هنا أن قيد الخانة الأولى يجعل الحالات غير متناظرة: غياب \(0\) لا يُعد بالطريقة نفسها التي يُعد بها غياب \(1\) أو غياب \(A\).
لنثبت طولًا معينًا \(n\). سننظر أولًا إلى جميع السلاسل الست عشرية ذات الطول \(n\) التي لا تكون خانتها الأولى صفرًا، ثم نحصي من بينها السلاسل التي تظهر فيها الرموز الثلاثة المطلوبة جميعًا. هذه بالضبط مسألة شمول واستبعاد، ولكن يجب إدخال قيد الخانة الأولى في كل حساب جزئي.
الخانة الأولى يمكن أن تكون أي رمز ست عشري غير صفري، أي هناك 15 اختيارًا. أما كل خانة لاحقة فلها 16 اختيارًا. إذن عدد جميع المرشحين هو
$$T_n = 15 \cdot 16^{n-1}.$$
وهذا هو حجم الفضاء الكلي قبل فرض ظهور \(0\) و\(1\) و\(A\).
نعرّف الأحداث التالية: الحدث \(E_0\) يعني أن \(0\) لا يظهر إطلاقًا، والحدث \(E_1\) يعني أن \(1\) لا يظهر إطلاقًا، والحدث \(E_A\) يعني أن \(A\) لا يظهر إطلاقًا.
إذن \(C_n\) هو عدد عناصر الفضاء الكلي التي لا تنتمي إلى أي من هذه الأحداث الثلاثة، وبالتالي
$$C_n = T_n - |E_0 \cup E_1 \cup E_A|.$$
ومن هنا نستخدم مبدأ الشمول والاستبعاد لتفكيك هذا الاتحاد إلى حدود مفردة ومزدوجة وثلاثية.
هذه هي الفكرة الأساسية في المسألة. إذا كان \(0\) ممنوعًا في كل الخانات، فإن شرط عدم البدء بصفر يصبح متحققًا تلقائيًا، لأن الصفر أصلًا غير متاح. أما إذا كان الممنوع هو \(1\) أو \(A\)، فإن الصفر يبقى متاحًا في الخانات اللاحقة لكنه يظل غير مسموح في الخانة الأولى. لذلك لا بد من فصل الخانة الأولى عن بقية الخانات في العد.
ولهذا نحصل على
$$|E_0| = 15^n,$$
لأن كل خانة يمكن أن تختار أي رمز غير الصفر. بينما
$$|E_1| = 14 \cdot 15^{n-1},\qquad |E_A| = 14 \cdot 15^{n-1},$$
لأن الخانة الأولى لا يجوز أن تكون صفرًا ولا الرمز الممنوع، فتملك 14 اختيارًا، في حين أن كل خانة لاحقة تملك 15 اختيارًا.
الآن ننتقل إلى التقاطعات.
إذا غاب الرمزان \(0\) و\(1\) معًا، فالأبجدية المتاحة تحتوي على 14 رمزًا ولا يوجد بينها صفر، ومن ثم يختفي أثر قيد البداية تلقائيًا:
$$|E_0 \cap E_1| = 14^n.$$
وبالمثل
$$|E_0 \cap E_A| = 14^n.$$
أما إذا غاب \(1\) و\(A\) معًا، فالصفر لا يزال متاحًا في الخانات الداخلية فقط، لذا
$$|E_1 \cap E_A| = 13 \cdot 14^{n-1}.$$
وأخيرًا، إذا غابت الرموز الثلاثة \(0\) و\(1\) و\(A\) كلها، فلا يبقى إلا 13 رمزًا، ولا يوجد بينها صفر، ومن ثم
$$|E_0 \cap E_1 \cap E_A| = 13^n.$$
بالتعويض في الصيغة العامة نحصل على
$$C_n = T_n - (|E_0| + |E_1| + |E_A|) + (|E_0 \cap E_1| + |E_0 \cap E_A| + |E_1 \cap E_A|) - |E_0 \cap E_1 \cap E_A|,$$
أي
$$C_n = 15 \cdot 16^{n-1} - \bigl(15^n + 14 \cdot 15^{n-1} + 14 \cdot 15^{n-1}\bigr) + \bigl(14^n + 14^n + 13 \cdot 14^{n-1}\bigr) - 13^n.$$
وبعد جمع المعاملات المتشابهة يمكن كتابة الصيغة المكافئة المختصرة على شكل
$$C_n = 15 \cdot 16^{n-1} - 43 \cdot 15^{n-1} + 41 \cdot 14^{n-1} - 13^n.$$
النسخ البرمجية تحتفظ عادة بالصيغة المفصلة، لأن كل حد فيها يوضح مباشرة أي حالة ممنوعة يقوم بعدّها.
أصغر طول غير تافه هو \(n=3\)، لأنه لا يمكن لثلاثة رموز مختلفة مطلوبة أن تظهر جميعًا قبل ذلك. عند التعويض نحصل على
$$C_3 = 15 \cdot 16^2 - 15^3 - 2 \cdot 14 \cdot 15^2 + 2 \cdot 14^3 + 13 \cdot 14^2 - 13^3 = 4.$$
ويمكن رؤية ذلك مباشرة دون أي صيغة: إذا كان العدد من ثلاث خانات ويحتوي \(0\) و\(1\) و\(A\) كلًّا منها مرة واحدة على الأقل، فلا بد أن تكون الخانات مجرد ترتيب لهذه الرموز الثلاثة. لدينا \(3! = 6\) ترتيبات، لكن ترتيبين منها يبدآن بصفر، وهما غير صالحين. إذن الأعداد الصالحة هي بالضبط
$$10A,\qquad 1A0,\qquad A01,\qquad A10.$$
هذا المثال الصغير مفيد جدًا كاختبار صحة، ولذلك تستخدمه إحدى النسخ البرمجية كنقطة تحقق.
مجموعات الأعداد ذات الأطوال المختلفة متباينة، لذلك يكون الجواب النهائي ببساطة
$$S = \sum_{n=1}^{16} C_n.$$
كما أن الصيغة نفسها تعطي تلقائيًا \(C_1=C_2=0\). وبما أن الحد الأعلى للطول هو 16 فقط، فلا توجد حاجة إلى علاقات عودية أو برمجة ديناميكية معقدة؛ فالجمع المباشر الدقيق كافٍ تمامًا.
تنفذ تطبيقات C++ وPython وJava الصيغة نفسها حرفيًا تقريبًا. فهي تمر على الأطوال من \(1\) إلى \(16\)، وتحسب في كل مرة العدد الكلي للحالات، ثم أعداد الحالات التي يغيب فيها رمز واحد، أو رمزان، أو الرموز الثلاثة معًا، وبعد ذلك تجمع هذه الحدود بالإشارات الصحيحة للحصول على \(C_n\).
في كل دورة تُحسب قوى مثل \(16^{n-1}\) و\(15^n\) و\(14^n\) و\(13^n\). ومن هذه القيم تُبنى جميع حدود الشمول والاستبعاد مباشرة. لا يوجد بحث على مستوى الخانات، ولا تعداد شجري، ولا جدول حالات؛ إنما هو حساب صحيح مباشر بأعداد صحيحة دقيقة.
الاختلاف العملي بين اللغات الثلاث هو فقط في نوع الأعداد المستخدمة. Python تستفيد من الأعداد الصحيحة كبيرة الدقة المدمجة، وJava تستخدم أعدادًا صحيحة ذات دقة غير محدودة، أما C++ فتستخدم نوعًا صحيحًا ثابت العرض يكفي لهذا المجال.
بعد جمع كل قيم \(C_n\)، يُحوَّل المجموع النهائي إلى تمثيل ست عشري بأحرف كبيرة ثم يُطبع. كما أن إحدى النسخ تتحقق أولًا من الحقيقة الصغيرة \(C_3=4\)، وهذا يؤكد أن إشارات الشمول والاستبعاد والمعاملات العددية مرتبة على نحو صحيح.
وبهذا يكون الكود، من الناحية المفهومية، ترجمة مباشرة جدًا للاشتقاق الرياضي: عدّ الحالات الممنوعة، ثم تركيبها بالشمول والاستبعاد، ثم الجمع على الأطوال كلها.
إذا كان الحد الأقصى للطول هو \(L\)، فإن زمن التنفيذ يساوي \(O(L)\)، لأن كل طول يحتاج عددًا ثابتًا من العمليات الحسابية. وفي هذه المسألة حيث \(L=16\)، يصبح الزمن عمليًا ثابتًا.
أما الذاكرة فهي \(O(1)\) إذا استثنينا المساحة اللازمة لتخزين العدد النهائي نفسه. لا توجد جداول كبيرة ولا هياكل بيانات تنمو مع عدد الحالات الصالحة، لذلك يبقى الحل بسيطًا وخفيفًا جدًا.