For each integer \(1\le n\le N\), the implementations do not work with \(n\) directly. Instead they attach to \(n\) a canonical ternary signature \(V(n)\) that preserves the quantity relevant to the problem. After that compression, the task becomes a counting problem: how many unordered pairs \(\{a,b\}\) and \(\{c,d\}\) with entries in \([1,N]\) have the same combined signature?
Brute force over all quadruples is impossible. Even brute force over all \(\binom{N+1}{2}\) unordered pairs would be far too large for \(N=100000\). The key observation in the code is that many integers share the same signature, the signature is built recursively from the ternary expansion, and pair equality can therefore be counted class-by-class instead of number-by-number.
Write the signature as
$$V(n)=\bigl(f(n),\varepsilon(n),\mathbf{u}(n)\bigr),$$
where \(f(n)\) is a nonpositive dyadic rational, \(\varepsilon(n)\in\{0,1\}\) is a parity bit, and \(\mathbf{u}(n)\) is a finite vector of nonnegative integers. The whole solution is built around the fact that this signature can be computed recursively from the ternary digits of \(n\), and that pair signatures combine componentwise.
Let \(n=3q+r\) with \(r\in\{0,1,2\}\). Start from
$$V(0)=\bigl(0,0,\mathbf{0}\bigr).$$
Then the recurrence used by all three implementations is
$$V(3q+1)=\bigl(f(q)-1,\varepsilon(q),\mathbf{u}(q)\bigr),$$
$$V(3q+2)=\bigl(f(q),\varepsilon(q)\oplus 1,\mathbf{u}(q)\bigr),$$
and
$$V(3q)=\begin{cases} \bigl(f(q)+1,\varepsilon(q),\mathbf{u}(q)\bigr), & f(q)\le -2,\\ \bigl(f(q)/2,\varepsilon(q),\mathbf{u}(q)\bigr), & -2<f(q)<0,\\ Z(3q), & f(q)=0. \end{cases}$$
The code stores \(f(n)\) after multiplying by a fixed power of two, so that every subtraction, increment, and halving stays exact in integer arithmetic. This works because the first component is always built from the operations \(-1\), \(+1\), and division by 2, so only dyadic rational numbers can appear.
The branch \(Z(3q)\) is not an arbitrary exception. It is reached exactly when the ternary expansion of \(n\) contains only the digits \(0\) and \(2\).
The proof is a short induction. From a state with \(f=0\), appending a ternary digit \(2\) keeps \(f=0\), while appending a digit \(0\) also keeps the first component at 0 via the special branch. Appending a digit \(1\) makes the first component negative immediately. Once \(f<0\), none of the three transitions can return it to 0: the \(r=1\) branch decreases it, the \(r=2\) branch leaves it unchanged, and the \(r=0\) branch either adds 1 to a value at most \(-2\) or halves a value in \((-2,0)\), both of which remain negative. Therefore
Equivalently, \(f(n)=0\) if and only if every ternary digit of \(n\) belongs to \(\{0,2\}\).
This is why the solution splits the problem into two regimes: ordinary numbers with \(f(n)<0\), and the special \(0/2\)-digit numbers where the scalar part vanishes and a more detailed combinatorial profile is needed.
Suppose \(n=\sum_{i\ge 0} t_i 3^i\) and every ternary digit satisfies \(t_i\in\{0,2\}\). Then the implementations encode the remaining information as a parity bit together with a vector that records how zeros are distributed to the right of each digit \(2\).
The parity bit is simply
$$\varepsilon(n)\equiv \#\{i:t_i=2\}\pmod 2.$$
For \(k\ge 1\), define
$$u_k(n)=\#\Bigl\{i:t_i=2,\ \#\{j<i:t_j=0\}=k\Bigr\}.$$
So \(u_k(n)\) counts how many digits \(2\) have exactly \(k\) zeros somewhere to their right. Digits \(2\) with no zero to their right affect only the parity bit and do not contribute to the stored vector. The implementations reconstruct this profile by scanning the ternary expansion from least significant trit to most significant trit, keeping a running count of zeros already seen.
A few concrete examples make the rule transparent. For \(18=200_3\), the parity bit is 1 and the only nonzero vector entry is \(u_2=1\). For \(20=202_3\), the parity bit is 0 and the only nonzero entry is \(u_1=1\), because one digit \(2\) has one zero to its right and the other has none. For \(24=220_3\), the parity bit is 0 and the only nonzero entry is \(u_1=2\), because both digits \(2\) have exactly one zero to their right.
Once a number has been replaced by its signature, a pair \(\{a,b\}\) is represented by the componentwise combination
$$V(a,b)=\bigl(f(a)+f(b),\ \varepsilon(a)\oplus\varepsilon(b),\ \mathbf{u}(a)+\mathbf{u}(b)\bigr).$$
If a signature class \(K\) occurs \(F(K)\) times among \(1,2,\dots,N\), then there is no reason to enumerate all members of that class separately. The number of unordered pairs contributed by one class on the diagonal is
$$\binom{F(K)+1}{2},$$
while two distinct classes \(K_1\) and \(K_2\) contribute
$$F(K_1)F(K_2).$$
Accumulating these weights by the resulting pair signature produces a distribution \(C(T)\):
$$C(T)=\#\bigl\{\{a,b\}:1\le a\le b\le N,\ V(a,b)=T\bigr\}.$$
The final answer is then
$$A(N)=\sum_T C(T)^2.$$
In other words, the program counts ordered pairs of unordered pairs that land in the same combined signature class.
For the first five integers, the signatures are
$$V(1)=(-1,0,\mathbf{0}),\quad V(2)=(0,1,\mathbf{0}),\quad V(3)=(-1/2,0,\mathbf{0}),$$
$$V(4)=(-2,0,\mathbf{0}),\quad V(5)=(-1,1,\mathbf{0}).$$
There are 15 unordered pairs \(\{a,b\}\) with \(1\le a\le b\le 5\), but only 12 distinct combined signatures. The collisions are
$$V(1,1)=V(5,5),\qquad V(1,5)=V(2,4),\qquad V(2,5)=V(3,3).$$
So three signature classes occur twice and nine classes occur once. Therefore
$$A(5)=3\cdot 2^2+9\cdot 1^2=21,$$
which is exactly the value used by the implementations as their built-in sanity check.
The C++, Python, and Java implementations compute \(V(n)\) for every \(0\le n\le N\) in increasing order. Because each transition only depends on the quotient \(\lfloor n/3\rfloor\), this is a simple dynamic-programming pass over the integers. The dyadic scalar is stored as a scaled integer, the parity bit is stored explicitly, and the zero-count profile is kept in a short fixed-length vector that is comfortably large enough for \(N=100000\).
The only non-constant-time update is the special \(0/2\)-digit branch for multiples of 3 with \(f=0\). In that case the implementation rescans the ternary digits of the current number to rebuild the zero-count profile. This is deliberate: once the scalar part has collapsed to zero, appending a trailing zero can shift every recorded zero count, so rebuilding from the digits is simpler and safer than trying to update the compressed profile locally.
After the table of \(V(n)\) values is available, the implementations build a frequency map \(F(K)\) for the distinct signature classes. This compression is substantial: for the target input, the 100000 integers collapse to only a few thousand distinct signatures, so the expensive part of the search moves from numbers to classes.
The next pass loops over unordered pairs of signature classes. For each diagonal class it adds \(\binom{F(K)+1}{2}\), and for each off-diagonal class pair it adds \(F(K_1)F(K_2)\), to the bucket indexed by the combined signature. Once that map has been built, the answer is the sum of the squares of all bucket sizes.
Because the final count is much larger than 64-bit signed range, the implementations use an extended integer type for the last accumulation stage: native arbitrary precision in Python, a big integer type in Java, and a 128-bit unsigned integer in C++.
Let \(U\) be the number of distinct signatures among \(1,\dots,N\). Building the main table is essentially linear in \(N\), with occasional extra \(O(\log_3 N)\) rescans on the special \(0/2\)-digit branch. The compression phase is \(O(N)\). The dominant counting phase is \(O(U^2)\), because every unordered pair of signature classes is processed once, and each combination uses only fixed-size arithmetic on the three signature components.
Memory usage is \(O(N)\) for the table of signatures together with \(O(U)\) and \(O(M)\) for the frequency map and the pair-signature map, where \(M\) is the number of distinct combined signatures that actually occur. For the target input this is practical precisely because \(U\) is far smaller than \(N\), so the program never needs to examine all integer pairs directly.
Für jede ganze Zahl \(1\le n\le N\) arbeiten die Implementierungen nicht direkt mit \(n\), sondern ordnen \(n\) eine kanonische ternäre Signatur \(V(n)\) zu. Danach wird die Aufgabe zu einem reinen Zählproblem: Wie viele ungeordnete Paare \(\{a,b\}\) und \(\{c,d\}\) mit Einträgen aus \([1,N]\) besitzen dieselbe kombinierte Signatur?
Eine rohe Vierfachzählung ist ausgeschlossen. Selbst ein direkter Durchlauf über alle \(\binom{N+1}{2}\) ungeordneten Paare wäre für \(N=100000\) viel zu groß. Die entscheidende Beobachtung ist, dass viele Zahlen dieselbe Signatur teilen, dass diese Signatur rekursiv aus der Ternärdarstellung entsteht und dass Gleichheiten von Paaren deshalb klassenweise statt zahlweise gezählt werden können.
Schreibe die Signatur als
$$V(n)=\bigl(f(n),\varepsilon(n),\mathbf{u}(n)\bigr),$$
wobei \(f(n)\) eine nichtpositive dyadische rationale Zahl ist, \(\varepsilon(n)\in\{0,1\}\) ein Paritätsbit und \(\mathbf{u}(n)\) ein endlicher Vektor nichtnegativer ganzer Zahlen. Die gesamte Lösung beruht darauf, dass diese Signatur rekursiv aus den Ternärziffern von \(n\) berechnet werden kann und dass sich Paarsignaturen komponentenweise zusammensetzen.
Sei \(n=3q+r\) mit \(r\in\{0,1,2\}\). Ausgangspunkt ist
$$V(0)=\bigl(0,0,\mathbf{0}\bigr).$$
Dann verwenden alle drei Implementierungen die Rekursion
$$V(3q+1)=\bigl(f(q)-1,\varepsilon(q),\mathbf{u}(q)\bigr),$$
$$V(3q+2)=\bigl(f(q),\varepsilon(q)\oplus 1,\mathbf{u}(q)\bigr),$$
und
$$V(3q)=\begin{cases} \bigl(f(q)+1,\varepsilon(q),\mathbf{u}(q)\bigr), & f(q)\le -2,\\ \bigl(f(q)/2,\varepsilon(q),\mathbf{u}(q)\bigr), & -2<f(q)<0,\\ Z(3q), & f(q)=0. \end{cases}$$
Im Code wird \(f(n)\) mit einer festen Zweierpotenz skaliert gespeichert, damit Subtraktion, Erhöhung und Halbierung exakt mit Ganzzahlen ausgeführt werden können. Das funktioniert, weil die erste Komponente nur durch die Operationen \(-1\), \(+1\) und Division durch 2 entsteht und daher stets dyadisch rational bleibt.
Der Zweig \(Z(3q)\) ist keine zufällige Ausnahme. Er tritt genau dann auf, wenn die Ternärdarstellung von \(n\) ausschließlich aus den Ziffern \(0\) und \(2\) besteht.
Der Beweis ist eine kurze Induktion. Aus einem Zustand mit \(f=0\) bleibt \(f\) beim Anhängen einer ternären Ziffer \(2\) gleich 0; beim Anhängen einer Ziffer \(0\) bleibt die erste Komponente über den Spezialzweig ebenfalls 0. Eine angehängte Ziffer \(1\) macht die erste Komponente sofort negativ. Sobald \(f<0\) gilt, kann keine der drei Übergangsregeln mehr zu 0 zurückkehren: Der Zweig \(r=1\) verkleinert \(f\), der Zweig \(r=2\) lässt es unverändert, und der Zweig \(r=0\) addiert entweder 1 zu einem Wert höchstens \(-2\) oder halbiert einen Wert aus \((-2,0)\); in beiden Fällen bleibt das Ergebnis negativ. Also gilt
Äquivalent dazu gilt: \(f(n)=0\) genau dann, wenn jede Ternärziffer von \(n\) zur Menge \(\{0,2\}\) gehört.
Genau deshalb teilt die Lösung das Problem in zwei Regime auf: gewöhnliche Zahlen mit \(f(n)<0\) und die speziellen \(0/2\)-Zahlen, bei denen der skalare Anteil verschwindet und durch ein feineres kombinatorisches Profil ersetzt werden muss.
Sei \(n=\sum_{i\ge 0} t_i 3^i\) mit \(t_i\in\{0,2\}\) für alle \(i\). Dann codieren die Implementierungen die restliche Information durch ein Paritätsbit und einen Vektor, der speichert, wie viele Nullen rechts von jeder Ziffer \(2\) liegen.
Das Paritätsbit ist einfach
$$\varepsilon(n)\equiv \#\{i:t_i=2\}\pmod 2.$$
Für \(k\ge 1\) definiert man
$$u_k(n)=\#\Bigl\{i:t_i=2,\ \#\{j<i:t_j=0\}=k\Bigr\}.$$
Damit zählt \(u_k(n)\), wie viele Ziffern \(2\) genau \(k\) Nullen irgendwo rechts von sich haben. Ziffern \(2\), rechts von denen keine Null steht, beeinflussen nur das Paritätsbit und erscheinen nicht im gespeicherten Vektor. Rekonstruiert wird dieses Profil durch einen Scan der Ternärdarstellung von der niederwertigsten zur höchstwertigen Tritstelle, wobei die Anzahl bereits gesehener Nullen mitgeführt wird.
Einige konkrete Beispiele machen die Regel greifbar. Für \(18=200_3\) ist das Paritätsbit 1 und der einzige von Null verschiedene Vektoreintrag ist \(u_2=1\). Für \(20=202_3\) ist das Paritätsbit 0 und der einzige nichtverschwindende Eintrag ist \(u_1=1\), weil eine Ziffer \(2\) genau eine Null rechts von sich hat und die andere gar keine. Für \(24=220_3\) ist das Paritätsbit 0 und der einzige nichtverschwindende Eintrag ist \(u_1=2\), weil beide Ziffern \(2\) genau eine Null rechts von sich haben.
Sobald eine Zahl durch ihre Signatur ersetzt wurde, wird ein Paar \(\{a,b\}\) durch die komponentenweise Kombination beschrieben:
$$V(a,b)=\bigl(f(a)+f(b),\ \varepsilon(a)\oplus\varepsilon(b),\ \mathbf{u}(a)+\mathbf{u}(b)\bigr).$$
Wenn eine Signaturklasse \(K\) unter \(1,2,\dots,N\) genau \(F(K)\) Mal vorkommt, muss man ihre Elemente nicht einzeln durchlaufen. Die Anzahl ungeordneter Paare auf der Diagonale einer Klasse ist
$$\binom{F(K)+1}{2},$$
während zwei verschiedene Klassen \(K_1\) und \(K_2\) genau
$$F(K_1)F(K_2)$$
ungeordnete Paare beitragen. Fasst man diese Gewichte nach der entstehenden Paarsignatur zusammen, so erhält man eine Verteilung \(C(T)\):
$$C(T)=\#\bigl\{\{a,b\}:1\le a\le b\le N,\ V(a,b)=T\bigr\}.$$
Die Endgröße ist dann
$$A(N)=\sum_T C(T)^2.$$
Das Programm zählt also geordnete Paare ungeordneter Zahlenpaare, die in dieselbe kombinierte Signaturklasse fallen.
Für die ersten fünf Zahlen lauten die Signaturen
$$V(1)=(-1,0,\mathbf{0}),\quad V(2)=(0,1,\mathbf{0}),\quad V(3)=(-1/2,0,\mathbf{0}),$$
$$V(4)=(-2,0,\mathbf{0}),\quad V(5)=(-1,1,\mathbf{0}).$$
Es gibt 15 ungeordnete Paare \(\{a,b\}\) mit \(1\le a\le b\le 5\), aber nur 12 verschiedene kombinierte Signaturen. Die Kollisionen sind
$$V(1,1)=V(5,5),\qquad V(1,5)=V(2,4),\qquad V(2,5)=V(3,3).$$
Damit treten drei Signaturklassen zweimal auf und neun Klassen genau einmal. Folglich
$$A(5)=3\cdot 2^2+9\cdot 1^2=21,$$
und genau dieser Wert wird in den Implementierungen als Plausibilitätsprüfung verwendet.
Die Implementierungen in C++, Python und Java berechnen \(V(n)\) für alle \(0\le n\le N\) in aufsteigender Reihenfolge. Da jeder Übergang nur vom Quotienten \(\lfloor n/3\rfloor\) abhängt, ist das ein einfacher dynamischer Durchlauf über die ganzen Zahlen. Der dyadische Skalar wird als skalierte Ganzzahl gespeichert, das Paritätsbit direkt abgelegt und das Nullprofil in einem kurzen Vektor fester Länge gehalten, der für \(N=100000\) mehr als ausreichend ist.
Nur der Spezialzweig für \(0/2\)-Zahlen mit \(f=0\) ist nicht konstant teuer. Dort scannt die Implementierung die Ternärziffern der aktuellen Zahl erneut, um das Nullprofil vollständig neu aufzubauen. Das ist beabsichtigt: Sobald der skalare Anteil zu 0 kollabiert ist, kann eine angehängte Null sämtliche gespeicherten Nullanzahlen verschieben, sodass ein Neuaufbau aus den Ziffern robuster ist als eine lokale Korrektur der komprimierten Darstellung.
Nachdem alle \(V(n)\) berechnet sind, bauen die Implementierungen eine Häufigkeitstabelle \(F(K)\) der verschiedenen Signaturklassen auf. Diese Kompression ist wesentlich: Für die Zieleingabe schrumpfen 100000 Zahlen auf nur einige Tausend verschiedene Signaturen, sodass der teure Teil der Rechnung von einzelnen Zahlen auf Klassen verschoben wird.
Im nächsten Schritt wird über ungeordnete Paare von Signaturklassen iteriert. Für eine Diagonalklasse wird \(\binom{F(K)+1}{2}\) addiert, für zwei verschiedene Klassen \(F(K_1)F(K_2)\), jeweils in den Behälter der entstehenden kombinierten Signatur. Sobald diese Abbildung aufgebaut ist, besteht die Antwort nur noch aus der Summe der Quadrate aller Behältergrößen.
Da der Endwert deutlich über den Bereich eines vorzeichenbehafteten 64-Bit-Typs hinausgeht, verwenden die Implementierungen in der letzten Akkumulationsphase erweiterte Ganzzahltypen: beliebige Genauigkeit in Python, einen Big-Integer-Typ in Java und einen 128-Bit-Unsigned-Typ in C++.
Sei \(U\) die Anzahl der verschiedenen Signaturen unter \(1,\dots,N\). Der Aufbau der Haupttabelle ist im Wesentlichen linear in \(N\), abgesehen von gelegentlichen zusätzlichen \(O(\log_3 N)\)-Scans im Spezialzweig für \(0/2\)-Zahlen. Die Kompressionsphase kostet \(O(N)\). Die dominante Zählphase hat Aufwand \(O(U^2)\), weil jedes ungeordnete Paar von Signaturklassen genau einmal verarbeitet wird und jede Kombination nur Operationen fester Größe auf den drei Signaturkomponenten benötigt.
Der Speicherbedarf ist \(O(N)\) für die Signaturtabelle sowie \(O(U)\) und \(O(M)\) für die Häufigkeitstabelle und die Tabelle kombinierter Paarsignaturen, wobei \(M\) die Anzahl tatsächlich auftretender kombinierter Signaturen ist. Für die Zieleingabe ist das gerade deshalb praktikabel, weil \(U\) deutlich kleiner als \(N\) ist und daher keine direkte Durchmusterung aller Zahlenpaare nötig wird.
Her \(1\le n\le N\) tamsayısı için uygulamalar \(n\) ile doğrudan çalışmaz. Bunun yerine \(n\)'ye, problemde önemli olan niceliği koruyan kanonik bir ternary imza \(V(n)\) atarlar. Bu sıkıştırmadan sonra görev saf bir sayma problemine dönüşür: \([1,N]\) aralığından gelen \(\{a,b\}\) ve \(\{c,d\}\) sırasız çiftlerinden kaç tanesi aynı birleşik imzaya sahiptir?
Bütün dörtlüleri kaba kuvvetle denemek imkansızdır. Hatta \(\binom{N+1}{2}\) tane sırasız çifti doğrudan dolaşmak bile \(N=100000\) için fazla büyüktür. Kodun temel fikri şudur: birçok sayı aynı imzayı paylaşır, bu imza ternary açılımdan rekürsif olarak üretilir ve bu yüzden çift eşitlikleri sayı sayı değil, sınıf sınıf sayılabilir.
İmzayı
$$V(n)=\bigl(f(n),\varepsilon(n),\mathbf{u}(n)\bigr)$$
şeklinde yazalım. Burada \(f(n)\) pozitif olmayan bir dyadic rasyoneldir, \(\varepsilon(n)\in\{0,1\}\) bir parite bitidir ve \(\mathbf{u}(n)\) sonlu bir negatif olmayan tamsayı vektörüdür. Bütün çözüm, bu imzanın \(n\)'nin ternary basamaklarından rekürsif biçimde hesaplanabilmesine ve çift imzalarının bileşen bazında birleşmesine dayanır.
\(n=3q+r\) ve \(r\in\{0,1,2\}\) olsun. Başlangıç durumu
$$V(0)=\bigl(0,0,\mathbf{0}\bigr)$$
olarak alınır. Sonra üç uygulamanın da kullandığı rekürans
$$V(3q+1)=\bigl(f(q)-1,\varepsilon(q),\mathbf{u}(q)\bigr),$$
$$V(3q+2)=\bigl(f(q),\varepsilon(q)\oplus 1,\mathbf{u}(q)\bigr),$$
ve
$$V(3q)=\begin{cases} \bigl(f(q)+1,\varepsilon(q),\mathbf{u}(q)\bigr), & f(q)\le -2,\\ \bigl(f(q)/2,\varepsilon(q),\mathbf{u}(q)\bigr), & -2<f(q)<0,\\ Z(3q), & f(q)=0 \end{cases}$$
şeklindedir. Kod, \(f(n)\) değerini sabit bir ikinin kuvvetiyle çarparak saklar; böylece çıkarma, artırma ve ikiye bölme işlemleri tam sayılarla hatasız yapılır. Bunun nedeni, ilk bileşenin yalnızca \(-1\), \(+1\) ve 2'ye bölme işlemlerinden oluşmasıdır; dolayısıyla ortaya çıkabilecek sayılar sadece dyadic rasyonellerdir.
\(Z(3q)\) dalı rastgele bir istisna değildir. Tam olarak, \(n\)'nin ternary gösteriminde yalnızca \(0\) ve \(2\) rakamları bulunduğunda devreye girer.
Kanıt kısa bir indüksiyondur. \(f=0\) olan bir durumdan başlayınca, sona ternary rakam \(2\) eklemek \(f\)'yi 0'da bırakır; sona \(0\) eklemek de özel dal üzerinden ilk bileşeni yine 0 yapar. Buna karşılık bir \(1\) rakamı eklemek ilk bileşeni hemen negatif yapar. Bir kez \(f<0\) olduktan sonra hiçbir geçiş onu tekrar 0'a döndüremez: \(r=1\) dalı değeri azaltır, \(r=2\) dalı olduğu gibi bırakır, \(r=0\) dalı ise ya en çok \(-2\) olan bir değere 1 ekler ya da \((-2,0)\) aralığındaki bir değeri ikiye böler; her iki durumda da sonuç negatiftir. Dolayısıyla
Eşdeğer olarak, \(f(n)=0\) ancak ve ancak \(n\)'nin her ternary basamağı \(\{0,2\}\) kümesine aitse gerçekleşir.
Bu yüzden çözüm problemi iki rejime ayırır: \(f(n)<0\) olan sıradan sayılar ve skaler kısmın kaybolup daha ayrıntılı bir kombinatorik profilin gerektiği özel \(0/2\) sayıları.
\(n=\sum_{i\ge 0} t_i 3^i\) olsun ve bütün ternary basamaklar \(t_i\in\{0,2\}\) koşulunu sağlasın. Bu durumda uygulamalar kalan bilgiyi bir parite biti ve her \(2\) rakamının sağında kaç tane \(0\) bulunduğunu kaydeden bir vektör ile temsil eder.
Parite biti basitçe
$$\varepsilon(n)\equiv \#\{i:t_i=2\}\pmod 2$$
şeklindedir. \(k\ge 1\) için
$$u_k(n)=\#\Bigl\{i:t_i=2,\ \#\{j<i:t_j=0\}=k\Bigr\}$$
tanımlanır. Yani \(u_k(n)\), sağında tam olarak \(k\) tane \(0\) bulunan \(2\) basamaklarının sayısını verir. Sağında hiç \(0\) bulunmayan \(2\) basamakları yalnızca parite bitini etkiler, saklanan vektöre girmez. Uygulamalar bu profili, ternary açılımı en düşük basamaktan en yüksek basamağa tarayıp o ana kadar görülen sıfır sayısını tutarak yeniden kurar.
Birkaç örnek kuralı netleştirir. \(18=200_3\) için parite biti 1'dir ve vektörde sıfır olmayan tek giriş \(u_2=1\)'dir. \(20=202_3\) için parite biti 0'dır ve tek sıfır olmayan giriş \(u_1=1\)'dir; çünkü \(2\) rakamlarından biri sağında bir sıfır görür, diğeri hiç görmez. \(24=220_3\) için parite biti yine 0'dır ve tek sıfır olmayan giriş \(u_1=2\)'dir; çünkü iki \(2\) rakamının da sağında tam bir sıfır vardır.
Bir sayı imzasıyla temsil edildikten sonra \(\{a,b\}\) çifti şu bileşen bazlı birleşimle yazılır:
$$V(a,b)=\bigl(f(a)+f(b),\ \varepsilon(a)\oplus\varepsilon(b),\ \mathbf{u}(a)+\mathbf{u}(b)\bigr).$$
Eğer bir imza sınıfı \(K\), \(1,2,\dots,N\) arasında \(F(K)\) kez görülüyse, bu sınıfın elemanlarını tek tek dolaşmaya gerek yoktur. Aynı sınıfın diyagonal katkısı
$$\binom{F(K)+1}{2}$$
olur; iki farklı sınıf \(K_1\) ve \(K_2\) ise
$$F(K_1)F(K_2)$$
tane sırasız çift üretir. Bu ağırlıkları ortaya çıkan çift imzasına göre toplarsak bir \(C(T)\) dağılımı elde ederiz:
$$C(T)=\#\bigl\{\{a,b\}:1\le a\le b\le N,\ V(a,b)=T\bigr\}.$$
Nihai cevap da
$$A(N)=\sum_T C(T)^2$$
olur. Başka bir deyişle program, aynı birleşik imza sınıfına düşen sırasız çift çiftlerini sıralı olarak saymaktadır.
İlk beş sayı için imzalar
$$V(1)=(-1,0,\mathbf{0}),\quad V(2)=(0,1,\mathbf{0}),\quad V(3)=(-1/2,0,\mathbf{0}),$$
$$V(4)=(-2,0,\mathbf{0}),\quad V(5)=(-1,1,\mathbf{0})$$
şeklindedir. \(1\le a\le b\le 5\) için 15 tane sırasız çift vardır, fakat birleşik imzalar yalnızca 12 farklı değer alır. Çakışmalar
$$V(1,1)=V(5,5),\qquad V(1,5)=V(2,4),\qquad V(2,5)=V(3,3)$$
şeklindedir. Böylece üç imza sınıfı iki kez, dokuz sınıf da bir kez görünür. O halde
$$A(5)=3\cdot 2^2+9\cdot 1^2=21$$
elde edilir ve bu da uygulamaların gömülü doğrulama değeriyle tam olarak aynıdır.
C++, Python ve Java uygulamaları \(0\le n\le N\) aralığındaki tüm sayılar için \(V(n)\) değerlerini artan sırada hesaplar. Her geçiş yalnızca \(\lfloor n/3\rfloor\) bölümüne bağlı olduğu için bu, tamsayılar üzerinde basit bir dinamik programlama geçişidir. Dyadic skaler ölçeklenmiş tam sayı olarak tutulur, parite biti doğrudan saklanır ve sıfır sayım profili de \(N=100000\) için rahatça yeterli olan kısa, sabit uzunluklu bir vektörde tutulur.
Sabit zamanlı olmayan tek güncelleme, \(f=0\) olan 3'ün katları için kullanılan özel \(0/2\) dalıdır. Bu durumda uygulama mevcut sayının ternary basamaklarını yeniden tarayarak sıfır sayım profilini baştan kurar. Bu tercih bilinçlidir: skaler kısım 0'a düştükten sonra sona eklenen bir \(0\), saklanan bütün sıfır sayılarını kaydırabilir; bu yüzden profili yerel olarak güncellemek yerine basamaklardan yeniden kurmak daha güvenlidir.
\(V(n)\) tablosu hazırlandıktan sonra uygulamalar, farklı imza sınıfları için bir \(F(K)\) frekans tablosu oluşturur. Bu sıkıştırma çok etkilidir: hedef girdide 100000 sayı yalnızca birkaç bin farklı imzaya iner; dolayısıyla pahalı arama sayılardan sınıflara taşınmış olur.
Bir sonraki aşama, imza sınıflarının sırasız çiftleri üzerinde döner. Diyagonal sınıflar için \(\binom{F(K)+1}{2}\), farklı sınıf çiftleri için \(F(K_1)F(K_2)\) eklenir ve bu ağırlıklar oluşan birleşik imzanın kovasına yazılır. Bu harita tamamlandığında cevap, bütün kova büyüklüklerinin karelerinin toplamıdır.
Son sayı işaretli 64 bit aralığını açıkça aştığı için son biriktirme aşamasında geniş tamsayı türleri kullanılır: Python'da doğal keyfi hassasiyet, Java'da büyük tamsayı türü ve C++ tarafında işaretsiz 128 bit türü.
\(U\), \(1,\dots,N\) arasındaki farklı imza sayısı olsun. Ana tabloyu kurmak, özel \(0/2\) dalındaki seyrek \(O(\log_3 N)\) taramalar dışında esasen \(N\) doğrusal zaman alır. Sıkıştırma aşaması \(O(N)\)'dir. Baskın maliyet \(O(U^2)\) olan sayma aşamasıdır; çünkü her sırasız imza sınıfı çifti tam bir kez işlenir ve her birleşim, üç imza bileşeni üzerinde sabit boyutlu aritmetik gerektirir.
Bellek kullanımı, imza tablosu için \(O(N)\), frekans tablosu ve çift-imza tablosu için sırasıyla \(O(U)\) ve \(O(M)\)'dir; burada \(M\), gerçekten ortaya çıkan birleşik imza sayısıdır. Hedef girdide bunun pratik olmasının nedeni tam olarak \(U\)'nun \(N\)'den çok daha küçük olması ve bu sayede bütün sayı çiftlerini doğrudan incelemeye gerek kalmamasıdır.
Para cada entero \(1\le n\le N\), las implementaciones no trabajan con \(n\) de forma directa. En su lugar asignan a \(n\) una firma ternaria canónica \(V(n)\) que preserva la cantidad relevante del problema. Después de esa compresión, la tarea pasa a ser un problema de conteo: ¿cuántos pares no ordenados \(\{a,b\}\) y \(\{c,d\}\), con entradas en \([1,N]\), tienen la misma firma combinada?
Una enumeración ingenua de todos los cuádruplos es imposible. Incluso recorrer de forma directa los \(\binom{N+1}{2}\) pares no ordenados sería demasiado para \(N=100000\). La observación decisiva es que muchos enteros comparten la misma firma, que esa firma se construye recursivamente a partir de la expansión ternaria y que, por tanto, las coincidencias entre pares pueden contarse por clases en vez de por valores individuales.
Escribamos la firma como
$$V(n)=\bigl(f(n),\varepsilon(n),\mathbf{u}(n)\bigr),$$
donde \(f(n)\) es un racional diádico no positivo, \(\varepsilon(n)\in\{0,1\}\) es un bit de paridad y \(\mathbf{u}(n)\) es un vector finito de enteros no negativos. Toda la solución se apoya en dos hechos: esta firma puede calcularse recursivamente a partir de los dígitos ternarios de \(n\), y las firmas de pares se combinan componente a componente.
Sea \(n=3q+r\) con \(r\in\{0,1,2\}\). El punto de partida es
$$V(0)=\bigl(0,0,\mathbf{0}\bigr).$$
Las tres implementaciones usan después la recurrencia
$$V(3q+1)=\bigl(f(q)-1,\varepsilon(q),\mathbf{u}(q)\bigr),$$
$$V(3q+2)=\bigl(f(q),\varepsilon(q)\oplus 1,\mathbf{u}(q)\bigr),$$
y
$$V(3q)=\begin{cases} \bigl(f(q)+1,\varepsilon(q),\mathbf{u}(q)\bigr), & f(q)\le -2,\\ \bigl(f(q)/2,\varepsilon(q),\mathbf{u}(q)\bigr), & -2<f(q)<0,\\ Z(3q), & f(q)=0. \end{cases}$$
El código almacena \(f(n)\) multiplicado por una potencia fija de 2, para que cada resta, incremento y división por 2 siga siendo exacta en aritmética entera. Esto funciona porque la primera componente solo se construye con las operaciones \(-1\), \(+1\) y división entre 2, así que únicamente pueden aparecer racionales diádicos.
La rama \(Z(3q)\) no es una excepción arbitraria. Aparece exactamente cuando la expansión ternaria de \(n\) contiene solo los dígitos \(0\) y \(2\).
La demostración es una inducción corta. Desde un estado con \(f=0\), añadir un dígito ternario \(2\) mantiene \(f=0\), y añadir un dígito \(0\) también mantiene la primera componente en 0 a través de la rama especial. En cambio, añadir un dígito \(1\) vuelve negativa a la primera componente de inmediato. Una vez que \(f<0\), ninguna de las tres transiciones puede devolverla a 0: la rama \(r=1\) la disminuye, la rama \(r=2\) la deja igual, y la rama \(r=0\) o bien suma 1 a un valor a lo sumo \(-2\) o bien divide entre 2 un valor de \((-2,0)\); en ambos casos el resultado sigue siendo negativo. Por tanto,
De forma equivalente, \(f(n)=0\) si y solo si todos los dígitos ternarios de \(n\) pertenecen al conjunto \(\{0,2\}\).
Por eso la solución separa dos regímenes: los números ordinarios con \(f(n)<0\) y los números especiales con dígitos \(0/2\), donde la parte escalar desaparece y hace falta un perfil combinatorio más fino.
Supongamos que \(n=\sum_{i\ge 0} t_i 3^i\) y que todos sus dígitos ternarios verifican \(t_i\in\{0,2\}\). Entonces las implementaciones codifican la información restante mediante un bit de paridad y un vector que registra cómo se distribuyen los ceros a la derecha de cada dígito \(2\).
El bit de paridad es simplemente
$$\varepsilon(n)\equiv \#\{i:t_i=2\}\pmod 2.$$
Para \(k\ge 1\), se define
$$u_k(n)=\#\Bigl\{i:t_i=2,\ \#\{j<i:t_j=0\}=k\Bigr\}.$$
Así, \(u_k(n)\) cuenta cuántos dígitos \(2\) tienen exactamente \(k\) ceros a su derecha. Los dígitos \(2\) que no tienen ningún cero a la derecha solo afectan al bit de paridad y no aparecen en el vector almacenado. Las implementaciones reconstruyen este perfil recorriendo la expansión ternaria desde el trit menos significativo hasta el más significativo, manteniendo el número de ceros ya vistos.
Unos ejemplos aclaran la regla. Para \(18=200_3\), el bit de paridad es 1 y la única entrada no nula del vector es \(u_2=1\). Para \(20=202_3\), el bit de paridad es 0 y la única entrada no nula es \(u_1=1\), porque un dígito \(2\) tiene un cero a su derecha y el otro no tiene ninguno. Para \(24=220_3\), el bit de paridad es 0 y la única entrada no nula es \(u_1=2\), porque ambos dígitos \(2\) tienen exactamente un cero a la derecha.
Una vez sustituido un número por su firma, el par \(\{a,b\}\) queda representado por la combinación componente a componente
$$V(a,b)=\bigl(f(a)+f(b),\ \varepsilon(a)\oplus\varepsilon(b),\ \mathbf{u}(a)+\mathbf{u}(b)\bigr).$$
Si una clase de firma \(K\) aparece \(F(K)\) veces entre \(1,2,\dots,N\), no hay razón para enumerar por separado todos sus miembros. El número de pares no ordenados aportados por una clase en la diagonal es
$$\binom{F(K)+1}{2},$$
mientras que dos clases distintas \(K_1\) y \(K_2\) aportan
$$F(K_1)F(K_2).$$
Si se acumulan esos pesos según la firma resultante del par, se obtiene una distribución \(C(T)\):
$$C(T)=\#\bigl\{\{a,b\}:1\le a\le b\le N,\ V(a,b)=T\bigr\}.$$
La respuesta final es entonces
$$A(N)=\sum_T C(T)^2.$$
Equivalente y combinatoriamente, el programa cuenta pares ordenados de pares no ordenados que caen en la misma clase de firma combinada.
Para los cinco primeros enteros, las firmas son
$$V(1)=(-1,0,\mathbf{0}),\quad V(2)=(0,1,\mathbf{0}),\quad V(3)=(-1/2,0,\mathbf{0}),$$
$$V(4)=(-2,0,\mathbf{0}),\quad V(5)=(-1,1,\mathbf{0}).$$
Existen 15 pares no ordenados \(\{a,b\}\) con \(1\le a\le b\le 5\), pero solo aparecen 12 firmas combinadas distintas. Las colisiones son
$$V(1,1)=V(5,5),\qquad V(1,5)=V(2,4),\qquad V(2,5)=V(3,3).$$
Por tanto, tres clases de firma aparecen dos veces y nueve aparecen una sola vez. Luego
$$A(5)=3\cdot 2^2+9\cdot 1^2=21,$$
que es exactamente el valor utilizado por las implementaciones como comprobación interna.
Las implementaciones en C++, Python y Java calculan \(V(n)\) para todos los \(0\le n\le N\) en orden creciente. Como cada transición depende solo del cociente \(\lfloor n/3\rfloor\), esto se convierte en una pasada de programación dinámica muy simple sobre los enteros. La parte diádica se guarda como entero escalado, el bit de paridad se almacena explícitamente y el perfil de ceros se conserva en un vector corto de longitud fija, más que suficiente para \(N=100000\).
La única actualización que no cuesta tiempo constante es la rama especial de los números con dígitos \(0/2\) cuando \(f=0\). En ese caso la implementación vuelve a recorrer los dígitos ternarios del número actual para reconstruir por completo el perfil de ceros. Esa decisión es intencional: una vez que la parte escalar ha colapsado a 0, añadir un cero final puede desplazar todos los recuentos almacenados, así que reconstruir desde los dígitos es más limpio que intentar corregir la representación comprimida localmente.
Una vez disponible la tabla de \(V(n)\), las implementaciones construyen un mapa de frecuencias \(F(K)\) para las distintas clases de firma. La compresión es fuerte: para la entrada objetivo, los 100000 enteros se reducen a solo unos pocos miles de firmas distintas, de modo que la parte cara de la búsqueda pasa de los números a las clases.
La fase siguiente recorre los pares no ordenados de clases de firma. Para una clase diagonal suma \(\binom{F(K)+1}{2}\), y para dos clases distintas suma \(F(K_1)F(K_2)\), todo ello en el contenedor indexado por la firma combinada resultante. Cuando ese mapa queda completo, la respuesta no es más que la suma de los cuadrados de todos los tamaños de contenedor.
Como el conteo final supera claramente el rango de un entero con signo de 64 bits, las implementaciones usan tipos ampliados en la última acumulación: precisión arbitraria nativa en Python, enteros grandes en Java y un entero sin signo de 128 bits en C++.
Sea \(U\) el número de firmas distintas entre \(1,\dots,N\). Construir la tabla principal es esencialmente lineal en \(N\), salvo por los rescaneos ocasionales de coste \(O(\log_3 N)\) en la rama especial de los números con dígitos \(0/2\). La fase de compresión cuesta \(O(N)\). La fase dominante de conteo cuesta \(O(U^2)\), porque cada par no ordenado de clases de firma se procesa exactamente una vez y cada combinación usa solo aritmética de tamaño fijo sobre las tres componentes de la firma.
El uso de memoria es \(O(N)\) para la tabla de firmas, junto con \(O(U)\) y \(O(M)\) para el mapa de frecuencias y el mapa de firmas combinadas, donde \(M\) es el número de firmas combinadas distintas que realmente aparecen. Para la entrada objetivo esto es práctico precisamente porque \(U\) es mucho menor que \(N\), así que nunca hace falta inspeccionar directamente todos los pares de enteros.
对每个 \(1\le n\le N\)，实现都不会直接拿 \(n\) 本身做最终比较，而是先给它构造一个规范化的三进制签名 \(V(n)\)。这个签名保留了题目真正关心的不变量。完成这一步压缩之后，问题就变成了一个纯计数问题：有多少个无序对 \(\{a,b\}\) 与 \(\{c,d\}\)（其中元素都在 \([1,N]\) 中）会落到同一个“二元组合签名”里？
如果直接枚举所有四元组，规模完全不可接受。即使只是枚举全部 \(\binom{N+1}{2}\) 个无序整数对，对 \(N=100000\) 也仍然太大。代码真正利用的是三个事实：很多整数会共享同一个签名；这个签名可以从三进制表示递归构造出来；于是“两个整数对是否等价”就可以按签名类来统计，而不需要逐个整数地比较。
把签名写成
$$V(n)=\bigl(f(n),\varepsilon(n),\mathbf{u}(n)\bigr),$$
其中 \(f(n)\) 是一个不大于 0 的 dyadic rational，\(\varepsilon(n)\in\{0,1\}\) 是一个奇偶位，而 \(\mathbf{u}(n)\) 是一个有限的非负整数向量。整个解法围绕两点展开：第一，\(V(n)\) 能从 \(n\) 的三进制数字递归地得到；第二，两个数构成一对之后，它们的组合签名可以按分量直接相加或异或得到。
设 \(n=3q+r\)，其中 \(r\in\{0,1,2\}\)。初始状态是
$$V(0)=\bigl(0,0,\mathbf{0}\bigr).$$
之后三份实现共同使用的递推关系为
$$V(3q+1)=\bigl(f(q)-1,\varepsilon(q),\mathbf{u}(q)\bigr),$$
$$V(3q+2)=\bigl(f(q),\varepsilon(q)\oplus 1,\mathbf{u}(q)\bigr),$$
以及
$$V(3q)=\begin{cases} \bigl(f(q)+1,\varepsilon(q),\mathbf{u}(q)\bigr), & f(q)\le -2,\\ \bigl(f(q)/2,\varepsilon(q),\mathbf{u}(q)\bigr), & -2<f(q)<0,\\ Z(3q), & f(q)=0. \end{cases}$$
代码里并不直接存浮点数，而是把 \(f(n)\) 乘上一个固定的 2 的幂之后作为整数保存，这样减 1、加 1、除以 2 都能保持完全精确。之所以可以这样做，是因为第一分量只会经历 \(-1\)、\(+1\) 和除以 2 这三种操作，所以它始终只是 dyadic rational，不会出现别的分母。
\(Z(3q)\) 并不是“碰巧写出来的特判”，它恰好发生在 \(n\) 的三进制展开只含 \(0\) 和 \(2\) 的时候。
这个结论可以用很短的归纳证明出来。从 \(f=0\) 的状态出发，如果末尾添加一个三进制数字 \(2\)，那么 \(f\) 仍然保持为 0；如果末尾添加一个 \(0\)，那么会走到特殊分支，但第一分量仍然保持 0。只有添加一个 \(1\) 时，第一分量会立刻变成负数。一旦 \(f<0\)，三种转移都不可能把它拉回 0：\(r=1\) 会进一步减小它，\(r=2\) 会保持不变，而 \(r=0\) 要么给一个不大于 \(-2\) 的值加 1，要么把 \((-2,0)\) 区间内的值再除以 2，这两种结果都仍然是负数。因此
等价地说，只有当 \(n\) 的每一个三进制数字都属于 \(\{0,2\}\) 时，才有 \(f(n)=0\)。
这就是为什么实现会把问题自然地分成两层：一层是普通整数，它们满足 \(f(n)<0\)；另一层是只含 \(0/2\) 数字的特殊整数，此时标量部分已经归零，必须再引入更细的组合型信息来区分它们。
设 \(n=\sum_{i\ge 0} t_i 3^i\)，并且每个三进制数字都满足 \(t_i\in\{0,2\}\)。这时实现把剩余信息编码成两部分：一个奇偶位，以及一个记录“每个数字 \(2\) 的右侧有多少个 0”的向量。
奇偶位的定义非常直接：
$$\varepsilon(n)\equiv \#\{i:t_i=2\}\pmod 2.$$
对每个 \(k\ge 1\)，再定义
$$u_k(n)=\#\Bigl\{i:t_i=2,\ \#\{j<i:t_j=0\}=k\Bigr\}.$$
也就是说，\(u_k(n)\) 统计的是：有多少个数字 \(2\)，它右边恰好出现了 \(k\) 个 0。右边完全没有 0 的那些 \(2\) 只会影响奇偶位，不会写进存储向量。实现的做法是从最低位 trit 扫到最高位 trit，同时维护“已经看见了多少个 0”的计数；每遇到一个 2，就按当前零计数把对应位置加 1，并翻转一次奇偶位。
具体例子最能说明这个规则。对于 \(18=200_3\)，奇偶位为 1，而且向量里唯一非零的分量是 \(u_2=1\)，因为唯一的那个 2 右边有两个 0。对于 \(20=202_3\)，奇偶位为 0，唯一非零的分量是 \(u_1=1\)，因为左边那个 2 右侧有一个 0，而最低位那个 2 右侧没有 0。对于 \(24=220_3\)，奇偶位同样为 0，唯一非零的分量是 \(u_1=2\)，因为两个 2 的右边都恰好有一个 0。
一旦每个整数都被替换成自己的签名，那么无序对 \(\{a,b\}\) 就由下面这个按分量组合的对象表示：
$$V(a,b)=\bigl(f(a)+f(b),\ \varepsilon(a)\oplus\varepsilon(b),\ \mathbf{u}(a)+\mathbf{u}(b)\bigr).$$
如果某个签名类 \(K\) 在 \(1,2,\dots,N\) 中出现了 \(F(K)\) 次，那么完全没必要把这个类里的元素逐一拿出来配对。来自同一个类的无序对数量是
$$\binom{F(K)+1}{2},$$
而来自两个不同签名类 \(K_1\) 和 \(K_2\) 的无序对数量则是
$$F(K_1)F(K_2).$$
如果按照组合后得到的签名 \(T\) 来累计这些权重，就得到分布 \(C(T)\)：
$$C(T)=\#\bigl\{\{a,b\}:1\le a\le b\le N,\ V(a,b)=T\bigr\}.$$
最终答案就是
$$A(N)=\sum_T C(T)^2.$$
从组合意义上说，这表示程序统计的是“有序的无序对对数”：也就是 \((\{a,b\},\{c,d\})\) 这样的两个无序对，只要它们的组合签名相同，就贡献 1。
前五个整数的签名分别是
$$V(1)=(-1,0,\mathbf{0}),\quad V(2)=(0,1,\mathbf{0}),\quad V(3)=(-1/2,0,\mathbf{0}),$$
$$V(4)=(-2,0,\mathbf{0}),\quad V(5)=(-1,1,\mathbf{0}).$$
在 \(1\le a\le b\le 5\) 的条件下，一共有 15 个无序对，但只出现了 12 个不同的组合签名。发生碰撞的只有三组：
$$V(1,1)=V(5,5),\qquad V(1,5)=V(2,4),\qquad V(2,5)=V(3,3).$$
因此有 3 个签名类出现 2 次，另外 9 个签名类出现 1 次，于是
$$A(5)=3\cdot 2^2+9\cdot 1^2=21.$$
这正是实现内置的那个小型校验值。
C++、Python 和 Java 实现都会按从小到大的顺序计算所有 \(0\le n\le N\) 的 \(V(n)\)。因为每一步转移只依赖于商 \(\lfloor n/3\rfloor\)，所以这本质上就是一个沿整数数组做的动态规划。dyadic 标量以缩放后的整数形式保存，奇偶位单独保存，而“零计数剖面”则放在一个固定长度的短向量中；对 \(N=100000\) 来说，这个长度绰绰有余。
唯一不是严格常数时间的更新，就是 \(f=0\) 且当前数是 3 的倍数时触发的特殊 \(0/2\) 分支。在这个分支里，实现会重新扫描当前数的三进制数字，把零计数剖面完整重建一遍。这么做是有理由的：一旦标量部分降到 0，末尾再补一个 0 就可能把之前记录的所有“右侧零数”整体推高 1，因此直接重扫数字比在压缩状态上做局部修补更稳妥。
当 \(V(n)\) 表建好以后，实现会先统计每个不同签名类的频数 \(F(K)\)。这种压缩非常明显：对目标输入来说，100000 个整数最后只剩几千个不同的签名类，所以后续真正昂贵的工作不再发生在整数层面，而是发生在签名类层面。
下一步遍历所有无序的签名类对。对角线上同一类的贡献是 \(\binom{F(K)+1}{2}\)，两类不同则贡献 \(F(K_1)F(K_2)\)。这些权重被加到“组合签名”对应的桶里。等到这个桶映射建立完成，最终答案就是所有桶大小的平方和。
由于最后的计数远远超出有符号 64 位整数的范围，实现在最终求和阶段使用了更大的整数类型：Python 使用原生任意精度整数，Java 使用大整数类型，C++ 则使用无符号 128 位整数。
记 \(U\) 为 \(1,\dots,N\) 之间不同签名的个数。主签名表的构造在本质上是 \(O(N)\) 的，只是在特殊 \(0/2\) 分支上会偶尔多出 \(O(\log_3 N)\) 的重扫。频数压缩阶段是 \(O(N)\)。真正主导运行时间的是 \(O(U^2)\) 的统计阶段，因为每一对无序签名类只处理一次，而且每次组合只涉及三种签名分量上的固定长度运算。
空间方面，签名表本身占 \(O(N)\)，频数映射和组合签名映射分别占 \(O(U)\) 和 \(O(M)\)，其中 \(M\) 是实际出现的不同组合签名数量。对目标输入来说，这一切之所以可行，关键就在于 \(U\) 远小于 \(N\)，于是程序不需要直接遍历所有整数对。
Для каждого целого \(1\le n\le N\) реализации не работают с \(n\) напрямую. Вместо этого числу сопоставляется каноническая троичная сигнатура \(V(n)\), сохраняющая нужный для задачи инвариант. После такой компрессии задача превращается в задачу подсчета: сколько неупорядоченных пар \(\{a,b\}\) и \(\{c,d\}\) с элементами из \([1,N]\) имеют одну и ту же объединенную сигнатуру?
Перебирать все четверки невозможно. Даже прямой перебор всех \(\binom{N+1}{2}\) неупорядоченных пар слишком велик для \(N=100000\). Ключевое наблюдение состоит в том, что многие числа имеют одинаковую сигнатуру, эта сигнатура рекурсивно строится из троичной записи, а значит совпадения пар можно считать по классам, а не по отдельным числам.
Будем писать сигнатуру в виде
$$V(n)=\bigl(f(n),\varepsilon(n),\mathbf{u}(n)\bigr),$$
где \(f(n)\) — неположительное dyadic rational, \(\varepsilon(n)\in\{0,1\}\) — бит четности, а \(\mathbf{u}(n)\) — конечный вектор неотрицательных целых чисел. Вся схема решения опирается на то, что эту сигнатуру можно рекурсивно вычислять по троичным цифрам числа, а сигнатуры пар объединяются покомпонентно.
Пусть \(n=3q+r\), где \(r\in\{0,1,2\}\). Начальное условие такое:
$$V(0)=\bigl(0,0,\mathbf{0}\bigr).$$
Далее все три реализации используют рекурсию
$$V(3q+1)=\bigl(f(q)-1,\varepsilon(q),\mathbf{u}(q)\bigr),$$
$$V(3q+2)=\bigl(f(q),\varepsilon(q)\oplus 1,\mathbf{u}(q)\bigr),$$
и
$$V(3q)=\begin{cases} \bigl(f(q)+1,\varepsilon(q),\mathbf{u}(q)\bigr), & f(q)\le -2,\\ \bigl(f(q)/2,\varepsilon(q),\mathbf{u}(q)\bigr), & -2<f(q)<0,\\ Z(3q), & f(q)=0. \end{cases}$$
В коде значение \(f(n)\) хранится после умножения на фиксированную степень двойки, чтобы все вычитания, прибавления единицы и деления на 2 выполнялись точно в целой арифметике. Это возможно потому, что первая компонента строится только из операций \(-1\), \(+1\) и деления пополам, то есть всегда остается dyadic rational.
Ветвь \(Z(3q)\) не является случайным исключением. Она возникает ровно тогда, когда троичная запись числа \(n\) состоит только из цифр \(0\) и \(2\).
Доказательство короткое и индуктивное. Если мы находимся в состоянии \(f=0\), то приписывание троичной цифры \(2\) оставляет \(f=0\), а приписывание цифры \(0\) тоже сохраняет нулевую первую компоненту через специальную ветвь. Приписывание цифры \(1\) делает первую компоненту отрицательной сразу. Как только \(f<0\), ни один из трех переходов уже не вернет ее к нулю: ветвь \(r=1\) уменьшает значение, ветвь \(r=2\) оставляет его без изменения, а ветвь \(r=0\) либо прибавляет 1 к значению не больше \(-2\), либо делит пополам значение из интервала \((-2,0)\); в обоих случаях результат остается отрицательным. Следовательно,
Эквивалентно: \(f(n)=0\) тогда и только тогда, когда каждая троичная цифра числа \(n\) принадлежит множеству \(\{0,2\}\).
Именно поэтому решение естественно распадается на два режима: обычные числа с \(f(n)<0\) и специальные числа из цифр \(0/2\), где скалярная часть исчезает и ее приходится заменять более тонким комбинаторным профилем.
Пусть \(n=\sum_{i\ge 0} t_i 3^i\), причем все троичные цифры удовлетворяют \(t_i\in\{0,2\}\). Тогда реализации кодируют оставшуюся информацию с помощью бита четности и вектора, который запоминает, сколько нулей находится справа от каждой цифры \(2\).
Бит четности задается формулой
$$\varepsilon(n)\equiv \#\{i:t_i=2\}\pmod 2.$$
Для \(k\ge 1\) определим
$$u_k(n)=\#\Bigl\{i:t_i=2,\ \#\{j<i:t_j=0\}=k\Bigr\}.$$
То есть \(u_k(n)\) считает, сколько цифр \(2\) имеют ровно \(k\) нулей где-то справа от себя. Цифры \(2\), справа от которых нулей нет, влияют только на бит четности и не попадают в сохраняемый вектор. Этот профиль восстанавливается сканированием троичной записи от младшего трита к старшему с поддержанием числа уже встреченных нулей.
Несколько примеров делают правило наглядным. Для \(18=200_3\) бит четности равен 1, а единственная ненулевая компонента вектора — \(u_2=1\). Для \(20=202_3\) бит четности равен 0, а единственная ненулевая компонента — \(u_1=1\), потому что одна цифра \(2\) имеет справа один ноль, а другая не имеет ни одного. Для \(24=220_3\) бит четности снова 0, а единственная ненулевая компонента — \(u_1=2\), поскольку обе цифры \(2\) имеют справа ровно по одному нулю.
После замены числа его сигнатурой пара \(\{a,b\}\) представляется покомпонентной комбинацией
$$V(a,b)=\bigl(f(a)+f(b),\ \varepsilon(a)\oplus\varepsilon(b),\ \mathbf{u}(a)+\mathbf{u}(b)\bigr).$$
Если класс сигнатуры \(K\) встречается \(F(K)\) раз среди чисел \(1,2,\dots,N\), нет смысла перечислять все элементы этого класса по отдельности. Число неупорядоченных пар, возникающих на диагонали одного класса, равно
$$\binom{F(K)+1}{2},$$
а две разные сигнатурные категории \(K_1\) и \(K_2\) дают
$$F(K_1)F(K_2)$$
неупорядоченных пар. Если собирать эти веса по получающейся сигнатуре пары, мы получим распределение \(C(T)\):
$$C(T)=\#\bigl\{\{a,b\}:1\le a\le b\le N,\ V(a,b)=T\bigr\}.$$
Итоговая величина равна
$$A(N)=\sum_T C(T)^2.$$
То есть программа считает упорядоченные пары неупорядоченных пар, попадающих в один и тот же класс объединенной сигнатуры.
Для первых пяти чисел сигнатуры таковы:
$$V(1)=(-1,0,\mathbf{0}),\quad V(2)=(0,1,\mathbf{0}),\quad V(3)=(-1/2,0,\mathbf{0}),$$
$$V(4)=(-2,0,\mathbf{0}),\quad V(5)=(-1,1,\mathbf{0}).$$
Неупорядоченных пар \(\{a,b\}\) при \(1\le a\le b\le 5\) всего 15, но различных объединенных сигнатур возникает только 12. Совпадения такие:
$$V(1,1)=V(5,5),\qquad V(1,5)=V(2,4),\qquad V(2,5)=V(3,3).$$
Значит, три сигнатурных класса встречаются дважды, а девять — по одному разу. Поэтому
$$A(5)=3\cdot 2^2+9\cdot 1^2=21,$$
и именно это значение используется реализациями как встроенная проверка корректности.
Реализации на C++, Python и Java вычисляют \(V(n)\) для всех \(0\le n\le N\) в возрастающем порядке. Поскольку каждый переход зависит только от частного \(\lfloor n/3\rfloor\), это обычный проход динамического программирования по целым числам. Диадическая скалярная часть хранится как масштабированное целое число, бит четности хранится явно, а профиль нулей — в коротком векторе фиксированной длины, более чем достаточной для \(N=100000\).
Единственное обновление не константной стоимости — специальная ветвь для чисел вида \(0/2\) при \(f=0\). В этом случае реализация повторно сканирует троичные цифры текущего числа и заново строит профиль нулей. Это сделано специально: как только скалярная часть схлопнулась к нулю, добавление завершающего нуля может сдвинуть все ранее записанные числа нулей вправо, поэтому пересборка по цифрам надежнее, чем локальная правка уже сжатого профиля.
После построения таблицы \(V(n)\) реализации создают карту частот \(F(K)\) для различных сигнатурных классов. Такое сжатие весьма существенно: для целевого входа 100000 чисел сводятся всего к нескольким тысячам разных сигнатур, поэтому дорогая часть вычисления переносится с отдельных чисел на классы.
Далее перебираются неупорядоченные пары сигнатурных классов. Для диагонального класса прибавляется \(\binom{F(K)+1}{2}\), а для двух разных классов — \(F(K_1)F(K_2)\); все это накапливается в корзине, соответствующей получившейся объединенной сигнатуре. После построения этой карты ответом остается лишь сумма квадратов размеров всех корзин.
Поскольку окончательный результат значительно превосходит диапазон знакового 64-битного типа, на последнем этапе накопления используются расширенные целочисленные типы: встроенная произвольная точность в Python, большие целые в Java и 128-битный беззнаковый тип в C++.
Обозначим через \(U\) число различных сигнатур среди \(1,\dots,N\). Построение основной таблицы по существу линейно по \(N\), за исключением редких дополнительных пересканирований стоимости \(O(\log_3 N)\) в специальной ветви для чисел из цифр \(0/2\). Этап сжатия стоит \(O(N)\). Доминирующая фаза подсчета имеет сложность \(O(U^2)\), потому что каждая неупорядоченная пара сигнатурных классов обрабатывается ровно один раз, а каждая комбинация использует только арифметику фиксированного размера над тремя компонентами сигнатуры.
Память расходуется как \(O(N)\) на таблицу сигнатур и как \(O(U)\) и \(O(M)\) на карту частот и карту объединенных сигнатур пар, где \(M\) — число реально возникающих объединенных сигнатур. Для целевого входа это практично именно потому, что \(U\) существенно меньше \(N\), так что программе не приходится напрямую перебирать все пары целых чисел.
لكل عدد صحيح \(1\le n\le N\)، لا تعمل التطبيقات على \(n\) مباشرة. بدلًا من ذلك تُسنِد إلى \(n\) بصمة ثلاثية معيارية \(V(n)\) تحفظ الكمية الجوهرية في المسألة. بعد هذا الضغط تتحول المهمة إلى مسألة عدّ صِرفة: كم عدد الزوجين غير المرتبين \(\{a,b\}\) و\(\{c,d\}\)، حيث العناصر كلها من \([1,N]\)، اللذين يملكان البصمة المجمعة نفسها؟
العدّ الخام لكل الرباعيات غير ممكن عمليًا. وحتى المرور المباشر على جميع الأزواج غير المرتبة وعددها \(\binom{N+1}{2}\) يبقى ضخمًا عندما \(N=100000\). الفكرة الأساسية في الشيفرات هي أن كثيرًا من الأعداد تشترك في البصمة نفسها، وأن هذه البصمة تُبنى عوديًا من التمثيل الثلاثي، ولذلك يمكن عدّ التطابقات على مستوى فئات البصمات بدلًا من العمل على كل عدد بمفرده.
نكتب البصمة بالشكل
$$V(n)=\bigl(f(n),\varepsilon(n),\mathbf{u}(n)\bigr),$$
حيث إن \(f(n)\) عدد نسبي ثنائي المقام وغير موجب، و\(\varepsilon(n)\in\{0,1\}\) بتّ تكافؤ، و\(\mathbf{u}(n)\) متجه منتهٍ من أعداد صحيحة غير سالبة. يعتمد الحل كله على حقيقتين: يمكن حساب هذه البصمة عوديًا من أرقام \(n\) في النظام الثلاثي، كما أن بصمة الزوج تُبنى بدمج المكونات الثلاثة مباشرة.
لنكتب \(n=3q+r\) حيث \(r\in\{0,1,2\}\). نقطة البداية هي
$$V(0)=\bigl(0,0,\mathbf{0}\bigr).$$
بعد ذلك تستعمل التطبيقات الثلاثة العلاقة
$$V(3q+1)=\bigl(f(q)-1,\varepsilon(q),\mathbf{u}(q)\bigr),$$
$$V(3q+2)=\bigl(f(q),\varepsilon(q)\oplus 1,\mathbf{u}(q)\bigr),$$
وكذلك
$$V(3q)=\begin{cases} \bigl(f(q)+1,\varepsilon(q),\mathbf{u}(q)\bigr), & f(q)\le -2,\\ \bigl(f(q)/2,\varepsilon(q),\mathbf{u}(q)\bigr), & -2<f(q)<0,\\ Z(3q), & f(q)=0. \end{cases}$$
تخزن الشيفرة \(f(n)\) بعد ضربه في قوة ثابتة للعدد 2، بحيث تبقى عمليات الطرح والزيادة والقسمة على 2 دقيقة تمامًا داخل الحساب الصحيح. وهذا ممكن لأن المكوّن الأول لا يُبنى إلا من العمليات \(-1\) و\(+1\) و\(/\!2\)، ولذلك لا تظهر إلا أعداد نسبية ذات مقام قوة للعدد 2.
الفرع \(Z(3q)\) ليس استثناءً اعتباطيًا، بل يظهر بالضبط عندما يحتوي التمثيل الثلاثي للعدد \(n\) على الرقمين \(0\) و\(2\) فقط.
البرهان قصير بالاستقراء. إذا بدأنا من حالة فيها \(f=0\)، فإن إلحاق الرقم الثلاثي \(2\) يبقي \(f\) مساويًا للصفر، كما أن إلحاق الرقم \(0\) يبقي المكوّن الأول صفرًا أيضًا عبر الفرع الخاص. أما إلحاق الرقم \(1\) فيجعل المكوّن الأول سالبًا فورًا. وبعد أن يصبح \(f<0\)، لا يمكن لأي انتقال من الانتقالات الثلاثة أن يعيده إلى الصفر: فرع \(r=1\) ينقصه أكثر، وفرع \(r=2\) يتركه كما هو، وفرع \(r=0\) إما أن يضيف 1 إلى قيمة لا تتجاوز \(-2\) أو يقسم قيمة من المجال \((-2,0)\) على 2، وفي الحالتين تبقى النتيجة سالبة. لذلك
وبصياغة مكافئة، يتحقق \(f(n)=0\) إذا وفقط إذا كان كل رقم ثلاثي في \(n\) من المجموعة \(\{0,2\}\).
ولهذا السبب يقسم الحل المسألة إلى نظامين مختلفين: أعداد عادية يكون فيها \(f(n)<0\)، وأعداد خاصة مكوّنة من الأرقام \(0/2\) فقط، حيث يختفي الجزء العددي السلمي ويصبح لا بد من استعمال توصيف تركيبي أدق.
افترض أن \(n=\sum_{i\ge 0} t_i 3^i\) وأن كل رقم ثلاثي يحقق \(t_i\in\{0,2\}\). عندئذٍ تمثل التطبيقات ما بقي من المعلومات بواسطة بتّ تكافؤ ومتجه يسجل كيف تتوزع الأصفار إلى يمين كل رقم \(2\).
بتّ التكافؤ هو ببساطة
$$\varepsilon(n)\equiv \#\{i:t_i=2\}\pmod 2.$$
ولكل \(k\ge 1\) نعرّف
$$u_k(n)=\#\Bigl\{i:t_i=2,\ \#\{j<i:t_j=0\}=k\Bigr\}.$$
إذًا \(u_k(n)\) يحصي عدد الأرقام \(2\) التي يوجد على يمينها بالضبط \(k\) أصفار. أما الأرقام \(2\) التي لا يوجد على يمينها أي صفر فهي تؤثر في بتّ التكافؤ فقط ولا تدخل في المتجه المخزن. وتعيد التطبيقات بناء هذا الملف عبر مسح التمثيل الثلاثي من أقل trit قيمة إلى أعلاه، مع حفظ عدد الأصفار التي شوهدت حتى تلك اللحظة.
الأمثلة توضح القاعدة مباشرة. في \(18=200_3\) يكون بتّ التكافؤ مساويًا لـ 1، والمدخل غير الصفري الوحيد في المتجه هو \(u_2=1\). وفي \(20=202_3\) يكون بتّ التكافؤ 0، والمدخل غير الصفري الوحيد هو \(u_1=1\)، لأن أحد الرقمين \(2\) على يمينه صفر واحد بينما الآخر لا يوجد على يمينه أي صفر. وفي \(24=220_3\) يكون بتّ التكافؤ 0 أيضًا، والمدخل غير الصفري الوحيد هو \(u_1=2\)، لأن كلا الرقمين \(2\) يقع على يمينه صفر واحد بالضبط.
بعد استبدال كل عدد ببصمته، يُمثَّل الزوج \(\{a,b\}\) بالتركيب المكوّني
$$V(a,b)=\bigl(f(a)+f(b),\ \varepsilon(a)\oplus\varepsilon(b),\ \mathbf{u}(a)+\mathbf{u}(b)\bigr).$$
إذا ظهرت فئة بصمة \(K\) عدد \(F(K)\) من المرات بين \(1,2,\dots,N\)، فلا حاجة إلى تعداد عناصر تلك الفئة عنصرًا عنصرًا. عدد الأزواج غير المرتبة الناتجة من الفئة نفسها على القطر هو
$$\binom{F(K)+1}{2},$$
أما فئتان مختلفتان \(K_1\) و\(K_2\) فتعطيان
$$F(K_1)F(K_2)$$
زوجًا غير مرتب. وعند تجميع هذه الأوزان بحسب بصمة الزوج الناتجة نحصل على توزيع \(C(T)\):
$$C(T)=\#\bigl\{\{a,b\}:1\le a\le b\le N,\ V(a,b)=T\bigr\}.$$
ثم تكون الإجابة النهائية
$$A(N)=\sum_T C(T)^2.$$
وبصياغة توافقية، فالبرنامج يعدّ الأزواج المرتبة من الأزواج غير المرتبة التي تنتهي إلى فئة البصمة المجمعة نفسها.
لبداية المتتالية تكون البصمات كما يلي:
$$V(1)=(-1,0,\mathbf{0}),\quad V(2)=(0,1,\mathbf{0}),\quad V(3)=(-1/2,0,\mathbf{0}),$$
$$V(4)=(-2,0,\mathbf{0}),\quad V(5)=(-1,1,\mathbf{0}).$$
يوجد 15 زوجًا غير مرتب \(\{a,b\}\) مع \(1\le a\le b\le 5\)، لكن عدد البصمات المجمعة المختلفة هو 12 فقط. والتصادمات هي
$$V(1,1)=V(5,5),\qquad V(1,5)=V(2,4),\qquad V(2,5)=V(3,3).$$
إذن هناك ثلاث فئات تظهر مرتين وتسع فئات تظهر مرة واحدة، ومن ثم
$$A(5)=3\cdot 2^2+9\cdot 1^2=21,$$
وهي بالضبط قيمة التحقق الصغيرة المضمنة داخل التطبيقات.
تحسب تطبيقات C++ وPython وJava القيم \(V(n)\) لكل \(0\le n\le N\) بترتيب تصاعدي. ولأن كل انتقال يعتمد فقط على خارج القسمة \(\lfloor n/3\rfloor\)، فإن هذا يساوي مرورًا بسيطًا من نوع البرمجة الديناميكية على الأعداد الصحيحة. يُخزَّن الجزء الديادي كسلسلة صحيحة بعد التحجيم، ويُخزَّن بتّ التكافؤ مباشرة، أما ملفّ عدّ الأصفار فيُحفَظ في متجه قصير بطول ثابت يكفي تمامًا عندما \(N=100000\).
التحديث الوحيد الذي ليس بزمن ثابت هو الفرع الخاص بالأعداد ذات الأرقام \(0/2\) عندما \(f=0\). في هذه الحالة تعيد الشيفرة مسح الأرقام الثلاثية للعدد الحالي كي تعيد بناء ملفّ عدّ الأصفار من جديد. هذا اختيار مقصود: فبعد انهيار الجزء السلمي إلى الصفر، يمكن لإضافة صفر في النهاية أن ترفع جميع أعداد الأصفار المسجلة، ولذلك يكون إعادة البناء من الأرقام نفسها أبسط وأكثر أمانًا من محاولة تعديل الملف المضغوط تعديلًا محليًا.
بعد اكتمال جدول \(V(n)\)، تبني التطبيقات خريطة تكرارات \(F(K)\) لفئات البصمات المختلفة. هذا الضغط مهم جدًا: في الدخل الهدف تنضغط الأعداد المئة ألف إلى بضعة آلاف فقط من البصمات المختلفة، وبالتالي ينتقل الجزء المكلف من الحساب من مستوى الأعداد إلى مستوى الفئات.
في المرحلة التالية يمر التنفيذ على الأزواج غير المرتبة من فئات البصمات. بالنسبة إلى الفئة القطرية يضاف \(\binom{F(K)+1}{2}\)، وبالنسبة إلى فئتين مختلفتين يضاف \(F(K_1)F(K_2)\)، وكل ذلك يُسجَّل في الحاوية المفهرسة بالبصمة المجمعة الناتجة. وبعد اكتمال هذه الخريطة، لا يبقى إلا جمع مربعات أحجام الحاويات كلها.
وبما أن الناتج النهائي أكبر بكثير من مجال الأعداد الصحيحة الموقعة ذات 64 بت، تستعمل التطبيقات في مرحلة التجميع الأخيرة أنواعًا عددية أوسع: دقة اعتباطية أصلية في Python، ونوع الأعداد الصحيحة الكبيرة في Java، ونوعًا غير موقع بطول 128 بت في C++.
ليكن \(U\) عدد البصمات المختلفة بين \(1,\dots,N\). بناء الجدول الرئيسي خطي تقريبًا في \(N\)، مع بعض عمليات المسح الإضافية النادرة بتكلفة \(O(\log_3 N)\) داخل الفرع الخاص بالأعداد ذات الأرقام \(0/2\). أما مرحلة الضغط فتكلف \(O(N)\). والمرحلة المهيمنة هي مرحلة العدّ بتكلفة \(O(U^2)\)، لأن كل زوج غير مرتب من فئات البصمات يُعالَج مرة واحدة فقط، وكل دمج يستعمل حسابًا ثابت الحجم على المكونات الثلاثة للبصمة.
من ناحية الذاكرة، يوجد \(O(N)\) لجدول البصمات، و\(O(U)\) و\(O(M)\) لخريطة التكرارات وخريطة بصمات الأزواج المجمعة، حيث \(M\) هو عدد البصمات المجمعة المختلفة التي تظهر فعليًا. وهذا عملي في الدخل الهدف لأن \(U\) أصغر بكثير من \(N\)، ولذلك لا يحتاج البرنامج إلى فحص جميع أزواج الأعداد مباشرة.