We are given a list of symbolic expressions built from variables and a binary constructor. For each unordered pair of positions containing different expressions, we ask whether a substitution can make the two expression trees identical. If no such substitution exists, that pair contributes \(0\). If a substitution does exist, the resulting common tree is evaluated numerically, and the overall total is taken modulo
$$M=10^9.$$
A brute-force search over all substitutions is hopeless, so the solution works directly with tree structure, recursive unification, and a cache of repeated pair computations.
The key observation is that each pair of expressions can be handled in two stages: first solve the symbolic equation by unification, then evaluate the unified term by a fixed arithmetic rule.
In abstract form, the expressions follow the grammar
$$E ::= v \mid I(E,E),$$
where \(v\) denotes a variable. Thus every expression is either a leaf carrying a variable name or an internal node with exactly two children. Structural equality means same tree shape and same variable labels in the corresponding positions.
This viewpoint turns the problem into a question about tree equations rather than about string manipulation.
For two expressions \(E_1\) and \(E_2\), we seek a substitution \(\sigma\) such that
$$\sigma(E_1)=\sigma(E_2).$$
A substitution maps variables to expressions and extends recursively:
$$\sigma\bigl(I(A,B)\bigr)=I\bigl(\sigma(A),\sigma(B)\bigr).$$
The recursive cases are straightforward. If both current nodes are binary constructor nodes, then their left children must unify and their right children must unify. If one side is a variable, we may bind that variable to the other side, provided the binding is legal. If neither rule applies, the pair cannot be unified.
Before each comparison, already known bindings are followed until the current node is fully resolved. This is why chains such as \(a \mapsto b\) and \(b \mapsto I(c,d)\) behave exactly as the direct binding \(a \mapsto I(c,d)\).
The only dangerous kind of binding is a self-referential one. If a variable \(v\) is to be replaced by a term \(T\), we must require
$$v\notin \operatorname{Vars}(T).$$
This is the classical occurs-check. Without it, an equation such as
$$v=I(v,w)$$
would force an infinite cyclic object instead of an ordinary finite term. The implementations explicitly reject such cases, so any successful unification always produces an acyclic expression tree.
Once unification succeeds, the common term is interpreted numerically. Unbound variables contribute \(0\). For the binary constructor, the recursive valuation rule is
$$J(x,y)=\bigl(1+x+y\bigr)^2+(y-x)\pmod{M}.$$
Equivalently, if \(V_\sigma(E)\) denotes the value of expression \(E\) under the successful substitution \(\sigma\), then
$$V_\sigma(v)=0\quad\text{for an unresolved variable},$$
$$V_\sigma\bigl(I(A,B)\bigr)=J\bigl(V_\sigma(A),V_\sigma(B)\bigr).$$
Therefore the pair contribution is
$$P(E_1,E_2)= \begin{cases} V_\sigma(E_1), & \text{if }E_1\text{ and }E_2\text{ unify},\\ 0, & \text{otherwise}. \end{cases}$$
Because the two expressions become identical after applying \(\sigma\), evaluating either side gives the same value.
The full input may contain many repeated expressions. After converting every parsed tree to one canonical textual form, equal expressions can be merged into unique representatives \(U_0,U_1,\dots,U_{U-1}\).
For those representatives, define the symmetric pair table
$$C_{i,j}=P(U_i,U_j),\qquad C_{i,j}=C_{j,i}.$$
If the original list has \(N\) positions and the expression at position \(p\) corresponds to representative index \(a_p\), then the required total is
$$S=\sum_{\substack{1\le p\lt q\le N \\ a_p\ne a_q}} C_{a_p,a_q}\pmod{M}.$$
The condition \(a_p\ne a_q\) matters: even if the same structural expression appears at different positions, that positional pair is excluded by the problem statement.
Take
$$E_1=I(a,b),\qquad E_2=I(c,I(c,d)).$$
The roots have the same binary shape, so we unify their children. From the left children we get
$$a\mapsto c.$$
From the right children we get
$$b\mapsto I(c,d).$$
This second binding is legal because \(b\) does not occur inside \(I(c,d)\). Hence the pair unifies, and the common resolved tree is
$$I(c,I(c,d)).$$
Now evaluate it. Since \(c\) and \(d\) remain unbound, both contribute \(0\). The inner node gives
$$J(0,0)=(1+0+0)^2+(0-0)=1.$$
The outer node then gives
$$J(0,1)=(1+0+1)^2+(1-0)=4+1=5.$$
So this pair contributes \(5\) modulo \(10^9\). By contrast, the pair \(a\) and \(I(a,b)\) fails immediately, because binding \(a\) to a term that already contains \(a\) violates the occurs-check.
The C++, Python, and Java implementations first parse the entire input into expression trees while preserving the original order and all duplicates. They then serialize each tree into a canonical form so that structurally identical expressions receive the same unique index.
Next, the implementation computes the pair value for every unique-expression pair. Each pair is processed by recursive unification with an occurs-check; if unification succeeds, the resolved tree is evaluated recursively modulo \(10^9\). During evaluation, already resolved subtrees are memoized inside the current pair computation so that repeated branches are not recomputed. The C++ implementation additionally distributes the unique-pair precomputation across several worker tasks, while the Python and Java implementations perform the same logic in direct nested loops.
Finally, the implementations scan all original input positions \((p,q)\) with \(p<q\), skip the pairs whose two positions refer to the same canonical expression, and add the cached value \(C_{a_p,a_q}\) for the remaining pairs.
Let \(N\) be the total number of input expressions, \(U\) the number of distinct structural expressions after deduplication, and \(L\) the total size of all parsed trees. Parsing plus canonicalization is linear in the input size, so it costs \(O(L)\) time.
The dominant symbolic phase is the unique-pair table. Its cost is
$$O\bigl(U^2\cdot T_{\text{pair}}\bigr),$$
where \(T_{\text{pair}}\) is the cost of one unification and, when successful, one recursive evaluation. On ordinary acyclic inputs this is close to linear in the number of visited nodes, although the occurs-check can revisit large subtrees in harder cases. The final positional summation costs \(O(N^2)\) time. Memory usage is \(O(L+U^2)\) for the stored trees and the pair cache. Parallelism in the C++ implementation improves wall-clock time but not the asymptotic bound.
Gegeben ist eine Liste symbolischer Ausdrücke, die aus Variablen und einem binären Konstruktor bestehen. Für jedes ungeordnete Paar von Positionen mit verschiedenen Ausdrücken wird gefragt, ob eine Substitution die beiden Ausdrucksbäume identisch machen kann. Falls keine solche Substitution existiert, trägt das Paar \(0\) bei. Falls sie existiert, wird der gemeinsame vereinheitlichte Baum numerisch ausgewertet, und die Gesamtsumme wird modulo
$$M=10^9$$
gebildet. Eine naive Suche über alle möglichen Substitutionen wäre hoffnungslos, daher arbeitet die Lösung direkt mit Baumstruktur, rekursiver Unifikation und einem Cache für wiederholte Ausdruckspaare.
Die zentrale Beobachtung ist, dass jedes Ausdruckspaar in zwei getrennten Phasen behandelt werden kann: zuerst löst man die symbolische Gleichung durch Unifikation, danach wertet man den vereinheitlichten Term mit einer festen arithmetischen Vorschrift aus.
Abstrakt gilt die Grammatik
$$E ::= v \mid I(E,E),$$
wobei \(v\) eine Variable bezeichnet. Jeder Ausdruck ist also entweder ein Blatt mit Variablennamen oder ein innerer Knoten mit genau zwei Kindern. Strukturelle Gleichheit bedeutet gleiche Baumform und dieselben Variablennamen an den entsprechenden Stellen.
Damit wird das Problem zu einer Gleichung über Bäume und nicht zu einer Frage der Textmanipulation.
Für zwei Ausdrücke \(E_1\) und \(E_2\) suchen wir eine Substitution \(\sigma\) mit
$$\sigma(E_1)=\sigma(E_2).$$
Eine Substitution ordnet Variablen wiederum Ausdrücke zu und setzt sich rekursiv fort:
$$\sigma\bigl(I(A,B)\bigr)=I\bigl(\sigma(A),\sigma(B)\bigr).$$
Die rekursiven Fälle sind klar. Wenn beide aktuellen Knoten binäre Konstruktoren sind, müssen ihre linken Kinder vereinheitlicht werden und ebenso ihre rechten Kinder. Wenn eine Seite eine Variable ist, darf diese Variable an die andere Seite gebunden werden, sofern die Bindung zulässig ist. Trifft keine dieser Regeln zu, scheitert die Unifikation.
Vor jedem Vergleich werden bereits bekannte Bindungen bis zum vollständig aufgelösten Term verfolgt. Deshalb verhalten sich Ketten wie \(a \mapsto b\) und \(b \mapsto I(c,d)\) genauso wie die direkte Bindung \(a \mapsto I(c,d)\).
Gefährlich ist nur eine selbstreferenzielle Bindung. Soll eine Variable \(v\) durch einen Term \(T\) ersetzt werden, muss gelten
$$v\notin \operatorname{Vars}(T).$$
Das ist der klassische Occurs-Check. Ohne ihn würde eine Gleichung wie
$$v=I(v,w)$$
zu einem unendlichen zyklischen Objekt führen statt zu einem endlichen Term. Die Implementierungen verwerfen solche Fälle explizit, daher erzeugt jede erfolgreiche Unifikation immer einen azyklischen Ausdrucksbaum.
Nach erfolgreicher Unifikation wird der gemeinsame Term numerisch interpretiert. Ungebundene Variablen tragen \(0\) bei. Für den binären Konstruktor gilt rekursiv
$$J(x,y)=\bigl(1+x+y\bigr)^2+(y-x)\pmod{M}.$$
Bezeichnet \(V_\sigma(E)\) den Wert des Ausdrucks \(E\) unter der erfolgreichen Substitution \(\sigma\), dann gilt
$$V_\sigma(v)=0\quad\text{für eine unaufgelöste Variable},$$
$$V_\sigma\bigl(I(A,B)\bigr)=J\bigl(V_\sigma(A),V_\sigma(B)\bigr).$$
Damit ist der Beitrag eines Paares
$$P(E_1,E_2)= \begin{cases} V_\sigma(E_1), & \text{falls }E_1\text{ und }E_2\text{ vereinheitlichbar sind},\\ 0, & \text{sonst}. \end{cases}$$
Da beide Ausdrücke nach Anwendung von \(\sigma\) identisch werden, liefert die Auswertung jeder Seite denselben Wert.
Die vollständige Eingabe kann viele Wiederholungen enthalten. Wenn jeder geparste Baum in eine kanonische Textform überführt wird, lassen sich gleiche Ausdrücke zu eindeutigen Repräsentanten \(U_0,U_1,\dots,U_{U-1}\) zusammenfassen.
Für diese Repräsentanten definieren wir die symmetrische Paar-Tabelle
$$C_{i,j}=P(U_i,U_j),\qquad C_{i,j}=C_{j,i}.$$
Hat die ursprüngliche Liste \(N\) Positionen und gehört der Ausdruck an Position \(p\) zum Repräsentanten mit Index \(a_p\), dann ist die gesuchte Summe
$$S=\sum_{\substack{1\le p\lt q\le N \\ a_p\ne a_q}} C_{a_p,a_q}\pmod{M}.$$
Die Bedingung \(a_p\ne a_q\) ist wesentlich: Selbst wenn derselbe strukturelle Ausdruck an mehreren Positionen steht, wird dieses Positionspaar laut Aufgabenstellung ausgelassen.
Betrachte
$$E_1=I(a,b),\qquad E_2=I(c,I(c,d)).$$
Die Wurzeln haben dieselbe binäre Form, also vereinheitlichen wir die Kinder. Aus den linken Kindern folgt
$$a\mapsto c.$$
Aus den rechten Kindern folgt
$$b\mapsto I(c,d).$$
Diese zweite Bindung ist zulässig, weil \(b\) in \(I(c,d)\) nicht vorkommt. Das Paar ist also vereinheitlichbar, und der gemeinsame aufgelöste Baum lautet
$$I(c,I(c,d)).$$
Nun werten wir aus. Da \(c\) und \(d\) ungebunden bleiben, tragen beide \(0\) bei. Der innere Knoten liefert
$$J(0,0)=(1+0+0)^2+(0-0)=1.$$
Der äußere Knoten liefert dann
$$J(0,1)=(1+0+1)^2+(1-0)=4+1=5.$$
Dieses Paar trägt also \(5\) modulo \(10^9\) bei. Dagegen scheitert das Paar \(a\) und \(I(a,b)\) sofort, weil die Bindung von \(a\) an einen Term mit erneutem \(a\) gegen den Occurs-Check verstößt.
Die C++-, Python- und Java-Implementierungen parsen zunächst die gesamte Eingabe zu Ausdrucksbäumen und bewahren dabei die ursprüngliche Reihenfolge sowie alle Duplikate. Danach wird jeder Baum in eine kanonische Form serialisiert, sodass strukturell gleiche Ausdrücke denselben eindeutigen Index erhalten.
Anschließend berechnet die Implementierung für jedes Paar eindeutiger Ausdrücke den Paarwert. Jedes Paar wird mit rekursiver Unifikation samt Occurs-Check verarbeitet; bei Erfolg wird der aufgelöste Baum rekursiv modulo \(10^9\) ausgewertet. Während dieser Auswertung werden bereits aufgelöste Teilbäume innerhalb des aktuellen Paars zwischengespeichert, damit wiederholte Teilstrukturen nicht mehrfach berechnet werden. Die C++-Implementierung verteilt die Vorberechnung der eindeutigen Paare zusätzlich auf mehrere Arbeitseinheiten, während Python und Java dieselbe Logik in direkten Doppelschleifen ausführen.
Zum Schluss werden alle ursprünglichen Positionspaare \((p,q)\) mit \(p<q\) durchlaufen, Paare mit demselben kanonischen Ausdruck werden übersprungen, und für alle übrigen wird der gecachte Wert \(C_{a_p,a_q}\) addiert.
Sei \(N\) die Gesamtzahl der Eingabeausdrücke, \(U\) die Zahl der verschiedenen strukturellen Ausdrücke nach der Deduplikation und \(L\) die Gesamtgröße aller geparsten Bäume. Parsing und Kanonisierung sind linear in der Eingabegröße und kosten daher \(O(L)\) Zeit.
Die dominante symbolische Phase ist die Tabelle der eindeutigen Paare. Ihr Aufwand beträgt
$$O\bigl(U^2\cdot T_{\text{pair}}\bigr),$$
wobei \(T_{\text{pair}}\) die Kosten einer Unifikation und, im Erfolgsfall, einer rekursiven Auswertung bezeichnet. Für gewöhnliche azyklische Eingaben liegt das nahe an linear in der Zahl der besuchten Knoten, auch wenn der Occurs-Check in schwierigeren Fällen große Teilbäume erneut betrachten kann. Die abschließende Summation über Positionen kostet \(O(N^2)\) Zeit. Der Speicherverbrauch liegt bei \(O(L+U^2)\) für die gespeicherten Bäume und den Paar-Cache. Parallelisierung in C++ verbessert die reale Laufzeit, aber nicht die asymptotische Schranke.
Elimizde değişkenlerden ve ikili bir kurucudan oluşan sembolik ifadelerin bir listesi vardır. Farklı ifadeler içeren her sırasız konum çifti için, bir substitüsyonun bu iki ifade ağacını aynı hale getirip getiremeyeceği sorulur. Böyle bir substitüsyon yoksa o çiftin katkısı \(0\) olur. Varsa, elde edilen ortak ağaç sayısal olarak değerlendirilir ve toplam sonuç
$$M=10^9$$
modunda alınır. Tüm substitüsyonları kaba kuvvetle denemek imkansız olduğundan çözüm, doğrudan ağaç yapısı, özyinelemeli unification ve tekrar eden çiftler için önbellek kullanır.
Ana fikir, her ifade çiftini iki aşamada ele almaktır: önce sembolik denklemi unification ile çözmek, sonra ortaya çıkan ortak terimi sabit bir aritmetik kuralla değerlendirmek.
İfadelerin soyut grameri
$$E ::= v \mid I(E,E)$$
şeklindedir; burada \(v\) bir değişken adıdır. Buna göre her ifade ya değişken taşıyan bir yaprak ya da tam iki çocuğu olan bir iç düğümdür. Yapısal eşitlik, aynı ağaç biçimini ve karşılık gelen konumlarda aynı değişken etiketlerini gerektirir.
Böylece problem bir metin karşılaştırması değil, ağaç denklemleri problemi haline gelir.
İki ifade \(E_1\) ve \(E_2\) için amaç,
$$\sigma(E_1)=\sigma(E_2)$$
eşitliğini sağlayan bir substitüsyon \(\sigma\) bulmaktır. Substitüsyon, değişkenleri yine ifadelere eşler ve ağaç boyunca özyinelemeli uygulanır:
$$\sigma\bigl(I(A,B)\bigr)=I\bigl(\sigma(A),\sigma(B)\bigr).$$
Kurallar doğaldır. İki mevcut düğüm de ikili kurucu ise sol çocuklar kendi aralarında, sağ çocuklar da kendi aralarında birleşmelidir. Taraflardan biri değişkense, bu değişkenin öteki tarafa bağlanmasına izin verilir; ama bağın yasal olması gerekir. Bu durumların hiçbiri uygulanamıyorsa çift birleşemez.
Her karşılaştırmadan önce daha önce bilinen bağlar sonuna kadar takip edilir. Bu yüzden \(a \mapsto b\) ve \(b \mapsto I(c,d)\) zinciri, doğrudan \(a \mapsto I(c,d)\) bağlanmış gibi davranır.
Asıl tehlike, kendi içine referans veren bir bağ kurmaktır. Bir \(v\) değişkeni \(T\) terimine bağlanacaksa
$$v\notin \operatorname{Vars}(T)$$
koşulu sağlanmalıdır. Bu klasik occurs-check'tir. Aksi halde
$$v=I(v,w)$$
gibi bir denklem, sonlu bir terim yerine sonsuz döngüsel bir nesne üretir. Uygulamalar bu tür durumları açıkça reddettiği için başarılı her unification sonlu ve döngüsüz bir ifade ağacı verir.
Unification başarılı olunca ortak terim sayısal olarak yorumlanır. Bağlanmamış değişkenlerin katkısı \(0\)'dır. İkili kurucu için özyinelemeli değerleme kuralı
$$J(x,y)=\bigl(1+x+y\bigr)^2+(y-x)\pmod{M}$$
şeklindedir. Başarılı substitüsyon \(\sigma\) altında \(E\) ifadesinin değerini \(V_\sigma(E)\) ile gösterirsek
$$V_\sigma(v)=0\quad\text{bağlanmamış değişken için},$$
$$V_\sigma\bigl(I(A,B)\bigr)=J\bigl(V_\sigma(A),V_\sigma(B)\bigr).$$
Dolayısıyla çift katkısı
$$P(E_1,E_2)= \begin{cases} V_\sigma(E_1), & \text{eğer }E_1\text{ ile }E_2\text{ birleşebiliyorsa},\\ 0, & \text{aksi halde}. \end{cases}$$
\(\sigma\) uygulandıktan sonra iki taraf aynı ağaca dönüştüğü için, hangi tarafı değerlendirirsek değerlendirelim aynı sonuç elde edilir.
Tam girdi birçok tekrar içerebilir. Her ayrıştırılmış ağacı tek bir kanonik metin biçimine dönüştürdüğümüzde, eşit ifadeleri \(U_0,U_1,\dots,U_{U-1}\) biçiminde benzersiz temsilcilere indirebiliriz.
Bu temsilciler için simetrik çift tablosunu
$$C_{i,j}=P(U_i,U_j),\qquad C_{i,j}=C_{j,i}$$
şeklinde tanımlayalım. Özgün listede \(N\) konum olsun ve \(p\). konumdaki ifade, \(a_p\) indisli temsilciye ait olsun. O zaman istenen toplam
$$S=\sum_{\substack{1\le p\lt q\le N \\ a_p\ne a_q}} C_{a_p,a_q}\pmod{M}$$
olur. Buradaki \(a_p\ne a_q\) koşulu önemlidir: aynı yapısal ifade iki farklı konumda tekrar etse bile, bu konum çifti soruda istenen toplamın dışında bırakılır.
Şu çifti ele alalım:
$$E_1=I(a,b),\qquad E_2=I(c,I(c,d)).$$
Kökler aynı ikili yapıya sahip olduğu için çocukları birleştiririz. Sol çocuklardan
$$a\mapsto c$$
elde edilir. Sağ çocuklardan ise
$$b\mapsto I(c,d)$$
çıkar. Bu ikinci bağ yasaldır, çünkü \(b\), \(I(c,d)\) içinde geçmez. Dolayısıyla çift birleşir ve ortak çözülmüş ağaç
$$I(c,I(c,d))$$
olur. Şimdi bunu değerlendirelim. \(c\) ve \(d\) bağlanmamış kaldığı için ikisi de \(0\) katkı verir. İç düğüm
$$J(0,0)=(1+0+0)^2+(0-0)=1$$
sonucunu verir. Dış düğüm ise
$$J(0,1)=(1+0+1)^2+(1-0)=4+1=5$$
olur. Yani bu çiftin katkısı \(10^9\) modunda \(5\)'tir. Buna karşılık \(a\) ile \(I(a,b)\) çifti hemen başarısız olur; çünkü \(a\)'yı yine \(a\) içeren bir terime bağlamak occurs-check kuralını bozar.
C++, Python ve Java uygulamaları önce tüm girdiyi ifade ağaçlarına ayrıştırır; bunu yaparken özgün sırayı ve tüm tekrarları korur. Ardından her ağaç kanonik bir metin biçimine dönüştürülür; böylece yapısal olarak aynı olan ifadeler aynı benzersiz indeksi alır.
Sonra uygulama, her benzersiz ifade çifti için çift değerini hesaplar. Her çift, occurs-check içeren özyinelemeli unification ile işlenir; birleşme başarılıysa çözülmüş ağaç \(10^9\) modunda özyinelemeli olarak değerlendirilir. Bu değerlendirme sırasında, o çifte ait çözülmüş alt ağaçlar tekrar hesaplanmasın diye geçici olarak önbelleğe alınır. C++ uygulaması bu benzersiz-çift önhesaplamasını birden fazla iş parçacığına dağıtır; Python ve Java ise aynı mantığı doğrudan iç içe döngülerle uygular.
Son aşamada tüm özgün konum çiftleri \((p,q)\) için \(p<q\) koşulu altında dolaşılır, aynı kanonik ifadeye işaret eden çiftler atlanır ve kalanlar için önbellekteki \(C_{a_p,a_q}\) değeri toplama eklenir.
\(N\) toplam ifade sayısı, \(U\) tekrarlar birleştirildikten sonraki farklı yapısal ifade sayısı ve \(L\) de ayrıştırılmış tüm ağaçların toplam boyu olsun. Ayrıştırma ve kanonikleştirme girdi boyutunda lineerdir; dolayısıyla zaman maliyeti \(O(L)\)'dir.
Baskın sembolik aşama benzersiz çift tablosudur. Bunun maliyeti
$$O\bigl(U^2\cdot T_{\text{pair}}\bigr)$$
şeklindedir; burada \(T_{\text{pair}}\), tek bir unification ile, başarı durumunda, tek bir özyinelemeli değerlendirmenin maliyetidir. Sıradan döngüsüz girdilerde bu maliyet ziyaret edilen düğüm sayısına yakın lineer davranır; yine de occurs-check zor örneklerde büyük alt ağaçlara tekrar bakabilir. Son konumsal toplama \(O(N^2)\) zaman ister. Bellek kullanımı, saklanan ağaçlar ve çift önbelleği için \(O(L+U^2)\)'dir. C++ sürümündeki paralellik duvar saati süresini azaltır, ancak asimptotik sınırı değiştirmez.
Se nos da una lista de expresiones simbólicas construidas con variables y un constructor binario. Para cada par no ordenado de posiciones que contienen expresiones distintas, se pregunta si existe una sustitución capaz de volver idénticos ambos árboles. Si no existe tal sustitución, ese par aporta \(0\). Si sí existe, el árbol común resultante se evalúa numéricamente y la suma total se toma módulo
$$M=10^9.$$
Una búsqueda ingenua sobre todas las sustituciones posibles sería inviable, así que la solución trabaja directamente sobre la estructura de árbol, la unificación recursiva y una caché para pares repetidos de expresiones.
La observación clave es que cada par puede tratarse en dos etapas separadas: primero se resuelve la ecuación simbólica mediante unificación; después se evalúa el término ya unificado con una regla aritmética fija.
En forma abstracta, las expresiones siguen la gramática
$$E ::= v \mid I(E,E),$$
donde \(v\) representa una variable. Por tanto, cada expresión es o bien una hoja con un nombre de variable o bien un nodo interno con exactamente dos hijos. La igualdad estructural significa misma forma de árbol y las mismas etiquetas de variable en las posiciones correspondientes.
Así, el problema se convierte en una ecuación entre árboles y no en una mera comparación de cadenas.
Dados dos términos \(E_1\) y \(E_2\), buscamos una sustitución \(\sigma\) tal que
$$\sigma(E_1)=\sigma(E_2).$$
Una sustitución asigna expresiones a variables y se extiende de forma recursiva:
$$\sigma\bigl(I(A,B)\bigr)=I\bigl(\sigma(A),\sigma(B)\bigr).$$
Las reglas son directas. Si ambos nodos actuales son constructores binarios, entonces sus hijos izquierdos deben unificarse y también sus hijos derechos. Si uno de los lados es una variable, se permite ligar esa variable al otro lado siempre que la ligadura sea válida. Si ninguna de estas reglas aplica, la unificación falla.
Antes de cada comparación se siguen todas las ligaduras ya conocidas hasta llegar al término realmente resuelto. Por eso una cadena como \(a \mapsto b\) y \(b \mapsto I(c,d)\) se comporta igual que la ligadura directa \(a \mapsto I(c,d)\).
El único tipo de ligadura peligroso es el autorreferencial. Si una variable \(v\) va a sustituirse por un término \(T\), debe cumplirse
$$v\notin \operatorname{Vars}(T).$$
Ese es el occurs-check clásico. Sin él, una ecuación como
$$v=I(v,w)$$
obligaría a construir un objeto infinito y cíclico en lugar de un término finito. Las implementaciones descartan explícitamente esos casos, así que cualquier unificación exitosa produce siempre un árbol acíclico.
Cuando la unificación tiene éxito, el término común se interpreta numéricamente. Las variables no ligadas aportan \(0\). Para el constructor binario, la regla recursiva es
$$J(x,y)=\bigl(1+x+y\bigr)^2+(y-x)\pmod{M}.$$
Si \(V_\sigma(E)\) denota el valor de la expresión \(E\) bajo la sustitución exitosa \(\sigma\), entonces
$$V_\sigma(v)=0\quad\text{para una variable no resuelta},$$
$$V_\sigma\bigl(I(A,B)\bigr)=J\bigl(V_\sigma(A),V_\sigma(B)\bigr).$$
En consecuencia, la contribución del par es
$$P(E_1,E_2)= \begin{cases} V_\sigma(E_1), & \text{si }E_1\text{ y }E_2\text{ unifican},\\ 0, & \text{en caso contrario}. \end{cases}$$
Como tras aplicar \(\sigma\) los dos lados se vuelven idénticos, evaluar cualquiera de ellos da el mismo resultado.
La entrada completa puede contener muchas repeticiones. Si cada árbol ya parseado se convierte a una única forma textual canónica, las expresiones iguales pueden agruparse en representantes únicos \(U_0,U_1,\dots,U_{U-1}\).
Para esos representantes definimos la tabla simétrica de pares
$$C_{i,j}=P(U_i,U_j),\qquad C_{i,j}=C_{j,i}.$$
Si la lista original tiene \(N\) posiciones y la expresión en la posición \(p\) corresponde al índice \(a_p\), entonces la suma pedida es
$$S=\sum_{\substack{1\le p\lt q\le N \\ a_p\ne a_q}} C_{a_p,a_q}\pmod{M}.$$
La restricción \(a_p\ne a_q\) es esencial: aunque una misma expresión estructural aparezca varias veces, ese par de posiciones queda excluido por el enunciado.
Tomemos
$$E_1=I(a,b),\qquad E_2=I(c,I(c,d)).$$
Las raíces tienen la misma forma binaria, así que unificamos sus hijos. De los hijos izquierdos obtenemos
$$a\mapsto c.$$
De los hijos derechos obtenemos
$$b\mapsto I(c,d).$$
Esta segunda ligadura es válida porque \(b\) no aparece dentro de \(I(c,d)\). Por tanto, el par unifica y el árbol común resuelto es
$$I(c,I(c,d)).$$
Ahora lo evaluamos. Como \(c\) y \(d\) permanecen libres, ambos aportan \(0\). El nodo interior vale
$$J(0,0)=(1+0+0)^2+(0-0)=1.$$
El nodo exterior vale entonces
$$J(0,1)=(1+0+1)^2+(1-0)=4+1=5.$$
Así, este par contribuye \(5\) módulo \(10^9\). En cambio, el par \(a\) e \(I(a,b)\) falla de inmediato porque ligar \(a\) a un término que ya contiene \(a\) violaría el occurs-check.
Las implementaciones en C++, Python y Java primero analizan toda la entrada para construir árboles de expresión, conservando el orden original y todos los duplicados. Luego cada árbol se convierte a una forma canónica, de modo que las expresiones estructuralmente iguales reciben el mismo índice único.
Después, la implementación calcula el valor de cada par de expresiones únicas. Cada par se procesa con unificación recursiva y occurs-check; si la unificación tiene éxito, el árbol resuelto se evalúa recursivamente módulo \(10^9\). Durante esa evaluación, los subárboles ya resueltos se memorizan dentro del cálculo del par actual para no recomputar ramas repetidas. La implementación en C++ además reparte la precomputación de pares únicos entre varias tareas de trabajo, mientras que Python y Java ejecutan la misma lógica mediante bucles anidados directos.
Finalmente, las implementaciones recorren todos los pares de posiciones originales \((p,q)\) con \(p<q\), omiten los casos en que ambas posiciones apuntan a la misma expresión canónica y suman el valor en caché \(C_{a_p,a_q}\) para los restantes.
Sea \(N\) el número total de expresiones de entrada, \(U\) el número de expresiones estructuralmente distintas tras eliminar duplicados y \(L\) el tamaño total de todos los árboles parseados. El análisis sintáctico y la canonización son lineales en el tamaño de la entrada, así que cuestan \(O(L)\) tiempo.
La fase simbólica dominante es la tabla de pares únicos. Su coste es
$$O\bigl(U^2\cdot T_{\text{pair}}\bigr),$$
donde \(T_{\text{pair}}\) representa el coste de una unificación y, si procede, de una evaluación recursiva. En entradas acíclicas normales, ese coste es casi lineal en el número de nodos visitados, aunque el occurs-check puede volver a recorrer subárboles grandes en casos más duros. La suma final sobre posiciones cuesta \(O(N^2)\) tiempo. La memoria usada es \(O(L+U^2)\) para los árboles almacenados y la caché de pares. El paralelismo de la implementación en C++ reduce el tiempo real de ejecución, pero no la cota asintótica.
题目给出一列由变量和一个二元构造子组成的符号表达式。对于每一对位置不同且表达式本身也不同的无序位置对，我们要判断是否存在某个替换，使得这两棵表达式树完全相同。如果不存在这样的替换，这一对的贡献就是 \(0\)。如果存在，就把统一后的公共表达式做数值计算，最后把所有贡献对
$$M=10^9$$
取模。显然不可能暴力枚举所有替换，因此解法必须直接利用树结构、递归统一以及重复表达式对的缓存。
核心思路是把每一对表达式分成两个阶段处理：先通过统一算法解出符号层面的等式，再按照固定的算术规则对统一后的公共项做递归求值。
从抽象角度看，表达式满足语法
$$E ::= v \mid I(E,E),$$
其中 \(v\) 表示变量。因此每个表达式要么是一个带变量名的叶子，要么是一个恰好有两个孩子的内部节点。所谓结构相同，就是树形相同，并且对应位置上的变量标签也相同。
这样一来，问题就不再是字符串比较，而是关于二叉树方程是否可解的问题。
给定两个表达式 \(E_1\) 与 \(E_2\)，我们寻找一个替换 \(\sigma\)，使得
$$\sigma(E_1)=\sigma(E_2).$$
替换的作用是把变量映射到另一个表达式，并且沿树递归传播：
$$\sigma\bigl(I(A,B)\bigr)=I\bigl(\sigma(A),\sigma(B)\bigr).$$
统一过程的规则很直接。如果当前两个节点都是二元构造子，那么它们的左子树必须统一，右子树也必须统一。如果一边是变量，就尝试把这个变量绑定到另一边对应的项上，只要这种绑定是合法的。如果这些规则都无法应用，统一就失败。
在每一次比较之前，都要先沿着已有绑定把当前节点追踪到最终解析后的形态。因此，像 \(a \mapsto b\) 再加上 \(b \mapsto I(c,d)\) 这样的绑定链，和直接得到 \(a \mapsto I(c,d)\) 的效果完全一样。
最危险的情况是自引用绑定。若变量 \(v\) 想要绑定到项 \(T\)，就必须满足
$$v\notin \operatorname{Vars}(T).$$
这就是经典的 occurs-check。没有这一步的话，方程
$$v=I(v,w)$$
就会迫使我们构造一个无限循环对象，而不是普通的有限项。三份实现都显式拒绝这种情况，所以任何成功的统一都会得到一个无环的有限表达式树。
统一成功后，得到的公共项要做数值解释。没有被绑定到具体表达式的变量，数值视为 \(0\)。二元构造子的递归数值规则为
$$J(x,y)=\bigl(1+x+y\bigr)^2+(y-x)\pmod{M}.$$
如果记 \(V_\sigma(E)\) 为表达式 \(E\) 在成功替换 \(\sigma\) 下的值，那么
$$V_\sigma(v)=0\quad\text{当 }v\text{ 仍然是自由变量时},$$
$$V_\sigma\bigl(I(A,B)\bigr)=J\bigl(V_\sigma(A),V_\sigma(B)\bigr).$$
于是，一个表达式对的贡献可以写成
$$P(E_1,E_2)= \begin{cases} V_\sigma(E_1), & \text{若 }E_1\text{ 与 }E_2\text{ 可以统一},\\ 0, & \text{否则}. \end{cases}$$
因为统一完成后两边已经变成同一棵树，所以评价左边或右边得到的数值完全一致。
完整输入中可能含有大量重复项。只要把每棵解析后的树转换为唯一的规范文本形式，相同的结构就能合并成唯一代表 \(U_0,U_1,\dots,U_{U-1}\)。
对这些代表，定义对称的配对表
$$C_{i,j}=P(U_i,U_j),\qquad C_{i,j}=C_{j,i}.$$
若原始输入共有 \(N\) 个位置，第 \(p\) 个位置对应的唯一代表编号为 \(a_p\)，那么题目要求的总和就是
$$S=\sum_{\substack{1\le p\lt q\le N \\ a_p\ne a_q}} C_{a_p,a_q}\pmod{M}.$$
其中条件 \(a_p\ne a_q\) 非常关键：即使同一个结构化表达式在多个位置上重复出现，这种位置对也不计入最终答案。
考虑下面这一对：
$$E_1=I(a,b),\qquad E_2=I(c,I(c,d)).$$
两个根节点具有相同的二元结构，因此分别统一左右子树。由左子树得到
$$a\mapsto c,$$
由右子树得到
$$b\mapsto I(c,d).$$
第二个绑定是合法的，因为 \(b\) 并没有出现在 \(I(c,d)\) 内部。于是这一对可以统一，其解析后的公共树为
$$I(c,I(c,d)).$$
接下来做数值计算。由于 \(c\) 与 \(d\) 都没有继续绑定到别的表达式，所以它们都按 \(0\) 处理。内部节点的值是
$$J(0,0)=(1+0+0)^2+(0-0)=1.$$
外部节点的值于是为
$$J(0,1)=(1+0+1)^2+(1-0)=4+1=5.$$
因此这一对的贡献是 \(5\)（模 \(10^9\) 下当然仍然是 \(5\)）。相对地，表达式 \(a\) 与 \(I(a,b)\) 这一对会立刻失败，因为若把 \(a\) 绑定到一个内部还含有 \(a\) 的项，就违反了 occurs-check。
C++、Python 和 Java 三份实现都先把完整输入解析成表达式树，并保留原始顺序以及所有重复项。接着，每棵树都会被转成规范形式，这样结构完全相同的表达式就会得到同一个唯一编号。
然后，程序为每一对唯一表达式计算一次配对值。每个配对都会执行带 occurs-check 的递归统一；若统一成功，就对解析后的公共树递归求值并对 \(10^9\) 取模。在这个求值过程中，当前配对内已经解析过的子树会被暂存，从而避免重复计算相同分支。C++ 实现还会把唯一表达式对的预计算拆分到多个工作任务上并行完成，而 Python 与 Java 则用直接的双重循环执行同样的逻辑。
最后，程序遍历所有原始位置对 \((p,q)\) 且满足 \(p<q\)，跳过那些指向同一个规范表达式的情况，把其余位置对对应的缓存值 \(C_{a_p,a_q}\) 加入总和。
设 \(N\) 为输入表达式总数，\(U\) 为去重后的不同结构表达式数，\(L\) 为所有解析树节点数之和。解析与规范化对输入规模是线性的，因此耗时为 \(O(L)\)。
主导性的符号计算阶段是唯一表达式配对表，其复杂度为
$$O\bigl(U^2\cdot T_{\text{pair}}\bigr),$$
这里 \(T_{\text{pair}}\) 表示一次统一以及在成功时一次递归求值的代价。对一般的无环输入来说，这个代价通常接近于访问节点数的线性规模；不过在较难的情况下，occurs-check 可能会重复查看较大的子树。最后按原始位置求和需要 \(O(N^2)\) 时间。内存复杂度为 \(O(L+U^2)\)，分别来自存储的表达式树和唯一配对缓存。C++ 版本的并行化只能改善实际运行时间，不会改变渐近量级。
Дан список символических выражений, построенных из переменных и одного бинарного конструктора. Для каждой неупорядоченной пары позиций, в которых стоят разные выражения, нужно определить, существует ли такая подстановка, которая делает оба дерева выражений одинаковыми. Если такой подстановки нет, вклад пары равен \(0\). Если она есть, общий унифицированный терм вычисляется численно, а итоговая сумма берется по модулю
$$M=10^9.$$
Полный перебор всех подстановок невозможен, поэтому решение опирается непосредственно на древесную структуру термов, рекурсивную унификацию и кеширование повторяющихся пар выражений.
Ключевая идея состоит в том, что каждую пару выражений удобно обрабатывать в два этапа: сначала решить символическое уравнение унификацией, а затем вычислить получившийся общий терм по фиксированному арифметическому правилу.
В абстрактной записи выражения задаются грамматикой
$$E ::= v \mid I(E,E),$$
где \(v\) обозначает переменную. Значит, каждое выражение либо является листом с именем переменной, либо внутренней вершиной с двумя потомками. Структурное равенство означает одинаковую форму дерева и одинаковые имена переменных в соответствующих местах.
После такой интерпретации задача становится задачей о равенстве деревьев, а не о сравнении строк.
Для двух выражений \(E_1\) и \(E_2\) нужно найти подстановку \(\sigma\), такую что
$$\sigma(E_1)=\sigma(E_2).$$
Подстановка сопоставляет переменным выражения и продолжается рекурсивно по дереву:
$$\sigma\bigl(I(A,B)\bigr)=I\bigl(\sigma(A),\sigma(B)\bigr).$$
Правила стандартны. Если обе текущие вершины являются бинарными конструкторами, то должны унифицироваться их левые поддеревья и их правые поддеревья. Если одна из сторон является переменной, можно попытаться связать эту переменную с другой стороной, при условии что такая связь допустима. Если ни одно из правил не применимо, унификация завершается неудачей.
Перед каждым сравнением уже известные связи разворачиваются до конца. Поэтому цепочка \(a \mapsto b\) и \(b \mapsto I(c,d)\) ведет себя точно так же, как прямая связь \(a \mapsto I(c,d)\).
Опасной является только самоссылочная связь. Если переменную \(v\) собираются связать с термом \(T\), необходимо условие
$$v\notin \operatorname{Vars}(T).$$
Это и есть классический occurs-check. Без него уравнение
$$v=I(v,w)$$
привело бы к бесконечному циклическому объекту вместо обычного конечного терма. Все три реализации явно отвергают такие случаи, поэтому любая успешная унификация всегда дает ациклическое дерево выражения.
После успешной унификации общий терм получает численную интерпретацию. Неразрешенные переменные дают вклад \(0\). Для бинарного конструктора используется рекурсивное правило
$$J(x,y)=\bigl(1+x+y\bigr)^2+(y-x)\pmod{M}.$$
Если \(V_\sigma(E)\) обозначает значение выражения \(E\) при успешной подстановке \(\sigma\), то
$$V_\sigma(v)=0\quad\text{для неразрешенной переменной},$$
$$V_\sigma\bigl(I(A,B)\bigr)=J\bigl(V_\sigma(A),V_\sigma(B)\bigr).$$
Тогда вклад пары равен
$$P(E_1,E_2)= \begin{cases} V_\sigma(E_1), & \text{если }E_1\text{ и }E_2\text{ унифицируются},\\ 0, & \text{иначе}. \end{cases}$$
После применения \(\sigma\) обе стороны совпадают, поэтому вычисление любой из них дает один и тот же результат.
Во входных данных может быть много повторов. Если каждое разобранное дерево перевести в единственную каноническую текстовую форму, одинаковые выражения можно объединить в уникальные представители \(U_0,U_1,\dots,U_{U-1}\).
Для этих представителей введем симметричную таблицу пар
$$C_{i,j}=P(U_i,U_j),\qquad C_{i,j}=C_{j,i}.$$
Пусть во входном списке \(N\) позиций, а выражение в позиции \(p\) соответствует индексу \(a_p\). Тогда искомая сумма имеет вид
$$S=\sum_{\substack{1\le p\lt q\le N \\ a_p\ne a_q}} C_{a_p,a_q}\pmod{M}.$$
Условие \(a_p\ne a_q\) существенно: даже если одно и то же структурное выражение встречается несколько раз, такая пара позиций не учитывается в ответе.
Рассмотрим
$$E_1=I(a,b),\qquad E_2=I(c,I(c,d)).$$
Корни имеют одинаковую бинарную форму, значит унифицируем их потомков. Из левых потомков получаем
$$a\mapsto c.$$
Из правых потомков получаем
$$b\mapsto I(c,d).$$
Вторая связь допустима, потому что \(b\) не входит внутрь \(I(c,d)\). Следовательно, пара унифицируется, а общий разрешенный терм равен
$$I(c,I(c,d)).$$
Теперь вычислим его. Поскольку \(c\) и \(d\) остаются свободными, оба дают \(0\). Внутренний узел равен
$$J(0,0)=(1+0+0)^2+(0-0)=1.$$
Тогда внешний узел равен
$$J(0,1)=(1+0+1)^2+(1-0)=4+1=5.$$
Значит, эта пара дает вклад \(5\) по модулю \(10^9\). Для контраста, пара \(a\) и \(I(a,b)\) сразу проваливается, потому что связывание \(a\) с термом, уже содержащим \(a\), нарушает occurs-check.
Реализации на C++, Python и Java сначала разбирают весь вход в деревья выражений, сохраняя исходный порядок и все дубликаты. Затем каждое дерево переводится в каноническую форму, чтобы структурно одинаковые выражения получили один и тот же уникальный индекс.
После этого программа вычисляет значение для каждой пары уникальных выражений. Каждая пара обрабатывается рекурсивной унификацией с occurs-check; если унификация успешна, разрешенное дерево рекурсивно вычисляется по модулю \(10^9\). Во время вычисления уже разрешенные поддеревья кэшируются внутри текущей обработки пары, чтобы не пересчитывать повторяющиеся ветви. Реализация на C++ дополнительно распараллеливает предварительный расчет таблицы уникальных пар, тогда как версии на Python и Java выполняют ту же логику обычными вложенными циклами.
На последнем этапе перебираются все исходные пары позиций \((p,q)\) при \(p<q\), отбрасываются случаи, где обе позиции указывают на одно и то же каноническое выражение, и для остальных в сумму добавляется кэшированное значение \(C_{a_p,a_q}\).
Пусть \(N\) обозначает общее число входных выражений, \(U\) число различных структурных выражений после устранения дубликатов, а \(L\) суммарный размер всех разобранных деревьев. Разбор и канонизация линейны по размеру входа, то есть занимают \(O(L)\) времени.
Доминирующая символьная стадия - это таблица уникальных пар. Ее стоимость равна
$$O\bigl(U^2\cdot T_{\text{pair}}\bigr),$$
где \(T_{\text{pair}}\) - цена одной унификации и, при успехе, одного рекурсивного вычисления. На обычных ациклических данных этот расход близок к линейному по числу посещенных вершин, хотя occurs-check в трудных случаях может повторно просматривать большие поддеревья. Финальное суммирование по позициям занимает \(O(N^2)\) времени. Память равна \(O(L+U^2)\) для хранимых деревьев и кеша пар. Параллелизм в реализации на C++ улучшает только реальное время выполнения, но не асимптотику.
لدينا قائمة من التعابير الرمزية المبنية من متغيرات وبانٍ ثنائي. لكل زوج غير مرتب من المواضع التي تحتوي على تعبيرين مختلفين، نريد معرفة هل توجد إحالة تجعل شجرتي التعبير متماثلتين تمامًا أم لا. إذا لم توجد مثل هذه الإحالة فمساهمة ذلك الزوج تساوي \(0\). وإذا وجدت، فنقيّم الشجرة المشتركة الناتجة عدديا، ثم نأخذ المجموع النهائي بترديد
$$M=10^9.$$
البحث الخام في جميع الإحالات الممكنة غير عملي تمامًا، لذلك يعتمد الحل على بنية الشجرة نفسها، وعلى التوحيد التعاودي، وعلى تخزين نتائج الأزواج المتكررة.
الفكرة الأساسية هي التعامل مع كل زوج على مرحلتين منفصلتين: أولًا حل المعادلة الرمزية بواسطة التوحيد، ثم تقييم الحد المشترك الناتج وفق قاعدة حسابية ثابتة.
من الناحية المجردة تخضع التعابير للقواعد
$$E ::= v \mid I(E,E),$$
حيث ترمز \(v\) إلى متغير. لذلك فكل تعبير هو إما ورقة تحمل اسم متغير، أو عقدة داخلية لها ابنان بالضبط. والمساواة البنيوية تعني تماثل شكل الشجرة وتماثل أسماء المتغيرات في المواضع المناظرة.
بهذه النظرة تصبح المسألة مسألة معادلات بين أشجار، لا مجرد مقارنة نصوص.
إذا كان لدينا تعبيران \(E_1\) و \(E_2\)، فنحن نبحث عن إحالة \(\sigma\) تحقق
$$\sigma(E_1)=\sigma(E_2).$$
الإحالة تربط المتغيرات بتعابير أخرى وتمتد تعاوديًا عبر الشجرة:
$$\sigma\bigl(I(A,B)\bigr)=I\bigl(\sigma(A),\sigma(B)\bigr).$$
القواعد هنا طبيعية. إذا كانت العقدتان الحاليتان كلتاهما من النوع الثنائي، فيجب أن يتوحد الفرعان الأيسران وأن يتوحد الفرعان الأيمنان أيضًا. وإذا كان أحد الطرفين متغيرًا، فيجوز ربط هذا المتغير بالطرف الآخر ما دام الربط قانونيًا. وإذا لم تنطبق أي قاعدة من هذه القواعد، يفشل التوحيد.
قبل كل مقارنة، يتم تتبع الروابط المعروفة سابقًا حتى الوصول إلى الحد المحسوم فعليًا. ولهذا فإن السلسلة \(a \mapsto b\) ثم \(b \mapsto I(c,d)\) تعادل تمامًا الربط المباشر \(a \mapsto I(c,d)\).
الحالة الخطرة هي الربط المرجعي الذاتي. إذا كان المتغير \(v\) سيوضع بدلًا من الحد \(T\)، فلا بد أن يتحقق الشرط
$$v\notin \operatorname{Vars}(T).$$
وهذا هو occurs-check الكلاسيكي. من دونه فإن معادلة مثل
$$v=I(v,w)$$
ستنتج جسمًا لا نهائيًا دائريًا بدل حد منتهٍ عادي. جميع التطبيقات هنا ترفض هذه الحالات صراحة، لذلك فإن كل توحيد ناجح يعطي دائمًا شجرة منتهية غير دورية.
بعد نجاح التوحيد نعطي الحد المشترك تفسيرًا عدديًا. المتغير غير المرتبط يساهم بالقيمة \(0\). أما القاعدة التعاودية للباني الثنائي فهي
$$J(x,y)=\bigl(1+x+y\bigr)^2+(y-x)\pmod{M}.$$
وإذا رمزنا إلى قيمة التعبير \(E\) تحت الإحالة الناجحة \(\sigma\) بالرمز \(V_\sigma(E)\)، فإن
$$V_\sigma(v)=0\quad\text{إذا بقي }v\text{ حرًا},$$
$$V_\sigma\bigl(I(A,B)\bigr)=J\bigl(V_\sigma(A),V_\sigma(B)\bigr).$$
ومن ثم تكون مساهمة الزوج
$$P(E_1,E_2)= \begin{cases} V_\sigma(E_1), & \text{إذا كان }E_1\text{ و }E_2\text{ قابلين للتوحيد},\\ 0, & \text{خلاف ذلك}. \end{cases}$$
وبما أن الطرفين يصبحان الشجرة نفسها بعد تطبيق \(\sigma\)، فإن تقييم أي منهما يعطي القيمة نفسها.
قد تحتوي المدخلات على كثير من التعابير المتكررة. إذا حوّلنا كل شجرة محللة إلى صيغة نصية معيارية واحدة، أمكن دمج التعابير المتساوية في ممثلين فريدين \(U_0,U_1,\dots,U_{U-1}\).
لهؤلاء الممثلين نعرّف جدول الأزواج المتماثل
$$C_{i,j}=P(U_i,U_j),\qquad C_{i,j}=C_{j,i}.$$
إذا كان عدد المواضع الأصلية \(N\)، وكان التعبير في الموضع \(p\) يقابل الفهرس \(a_p\)، فإن المجموع المطلوب هو
$$S=\sum_{\substack{1\le p\lt q\le N \\ a_p\ne a_q}} C_{a_p,a_q}\pmod{M}.$$
والشرط \(a_p\ne a_q\) مهم للغاية: فإذا ظهر التعبير البنيوي نفسه في موضعين مختلفين، فإن هذا الزوج من المواضع لا يدخل في الناتج المطلوب.
لنأخذ الزوج
$$E_1=I(a,b),\qquad E_2=I(c,I(c,d)).$$
الجذران لهما البنية الثنائية نفسها، لذا نوحد الأبناء. من الابنين الأيسرين نحصل على
$$a\mapsto c,$$
ومن الابنين الأيمنين نحصل على
$$b\mapsto I(c,d).$$
هذا الربط الثاني مسموح لأن \(b\) لا يظهر داخل \(I(c,d)\). لذلك ينجح التوحيد، وتكون الشجرة المشتركة المحلولة هي
$$I(c,I(c,d)).$$
نقيمها الآن عدديا. بما أن \(c\) و \(d\) بقيا غير مرتبطين، فإن كليهما يساوي \(0\). قيمة العقدة الداخلية هي
$$J(0,0)=(1+0+0)^2+(0-0)=1.$$
وعندئذ تكون قيمة العقدة الخارجية
$$J(0,1)=(1+0+1)^2+(1-0)=4+1=5.$$
إذن مساهمة هذا الزوج هي \(5\) بترديد \(10^9\). وعلى النقيض من ذلك، فإن الزوج \(a\) و \(I(a,b)\) يفشل فورًا، لأن ربط \(a\) بحد يحتوي أصلًا على \(a\) يخرق occurs-check.
تبدأ تطبيقات C++ و Python و Java بتحليل المدخلات كلها إلى أشجار تعبيرية مع الحفاظ على الترتيب الأصلي وجميع التكرارات. بعد ذلك تُحوَّل كل شجرة إلى صيغة معيارية، بحيث تحصل التعابير المتطابقة بنيويًا على الفهرس الفريد نفسه.
ثم تحسب التطبيقات قيمة كل زوج من التعابير الفريدة. كل زوج يمر بعملية توحيد تعاودي مع occurs-check، وإذا نجح التوحيد تُقيَّم الشجرة المحلولة تعاوديًا بترديد \(10^9\). وخلال هذه العملية تُخزَّن الأشجار الفرعية المحلولة داخل حساب الزوج الحالي حتى لا يعاد تقييم الفروع المتكررة. كما أن تطبيق C++ يوزع مرحلة الحساب المسبق لأزواج التعابير الفريدة على عدة مهام عمل، بينما تنفذ نسختا Python و Java المنطق نفسه بواسطة حلقات متداخلة مباشرة.
وفي النهاية تمر التطبيقات على جميع أزواج المواضع الأصلية \((p,q)\) حيث \(p<q\)، وتتجاوز الحالات التي يشير فيها الموضعان إلى التعبير المعياري نفسه، ثم تضيف القيمة المخزنة \(C_{a_p,a_q}\) لبقية الأزواج.
لنفرض أن \(N\) هو عدد التعابير الكلي في المدخل، و\(U\) هو عدد التعابير البنيوية المختلفة بعد إزالة التكرار، و\(L\) هو مجموع أحجام جميع الأشجار المحللة. التحليل النحوي والتقييس خطيان في حجم المدخل، وبالتالي زمنهما \(O(L)\).
أما المرحلة الرمزية المسيطرة فهي بناء جدول الأزواج الفريدة، وتكلفته
$$O\bigl(U^2\cdot T_{\text{pair}}\bigr),$$
حيث \(T_{\text{pair}}\) هو كلفة عملية توحيد واحدة، ومع النجاح، عملية تقييم تعاودي واحدة. في المدخلات العادية غير الدورية تكون هذه الكلفة قريبة من الخطية في عدد العقد التي تُزار، لكن occurs-check قد يعيد المرور على أشجار فرعية كبيرة في الحالات الأصعب. الجمع النهائي على مستوى المواضع يحتاج إلى \(O(N^2)\) زمنًا. أما الذاكرة فتبلغ \(O(L+U^2)\) من أجل الأشجار المخزنة وجدول الأزواج. والتوازي في تطبيق C++ يحسن الزمن الفعلي فقط ولا يغير الرتبة الأسية.