We are given \(n\) people together with two pairing rules: one for beds and one for desks. Each rule is an involution, so every person is either paired with exactly one other person or left fixed by that rule. The task is to count, modulo
$$P=999{,}999{,}937,$$
how many relabelings of the people preserve both structures simultaneously.
The solution treats the data as a finite colored graph built from two involutions, then counts its structure-preserving permutations by decomposing the graph into connected components and grouping isomorphic components together.
Let \(V=\{1,2,\dots,n\}\). Write the bed relation as \(\beta:V\to V\) and the desk relation as \(\delta:V\to V\). Because each relation is an involution, we have
$$\beta(\beta(i))=i,\qquad \delta(\delta(i))=i \qquad \text{for every } i\in V.$$
A relabeling is a permutation \(\pi\) of \(V\). It is valid exactly when it preserves both relations, which means
$$\pi(\beta(i))=\beta(\pi(i)),\qquad \pi(\delta(i))=\delta(\pi(i)) \qquad \text{for every } i\in V.$$
So the problem is to count all permutations that commute with both involutions.
Connect each vertex \(i\) to \(\beta(i)\) by a bed edge and to \(\delta(i)\) by a desk edge. Fixed points are allowed, so a vertex can carry a loop of one color. Every vertex therefore has exactly one incident bed edge and exactly one incident desk edge, counting loops.
Now split this colored graph into connected components. If a permutation preserves both colored edge relations, it must send each connected component to another connected component with exactly the same colored structure. Therefore the global counting problem breaks into independent pieces indexed by component isomorphism classes.
Take one component \(C\) of size \(m\) and relabel its vertices locally as \(0,1,\dots,m-1\). Record two local partner tables: one table gives the bed partner of each local index, and the other gives the desk partner. This removes the original labels and keeps only the structure.
If \(f:C\to C'\) is a color-preserving bijection between two components, then it must satisfy
$$f(p_C(x))=p_{C'}(f(x)),\qquad f(q_C(x))=q_{C'}(f(x))$$
for every local vertex \(x\), where \(p_C\) and \(q_C\) denote the local bed and desk partner tables. Because the component is connected and each vertex has exactly one neighbor of each color, once the image of one starting vertex is chosen, these equations force the image of every reachable vertex. Either the propagation stays consistent and yields one isomorphism, or it produces a contradiction and fails.
A necessary first check is that the chosen starting vertices have the same loop pattern:
$$p_C(r)=r \iff p_{C'}(s)=s,\qquad q_C(r)=r \iff q_{C'}(s)=s.$$
Trying all possible starting images \(s\) therefore counts all isomorphisms from \(C\) to \(C'\).
For a component \(C\), let
$$a(C)=\left|\operatorname{Aut}(C)\right|,$$
the number of color-preserving automorphisms of \(C\). This is exactly the number obtained when the implementation compares a component with itself.
If \(C\) and \(C'\) are isomorphic, then the number of isomorphisms \(C\to C'\) is also \(a(C)\). The reason is simple: choose one fixed isomorphism \(\varphi:C\to C'\). Then every other isomorphism \(C\to C'\) is uniquely of the form \(\varphi\circ \sigma\) with \(\sigma\in \operatorname{Aut}(C)\).
Suppose an isomorphism class appears \(m_j\) times, and let \(a_j\) be the automorphism count of one representative component in that class. A valid global permutation can first permute those \(m_j\) copies among themselves in
$$m_j!$$
ways. After the target copy of each source component is chosen, there are
$$a_j$$
color-preserving bijections for that source-to-target move. Since this choice is made independently for all \(m_j\) copies, the class contributes
$$a_j^{m_j}\cdot m_j!.$$
If the graph has isomorphism classes \(\mathcal{C}_1,\dots,\mathcal{C}_t\), the final formula is
$$\boxed{N=\prod_{j=1}^{t} a_j^{m_j}\cdot m_j! \pmod{P}.}$$
Consider \(n=4\), with bed pairing \(2\leftrightarrow 3\) and desk pairings \(1\leftrightarrow 3\), \(2\leftrightarrow 4\). The bed relation fixes \(1\) and \(4\), so those two vertices carry bed loops. The whole structure is one connected component, and its colored shape is an alternating path
$$1 \overset{\delta}{\leftrightarrow} 3 \overset{\beta}{\leftrightarrow} 2 \overset{\delta}{\leftrightarrow} 4$$
with bed loops at the two ends. There are exactly two automorphisms: the identity, and the reversal that swaps the two ends and the two middle vertices while preserving edge colors. Hence the answer is
$$2,$$
which matches the implementation checkpoint for this small case.
The C++, Python, and Java implementations begin by storing both involutions as tables on \(1,\dots,n\), with fixed points filled in automatically for any person not listed in a pair. They then traverse the graph with an explicit stack, following both colored relations, to extract every connected component.
Each component is relabeled locally so that it can be compared without referring to the original global labels. To compare two components, the implementation tries every possible image of the first local vertex whose loop pattern matches. For each candidate, it propagates the bed and desk constraints through the entire component. A contradiction rejects that candidate; a complete consistent propagation counts as one isomorphism.
After grouping components into isomorphism classes, the implementation computes the modular product
$$a_j^{m_j}\cdot m_j! \pmod{P}$$
for every class, using fast modular exponentiation for the power term and ordinary modular multiplication for the factorial term. No search over all \(n!\) permutations is ever attempted.
Building the two involution tables and extracting all connected components costs \(O(n)\) time and \(O(n)\) memory. If two components have size \(s\), then testing isomorphism between them tries up to \(s\) starting images, and each successful or failed propagation touches at most \(s\) local vertices, so one comparison is \(O(s^2)\) in the worst case.
If the component sizes are \(s_1,\dots,s_r\), the grouping stage is therefore bounded by the pairwise same-size comparisons performed by the simple implementation; for the actual \(n=500\) instance this is easily fast enough. The overall memory use remains linear in \(n\).
Gegeben sind \(n\) Personen sowie zwei Zuordnungen: eine Bettzuordnung und eine Tischzuordnung. Beide Zuordnungen sind Involutionen, also wird jede Person entweder genau einer anderen Person zugeordnet oder bleibt unter der jeweiligen Zuordnung fest. Gesucht ist die Anzahl aller Umbenennungen der Personen, die beide Strukturen gleichzeitig erhalten, modulo
$$P=999{,}999{,}937.$$
Die Lösung interpretiert die Daten als endlichen, zweifarbig markierten Graphen mit zwei Involutionen. Danach zerlegt sie den Graphen in Zusammenhangskomponenten und zählt die struktur-erhaltenden Permutationen über die Isomorphieklassen dieser Komponenten.
Sei \(V=\{1,2,\dots,n\}\). Schreibe die Bettzuordnung als \(\beta:V\to V\) und die Tischzuordnung als \(\delta:V\to V\). Dann gilt
$$\beta(\beta(i))=i,\qquad \delta(\delta(i))=i \qquad \text{für alle } i\in V.$$
Eine Umbenennung ist eine Permutation \(\pi\) von \(V\). Sie ist genau dann gültig, wenn sie beide Zuordnungen erhält, also
$$\pi(\beta(i))=\beta(\pi(i)),\qquad \pi(\delta(i))=\delta(\pi(i)) \qquad \text{für alle } i\in V.$$
Damit zählen wir genau die Permutationen, die mit beiden Involutionen kommutieren.
Verbinde jeden Knoten \(i\) mit \(\beta(i)\) durch eine Bettkante und mit \(\delta(i)\) durch eine Tischkante. Fixpunkte sind erlaubt; sie erscheinen als Schleifen der entsprechenden Farbe. Jeder Knoten besitzt also genau eine Bettkante und genau eine Tischkante, wenn Schleifen mitgezählt werden.
Nun zerfällt der gefärbte Graph in Zusammenhangskomponenten. Jede gültige Permutation muss jede Komponente auf eine andere Komponente mit identischer Farbstuktur abbilden. Deshalb reduziert sich das globale Zählen auf unabhängige Beiträge der Isomorphieklassen von Komponenten.
Nimm eine Komponente \(C\) der Größe \(m\) und nummeriere ihre Knoten lokal als \(0,1,\dots,m-1\). Speichere dann zwei lokale Partnertabellen: eine für den Bettpartner und eine für den Tischpartner jedes lokalen Knotens. So verschwinden die ursprünglichen globalen Beschriftungen, während die Struktur erhalten bleibt.
Ist \(f:C\to C'\) eine farberhaltende Bijektion zwischen zwei Komponenten, dann muss
$$f(p_C(x))=p_{C'}(f(x)),\qquad f(q_C(x))=q_{C'}(f(x))$$
für jeden lokalen Knoten \(x\) gelten. Weil die Komponente zusammenhängend ist und jeder Knoten genau einen Nachbarn jeder Farbe besitzt, bestimmt die Wahl des Bildes eines einzigen Startknotens den Rest der Abbildung eindeutig. Entweder bleibt diese Fortpflanzung konsistent und liefert einen Isomorphismus, oder sie erzeugt einen Widerspruch und scheitert.
Schon vor dem Start muss das Schleifenmuster passen:
$$p_C(r)=r \iff p_{C'}(s)=s,\qquad q_C(r)=r \iff q_{C'}(s)=s.$$
Wenn man alle möglichen Startbilder \(s\) ausprobiert, erhält man genau die Anzahl aller Isomorphismen von \(C\) nach \(C'\).
Für eine Komponente \(C\) sei
$$a(C)=\left|\operatorname{Aut}(C)\right|$$
die Anzahl ihrer farberhaltenden Automorphismen. Genau diese Zahl berechnet die Implementierung, wenn sie eine Komponente mit sich selbst vergleicht.
Sind \(C\) und \(C'\) isomorph, dann gibt es ebenso viele Isomorphismen \(C\to C'\), nämlich wieder \(a(C)\). Fixiert man einen Isomorphismus \(\varphi:C\to C'\), dann ist jeder weitere Isomorphismus eindeutig von der Form \(\varphi\circ \sigma\) mit \(\sigma\in \operatorname{Aut}(C)\).
Angenommen, eine Isomorphieklasse tritt \(m_j\)-mal auf und \(a_j\) sei die Automorphismenzahl eines Repräsentanten. Dann kann eine gültige globale Permutation diese \(m_j\) Kopien zunächst in
$$m_j!$$
verschiedenen Weisen untereinander vertauschen. Ist das Ziel jeder Quelle festgelegt, so gibt es für jede einzelne Abbildung noch
$$a_j$$
farberhaltende Bijektionen. Insgesamt liefert diese Klasse also den Faktor
$$a_j^{m_j}\cdot m_j!.$$
Für die Isomorphieklassen \(\mathcal{C}_1,\dots,\mathcal{C}_t\) ergibt sich damit
$$\boxed{N=\prod_{j=1}^{t} a_j^{m_j}\cdot m_j! \pmod{P}.}$$
Betrachte \(n=4\) mit Bettzuordnung \(2\leftrightarrow 3\) und Tischzuordnungen \(1\leftrightarrow 3\), \(2\leftrightarrow 4\). Unter der Bettzuordnung sind \(1\) und \(4\) Fixpunkte und tragen daher Bettschleifen. Die gesamte Struktur bildet genau eine Zusammenhangskomponente, deren gefärbte Form ein alternierender Pfad ist:
$$1 \overset{\delta}{\leftrightarrow} 3 \overset{\beta}{\leftrightarrow} 2 \overset{\delta}{\leftrightarrow} 4.$$
Dazu kommen Bettschleifen an den beiden Enden. Diese Komponente hat genau zwei Automorphismen: die Identität und die Umkehrung des Pfades. Deshalb ist die gesuchte Anzahl
$$2,$$
genau wie im kleinen Kontrollfall der Implementierung.
Die C++-, Python- und Java-Implementierungen speichern zunächst beide Involutionen als Tabellen auf \(1,\dots,n\); nicht genannte Personen bleiben dabei automatisch Fixpunkte. Anschließend laufen sie mit einem expliziten Stack durch den Graphen, folgen beiden farbigen Relationen und extrahieren so alle Zusammenhangskomponenten.
Jede Komponente wird lokal neu indiziert, damit Vergleiche ohne Bezug auf die ursprünglichen globalen Labels möglich sind. Zum Vergleich zweier Komponenten probiert die Implementierung alle möglichen Bilder des ersten lokalen Knotens mit passendem Schleifenmuster aus. Von dort werden die Bett- und Tischbedingungen durch die ganze Komponente propagiert. Ein Widerspruch verwirft den Kandidaten, eine vollständige konsistente Propagation zählt als ein Isomorphismus.
Nachdem alle Komponenten zu Isomorphieklassen gruppiert sind, berechnet die Implementierung für jede Klasse den modularen Beitrag
$$a_j^{m_j}\cdot m_j! \pmod{P}$$
mittels schneller modularer Exponentiation für die Potenz und gewöhnlicher modularer Multiplikation für die Fakultät. Eine Suche über alle \(n!\) Permutationen findet an keiner Stelle statt.
Das Aufbauen der beiden Involutionstabellen und das Zerlegen in Zusammenhangskomponenten kostet \(O(n)\) Zeit und \(O(n)\) Speicher. Haben zwei Komponenten Größe \(s\), dann testet ein Isomorphievergleich bis zu \(s\) Startbilder, und jede einzelne Fortpflanzung berührt höchstens \(s\) lokale Knoten. Daher kostet ein Vergleich im Worst Case \(O(s^2)\).
Für Komponentengrößen \(s_1,\dots,s_r\) wird die Laufzeit der Klassierung also durch die tatsächlich ausgeführten Paarvergleiche gleich großer Komponenten bestimmt; für den realen Fall \(n=500\) ist das problemlos beherrschbar. Der gesamte Speicherverbrauch bleibt linear in \(n\).
\(n\) kişi için iki eşleme verilir: biri yatak ilişkisi, diğeri masa ilişkisi. Her iki ilişki de involüsyondur; yani bir kişi ya tam olarak bir başka kişiyle eşleşir ya da o ilişki altında sabit kalır. Amaç, bu iki yapıyı aynı anda koruyan yeniden etiketlemelerin sayısını
$$P=999{,}999{,}937$$
modunda bulmaktır.
Çözüm, veriyi iki involüsyonun oluşturduğu sonlu bir iki-renkli grafik olarak yorumlar. Daha sonra bu grafiği bağlı bileşenlerine ayırır ve yapı-koruyan permütasyonları, izomorf bileşen sınıflarının katkılarını çarparak sayar.
\(V=\{1,2,\dots,n\}\) olsun. Yatak ilişkisini \(\beta:V\to V\), masa ilişkisini \(\delta:V\to V\) ile gösterelim. İnvolüsyon oldukları için
$$\beta(\beta(i))=i,\qquad \delta(\delta(i))=i \qquad \text{her } i\in V \text{ için}$$
eşitlikleri geçerlidir. Bir yeniden etiketleme, \(V\) üzerinde bir \(\pi\) permütasyonudur. Bunun geçerli olması için her iki ilişkiyi de koruması gerekir:
$$\pi(\beta(i))=\beta(\pi(i)),\qquad \pi(\delta(i))=\delta(\pi(i)) \qquad \text{her } i\in V \text{ için}.$$
Yani problem, iki involüsyonla değişmeli olan tüm permütasyonları saymaya indirgenir.
Her \(i\) düğümünü \(\beta(i)\) ile bir yatak kenarıyla, \(\delta(i)\) ile de bir masa kenarıyla bağlayalım. Sabit noktalar mümkündür; bunlar ilgili renkte döngü olarak görünür. Böylece her düğümün, döngüler dahil, tam bir yatak kenarı ve tam bir masa kenarı vardır.
Bu renklendirilmiş grafik bağlı bileşenlere ayrılır. Her geçerli permütasyon, bir bağlı bileşeni ancak aynı renk yapısına sahip başka bir bağlı bileşene gönderebilir. Bu yüzden toplam sayım, bileşen izomorfi sınıflarının bağımsız katkılarına ayrılır.
Boyutu \(m\) olan bir \(C\) bileşeni alalım ve düğümlerini yerel olarak \(0,1,\dots,m-1\) diye numaralayalım. Sonra iki yerel partner tablosu tutalım: biri her düğümün yatak partnerini, diğeri masa partnerini versin. Böylece küresel etiketler atılır, yalnızca yapı kalır.
\(f:C\to C'\) renk-koruyan bir bijeksiyon ise şu koşulları sağlamalıdır:
$$f(p_C(x))=p_{C'}(f(x)),\qquad f(q_C(x))=q_{C'}(f(x)).$$
Bileşen bağlı olduğundan ve her düğümün her renkte tam bir komşusu bulunduğundan, bir başlangıç düğümünün görüntüsü seçildiğinde bu eşitlikler geri kalan bütün görüntüleri zorunlu kılar. Yayılım ya tutarlı biçimde tamamlanır ve bir izomorfizm verir, ya da çelişki üretip başarısız olur.
Başlangıçta döngü deseni de aynı olmalıdır:
$$p_C(r)=r \iff p_{C'}(s)=s,\qquad q_C(r)=r \iff q_{C'}(s)=s.$$
Dolayısıyla tüm olası başlangıç görüntüleri \(s\) denenerek \(C\) ile \(C'\) arasındaki bütün izomorfizmler sayılır.
Bir \(C\) bileşeni için
$$a(C)=\left|\operatorname{Aut}(C)\right|$$
olsun; bu, \(C\)'nin renk-koruyan otomorfizm sayısıdır. Uygulama, bir bileşeni kendisiyle karşılaştırdığında tam olarak bu değeri hesaplar.
Eğer \(C\) ile \(C'\) izomorf ise, \(C\to C'\) izomorfizmlerinin sayısı da yine \(a(C)\)'dir. Gerçekten, sabit bir \(\varphi:C\to C'\) izomorfizmi seçilirse, diğer bütün izomorfizmler benzersiz biçimde \(\varphi\circ \sigma\) şeklindedir; burada \(\sigma\in \operatorname{Aut}(C)\).
Bir izomorfi sınıfı \(m_j\) kez görünsün ve bu sınıfın bir temsilcisinin otomorfizm sayısı \(a_j\) olsun. Geçerli bir küresel permütasyon önce bu \(m_j\) kopyayı
$$m_j!$$
farklı biçimde kendi arasında permüte edebilir. Her kaynak kopya için hedef kopya seçildikten sonra, o geçişi gerçekleştiren
$$a_j$$
farklı renk-koruyan bijeksiyon vardır. Bu nedenle sınıfın toplam katkısı
$$a_j^{m_j}\cdot m_j!$$
olur. İzomorfi sınıfları \(\mathcal{C}_1,\dots,\mathcal{C}_t\) için nihai formül
$$\boxed{N=\prod_{j=1}^{t} a_j^{m_j}\cdot m_j! \pmod{P}.}$$
\(n=4\) için yatak eşleşmesi \(2\leftrightarrow 3\), masa eşleşmeleri ise \(1\leftrightarrow 3\) ve \(2\leftrightarrow 4\) olsun. Yatak ilişkisi altında \(1\) ve \(4\) sabit kaldığı için bu iki düğümde yatak döngüsü vardır. Tüm yapı tek bir bağlı bileşendir ve renkli şekli şu alternanslı yol olarak görülebilir:
$$1 \overset{\delta}{\leftrightarrow} 3 \overset{\beta}{\leftrightarrow} 2 \overset{\delta}{\leftrightarrow} 4.$$
Uçlardaki iki yatak döngüsü de korunur. Bu bileşenin tam iki otomorfizmi vardır: özdeşlik ve yolu ters çeviren simetri. Dolayısıyla cevap
$$2$$
olur; bu da uygulamanın küçük doğrulama örneğiyle aynıdır.
C++, Python ve Java uygulamaları önce her iki involüsyonu da \(1,\dots,n\) üzerinde tablo olarak kurar; listelenmeyen kişiler otomatik olarak sabit nokta kabul edilir. Ardından açık bir yığın kullanarak grafiği dolaşır, iki renkli ilişkiyi takip eder ve tüm bağlı bileşenleri çıkarır.
Her bileşen yerel olarak yeniden numaralanır; böylece karşılaştırmalar özgün küresel etiketlerden bağımsız hale gelir. İki bileşeni karşılaştırırken uygulama, önce döngü deseni uyan aday başlangıç görüntülerini dener. Sonra yatak ve masa kısıtlarını bütün bileşene yayar. Bir çelişki adayın reddedilmesine yol açar; tam ve tutarlı bir yayılım ise bir izomorfizm olarak sayılır.
Bileşenler izomorf sınıflara ayrıldıktan sonra uygulama her sınıf için
$$a_j^{m_j}\cdot m_j! \pmod{P}$$
katkısını hesaplar. Kuvvet terimi hızlı modüler üs alma ile, faktöriyel terimi ise sıradan modüler çarpma ile bulunur. Hiçbir aşamada \(n!\) olası permütasyon tek tek denenmez.
İki involüsyon tablosunu kurmak ve bağlı bileşenleri çıkarmak \(O(n)\) zaman ve \(O(n)\) bellek ister. Boyutu \(s\) olan iki bileşen karşılaştırılırken en fazla \(s\) farklı başlangıç görüntüsü denenir; her yayılım da en fazla \(s\) yerel düğüme dokunur. Bu yüzden tek bir karşılaştırmanın en kötü durum maliyeti \(O(s^2)\)'dir.
Bileşen boyutları \(s_1,\dots,s_r\) ise, sınıflandırma aşamasının toplam maliyeti uygulamanın gerçekten yaptığı aynı boyutlu çift karşılaştırmalarıyla sınırlanır; gerçek \(n=500\) girdisi için bu rahatlıkla yeterlidir. Toplam bellek kullanımı doğrusal kalır.
Se nos dan \(n\) personas y dos reglas de emparejamiento: una para camas y otra para escritorios. Cada regla es una involución, así que cada persona queda emparejada con exactamente otra persona o permanece fija bajo esa regla. Hay que contar, módulo
$$P=999{,}999{,}937,$$
cuántas relabelaciones de las personas preservan simultáneamente ambas estructuras.
La solución interpreta los datos como un grafo finito con dos colores de arista construido a partir de dos involuciones. Después descompone ese grafo en componentes conexas y cuenta las permutaciones que preservan la estructura agrupando las componentes isomorfas.
Sea \(V=\{1,2,\dots,n\}\). Denotemos la relación de camas por \(\beta:V\to V\) y la relación de escritorios por \(\delta:V\to V\). Como ambas son involuciones, se cumple
$$\beta(\beta(i))=i,\qquad \delta(\delta(i))=i \qquad \text{para todo } i\in V.$$
Una relabelación es una permutación \(\pi\) de \(V\). Es válida exactamente cuando conserva ambas relaciones, es decir, cuando
$$\pi(\beta(i))=\beta(\pi(i)),\qquad \pi(\delta(i))=\delta(\pi(i)) \qquad \text{para todo } i\in V.$$
Así, el problema consiste en contar todas las permutaciones que conmutan con las dos involuciones.
Unimos cada vértice \(i\) con \(\beta(i)\) mediante una arista de cama y con \(\delta(i)\) mediante una arista de escritorio. Los puntos fijos están permitidos, de modo que un vértice puede tener un lazo de uno de los colores. Por tanto, cada vértice tiene exactamente una arista de cama y exactamente una arista de escritorio, contando lazos.
Este grafo coloreado se descompone en componentes conexas. Toda permutación válida debe enviar cada componente a otra componente con exactamente la misma estructura de colores. Por ello, el conteo global se descompone en contribuciones independientes de las clases de isomorfía de componentes.
Tomemos una componente \(C\) de tamaño \(m\) y reenumeremos sus vértices localmente como \(0,1,\dots,m-1\). Guardamos entonces dos tablas locales: una da el compañero de cama de cada índice local y la otra da el compañero de escritorio. De este modo desaparecen las etiquetas globales originales y solo queda la estructura.
Si \(f:C\to C'\) es una biyección que preserva los colores, entonces debe satisfacer
$$f(p_C(x))=p_{C'}(f(x)),\qquad f(q_C(x))=q_{C'}(f(x))$$
para todo vértice local \(x\). Como la componente es conexa y cada vértice tiene exactamente un vecino de cada color, una vez fijada la imagen de un vértice inicial, estas ecuaciones fuerzan la imagen de todos los demás. O bien la propagación es consistente y produce un isomorfismo, o bien aparece una contradicción y el intento falla.
Antes de propagar, el patrón de lazos debe coincidir:
$$p_C(r)=r \iff p_{C'}(s)=s,\qquad q_C(r)=r \iff q_{C'}(s)=s.$$
Probar todas las posibles imágenes iniciales \(s\) cuenta exactamente todos los isomorfismos de \(C\) en \(C'\).
Para una componente \(C\), definimos
$$a(C)=\left|\operatorname{Aut}(C)\right|,$$
el número de automorfismos que preservan los colores. Ese es precisamente el valor que obtiene la implementación al comparar una componente consigo misma.
Si \(C\) y \(C'\) son isomorfas, entonces el número de isomorfismos \(C\to C'\) también es \(a(C)\). En efecto, si fijamos un isomorfismo \(\varphi:C\to C'\), cualquier otro isomorfismo es de forma única \(\varphi\circ \sigma\) con \(\sigma\in \operatorname{Aut}(C)\).
Supongamos que una clase de isomorfía aparece \(m_j\) veces y que \(a_j\) es el número de automorfismos de un representante. Una permutación global válida puede permutar esas \(m_j\) copias entre sí de
$$m_j!$$
maneras. Una vez elegido el destino de cada copia origen, existen
$$a_j$$
biyeciones que preservan los colores para cada movimiento. Por tanto, la contribución de esa clase es
$$a_j^{m_j}\cdot m_j!.$$
Si las clases de isomorfía son \(\mathcal{C}_1,\dots,\mathcal{C}_t\), obtenemos
$$\boxed{N=\prod_{j=1}^{t} a_j^{m_j}\cdot m_j! \pmod{P}.}$$
Consideremos \(n=4\), con emparejamiento de camas \(2\leftrightarrow 3\) y emparejamientos de escritorios \(1\leftrightarrow 3\), \(2\leftrightarrow 4\). La relación de camas fija a \(1\) y \(4\), así que esos dos vértices tienen lazos de cama. Toda la estructura forma una única componente conexa, cuya forma coloreada es el camino alternante
$$1 \overset{\delta}{\leftrightarrow} 3 \overset{\beta}{\leftrightarrow} 2 \overset{\delta}{\leftrightarrow} 4$$
con lazos de cama en los extremos. Esta componente tiene exactamente dos automorfismos: la identidad y la simetría que invierte el camino. Por eso la respuesta es
$$2,$$
en acuerdo con el caso pequeño comprobado por la implementación.
Las implementaciones en C++, Python y Java comienzan guardando ambas involuciones como tablas sobre \(1,\dots,n\); cualquier persona no mencionada en una pareja queda automáticamente como punto fijo. Después recorren el grafo con una pila explícita, siguiendo ambas relaciones coloreadas, para extraer todas las componentes conexas.
Cada componente se reindexa localmente para poder compararla sin depender de las etiquetas globales originales. Para comparar dos componentes, la implementación prueba todas las posibles imágenes del primer vértice local cuyo patrón de lazos coincida. A partir de ahí propaga las restricciones de cama y escritorio por toda la componente. Si aparece una contradicción, el intento se descarta; si la propagación completa es coherente, cuenta como un isomorfismo.
Una vez agrupadas las componentes por clase de isomorfía, la implementación calcula para cada clase el producto modular
$$a_j^{m_j}\cdot m_j! \pmod{P}$$
usando exponenciación modular rápida para la potencia y multiplicación modular ordinaria para el factorial. En ningún momento se enumeran las \(n!\) permutaciones posibles.
Construir las dos tablas de involución y extraer las componentes conexas cuesta \(O(n)\) tiempo y \(O(n)\) memoria. Si dos componentes tienen tamaño \(s\), comparar si son isomorfas prueba hasta \(s\) imágenes iniciales, y cada propagación toca a lo sumo \(s\) vértices locales. Por tanto, una comparación cuesta \(O(s^2)\) en el peor caso.
Si los tamaños de las componentes son \(s_1,\dots,s_r\), la etapa de agrupación queda acotada por las comparaciones por pares entre componentes del mismo tamaño que realiza la implementación sencilla; para el caso real \(n=500\), esto resulta perfectamente manejable. El consumo total de memoria permanece lineal en \(n\).
题目给出 \(n\) 个人，以及两种配对规则：床位配对和课桌配对。每一种规则都是一个 involution，也就是说，每个人要么与恰好另一人配对，要么在该规则下保持不变。要求计算所有同时保持这两种结构的重新标号方案数，结果对
$$P=999{,}999{,}937$$
取模。
核心思想是把整个数据看成由两个 involution 生成的有限双色图。然后把图拆成连通分量，再按“分量的同构类型”分别计数。这样就不需要去考虑所有 \(n!\) 个重标号，而是只处理每一种局部结构的对称性。
设顶点集合为 \(V=\{1,2,\dots,n\}\)。用 \(\beta:V\to V\) 表示床位关系，用 \(\delta:V\to V\) 表示课桌关系。因为它们都是 involution，所以对每个 \(i\in V\) 都有
$$\beta(\beta(i))=i,\qquad \delta(\delta(i))=i.$$
任意一次重新标号就是 \(V\) 上的一个置换 \(\pi\)。它合法，当且仅当它同时保持两种关系，即
$$\pi(\beta(i))=\beta(\pi(i)),\qquad \pi(\delta(i))=\delta(\pi(i)) \qquad \text{对所有 } i\in V.$$
换句话说，我们要数的是与这两个 involution 同时可交换的所有置换。
对于每个顶点 \(i\)，连一条“床位边”到 \(\beta(i)\)，再连一条“课桌边”到 \(\delta(i)\)。固定点是允许的，因此某个顶点可以带有某一种颜色的自环。把自环也算进去以后，每个顶点恰好有一条床位边和一条课桌边。
这样得到的是一张带两种颜色的图。任何保持两种关系的置换，都必须把一个连通分量送到另一块具有完全相同颜色结构的连通分量。所以全局计数自然分解成若干个“同构分量类”的独立贡献。
取一个大小为 \(m\) 的连通分量 \(C\)，把它的顶点局部重编号为 \(0,1,\dots,m-1\)。接着记录两张局部配对表：一张给出每个局部编号的床位伙伴，另一张给出课桌伙伴。这样做的目的是去掉原始全局编号，只保留结构本身。
若 \(f:C\to C'\) 是一个保持颜色的双射，那么对每个局部顶点 \(x\) 都必须满足
$$f(p_C(x))=p_{C'}(f(x)),\qquad f(q_C(x))=q_{C'}(f(x)).$$
由于分量是连通的，而且每个顶点在每种颜色下都只有唯一的相邻目标，一旦选定了起始顶点的像，这两个方程就会把所有其他顶点的像都唯一地推出来。推导过程要么始终一致，从而得到一个真正的同构；要么在某处出现冲突，于是该起点选择失败。
在尝试之前，还要先检查起点的自环模式是否一致：
$$p_C(r)=r \iff p_{C'}(s)=s,\qquad q_C(r)=r \iff q_{C'}(s)=s.$$
把所有可能的起点像 \(s\) 都试一遍，就得到了从 \(C\) 到 \(C'\) 的全部同构个数。
对一个分量 \(C\)，记
$$a(C)=\left|\operatorname{Aut}(C)\right|,$$
即保持颜色的自同构数量。这正是实现中把某个分量与它自身比较时得到的值。
如果 \(C\) 与 \(C'\) 同构，那么从 \(C\) 到 \(C'\) 的同构总数其实也是 \(a(C)\)。理由很直接：固定一个具体同构 \(\varphi:C\to C'\) 后，任何其他同构都唯一地写成 \(\varphi\circ \sigma\)，其中 \(\sigma\in \operatorname{Aut}(C)\)。因此两者的数量完全一致。
假设某一种同构类型出现了 \(m_j\) 次，取它的一个代表分量，其自同构数为 \(a_j\)。一个合法的全局置换首先可以把这 \(m_j\) 个拷贝彼此重排，其方式数是
$$m_j!.$$
当每个源分量的目标拷贝确定以后，对每一次源到目标的移动，都有
$$a_j$$
个保持颜色的双射可选，所以这个同构类的总贡献就是
$$a_j^{m_j}\cdot m_j!.$$
若所有同构类为 \(\mathcal{C}_1,\dots,\mathcal{C}_t\)，最终公式为
$$\boxed{N=\prod_{j=1}^{t} a_j^{m_j}\cdot m_j! \pmod{P}.}$$
考虑 \(n=4\) 的小例子：床位配对为 \(2\leftrightarrow 3\)，课桌配对为 \(1\leftrightarrow 3\) 与 \(2\leftrightarrow 4\)。在床位关系下，\(1\) 和 \(4\) 是固定点，因此这两个顶点带有床位自环。整个结构只有一个连通分量，它的彩色形状可以写成
$$1 \overset{\delta}{\leftrightarrow} 3 \overset{\beta}{\leftrightarrow} 2 \overset{\delta}{\leftrightarrow} 4$$
并且两端各有一个床位自环。这个分量恰好有两个自同构：恒等映射，以及把整条路径反向的对称。于是答案就是
$$2,$$
这与实现中的小规模校验值完全一致。
C++、Python 和 Java 实现都会先把两种 involution 存成 \(1,\dots,n\) 上的表；任何没有显式出现在配对中的人都会自动视为固定点。随后程序使用显式栈遍历图，同时沿着两种颜色的关系扩展，从而提取出全部连通分量。
每个分量都会被重新编号成局部编号，这样后续比较时就不再依赖原始全局标签。比较两个分量时，实现会尝试第一个局部顶点的所有可能像，但只保留自环模式匹配的候选点。对于每个候选点，再把床位约束和课桌约束传播到整个分量。如果过程中出现矛盾，则该候选失败；若能一致地完成传播，就得到一个同构。
把所有分量按同构类型分组后，实现对每一组计算
$$a_j^{m_j}\cdot m_j! \pmod{P}$$
这一贡献。幂次部分通过快速模幂完成，阶乘部分通过普通模乘完成。整个过程中从不枚举 \(n!\) 个可能的全排列。
建立两张 involution 表并提取所有连通分量只需要 \(O(n)\) 时间和 \(O(n)\) 额外空间。若两个分量的大小同为 \(s\)，那么一次同构比较最多尝试 \(s\) 个起点像，而每次传播最多访问 \(s\) 个局部顶点，因此一次比较的最坏时间复杂度为 \(O(s^2)\)。
若各分量大小为 \(s_1,\dots,s_r\)，那么分组阶段的总成本由实现实际执行的同尺寸分量两两比较所决定；对真实的 \(n=500\) 数据来说，这个开销完全可控。总体内存使用始终保持在线性规模。
Даны \(n\) человек и два правила попарного связывания: по кроватям и по партам. Каждое правило является инволюцией: человек либо соединён ровно с одним другим человеком, либо остаётся неподвижной точкой этого правила. Нужно подсчитать количество всех перенумераций, которые одновременно сохраняют обе структуры, по модулю
$$P=999{,}999{,}937.$$
Решение рассматривает исходные данные как конечный граф с двумя цветами рёбер, порождённый двумя инволюциями. Затем граф раскладывается на компоненты связности, а число допустимых перестановок выражается через изоморфные классы этих компонент.
Пусть \(V=\{1,2,\dots,n\}\). Обозначим отношение кроватей через \(\beta:V\to V\), а отношение парт через \(\delta:V\to V\). Тогда
$$\beta(\beta(i))=i,\qquad \delta(\delta(i))=i \qquad \text{для всех } i\in V.$$
Любая перенумерация есть перестановка \(\pi\) множества \(V\). Она допустима тогда и только тогда, когда сохраняет оба отношения:
$$\pi(\beta(i))=\beta(\pi(i)),\qquad \pi(\delta(i))=\delta(\pi(i)) \qquad \text{для всех } i\in V.$$
Иначе говоря, требуется посчитать все перестановки, которые коммутируют сразу с двумя инволюциями.
Соединим вершину \(i\) с \(\beta(i)\) ребром цвета кроватей и с \(\delta(i)\) ребром цвета парт. Неподвижные точки разрешены, поэтому у вершины может быть петля одного из цветов. С учётом петель каждая вершина имеет ровно одно ребро каждого цвета.
Полученный окрашенный граф распадается на компоненты связности. Любая допустимая перестановка обязана переводить компоненту связности только в такую компоненту, у которой полностью совпадает цветная структура. Поэтому глобальный подсчёт распадается на независимые вклады классов изоморфных компонент.
Возьмём компоненту \(C\) размера \(m\) и перенумеруем её вершины локально числами \(0,1,\dots,m-1\). После этого сохраним две локальные таблицы: одна даёт для каждого локального индекса его соседа по отношению кроватей, другая - соседа по отношению парт. Тем самым исходные глобальные метки исчезают, остаётся только структура.
Если \(f:C\to C'\) - биекция, сохраняющая цвета, то для каждой локальной вершины \(x\) необходимо выполнять
$$f(p_C(x))=p_{C'}(f(x)),\qquad f(q_C(x))=q_{C'}(f(x)).$$
Так как компонента связна и у каждой вершины есть ровно по одному соседу каждого цвета, после выбора образа одной стартовой вершины эти равенства однозначно навязывают образы всех остальных вершин. Либо распространение ограничений остаётся согласованным и даёт изоморфизм, либо в какой-то момент возникает противоречие.
До распространения нужно проверить совпадение рисунка петель:
$$p_C(r)=r \iff p_{C'}(s)=s,\qquad q_C(r)=r \iff q_{C'}(s)=s.$$
Перебор всех возможных стартовых образов \(s\) даёт точное число изоморфизмов из \(C\) в \(C'\).
Для компоненты \(C\) обозначим через
$$a(C)=\left|\operatorname{Aut}(C)\right|$$
число её цветосохраняющих автоморфизмов. Именно это число вычисляется, когда реализация сравнивает компоненту с самой собой.
Если \(C\) и \(C'\) изоморфны, то число изоморфизмов \(C\to C'\) тоже равно \(a(C)\). Действительно, зафиксируем один изоморфизм \(\varphi:C\to C'\). Тогда любой другой изоморфизм единственным образом записывается как \(\varphi\circ \sigma\), где \(\sigma\in \operatorname{Aut}(C)\).
Пусть некоторый класс изоморфии встречается \(m_j\) раз, а \(a_j\) - число автоморфизмов одного представителя этого класса. Тогда допустимая глобальная перестановка может сначала переставить эти \(m_j\) копий между собой
$$m_j!$$
способами. После выбора целевой копии для каждой исходной компоненты остаётся
$$a_j$$
цветосохраняющих биекций для каждого перехода. Следовательно, вклад этого класса равен
$$a_j^{m_j}\cdot m_j!.$$
Если классы изоморфии обозначены \(\mathcal{C}_1,\dots,\mathcal{C}_t\), то окончательная формула имеет вид
$$\boxed{N=\prod_{j=1}^{t} a_j^{m_j}\cdot m_j! \pmod{P}.}$$
Рассмотрим \(n=4\), где по кроватям имеется пара \(2\leftrightarrow 3\), а по партам пары \(1\leftrightarrow 3\) и \(2\leftrightarrow 4\). В отношении кроватей вершины \(1\) и \(4\) являются неподвижными точками, то есть несут петли цвета кроватей. Вся структура образует одну компоненту связности, и её цветная форма есть чередующийся путь
$$1 \overset{\delta}{\leftrightarrow} 3 \overset{\beta}{\leftrightarrow} 2 \overset{\delta}{\leftrightarrow} 4$$
с петлями цвета кроватей на концах. У этой компоненты ровно два автоморфизма: тождественный и отражение пути. Поэтому ответ равен
$$2,$$
что совпадает с малой проверкой, используемой в реализации.
Реализации на C++, Python и Java сначала сохраняют обе инволюции в виде таблиц на \(1,\dots,n\); любой человек, не входящий явно ни в одну пару, автоматически остаётся неподвижной точкой. Затем граф обходится явным стеком по обоим цветным отношениям, и так выделяются все компоненты связности.
Каждая компонента получает локальную нумерацию, чтобы сравнение не зависело от исходных глобальных меток. При сравнении двух компонент реализация перебирает все возможные образы первой локальной вершины, но только с совпадающим рисунком петель. Для каждого кандидата ограничения по кроватям и партам распространяются по всей компоненте. Противоречие отвергает кандидата, а полное согласованное распространение засчитывается как один изоморфизм.
После группировки компонент по классам изоморфии реализация вычисляет для каждого класса множитель
$$a_j^{m_j}\cdot m_j! \pmod{P}$$
с помощью быстрого модульного возведения в степень и обычного модульного перемножения для факториала. Полный перебор всех \(n!\) перестановок нигде не используется.
Построение двух таблиц инволюций и выделение всех компонент связности требуют \(O(n)\) времени и \(O(n)\) памяти. Если две компоненты имеют размер \(s\), то проверка изоморфизма пробует до \(s\) стартовых образов, а каждое распространение ограничений посещает не более \(s\) локальных вершин. Следовательно, одна проверка стоит \(O(s^2)\) в худшем случае.
Если размеры компонент равны \(s_1,\dots,s_r\), то стадия группировки ограничена теми попарными сравнениями компонент одинакового размера, которые выполняет простая реализация; для реального случая \(n=500\) этого более чем достаточно. Общий расход памяти остаётся линейным по \(n\).
لدينا \(n\) شخصًا وقاعدتا إقران: واحدة للأسرة وأخرى للمكاتب. كل قاعدة هي involution، أي إن كل شخص إما يقترن بشخص واحد بالضبط أو يبقى ثابتًا تحت تلك القاعدة. المطلوب هو عدّ جميع إعادة تسميات الأشخاص التي تحفظ البنيتين معًا، مع أخذ الناتج modulo
$$P=999{,}999{,}937.$$
الفكرة الأساسية هي النظر إلى المعطيات على أنها رسم بياني محدود ذو لونين من الحواف، ناتج عن involutionين. بعد ذلك نجزئ الرسم إلى مركبات متصلة، ثم نعدّ التبديلات الحافظة للبنية عبر تجميع المركبات المتماثلة بنيويًا في فئات واحدة.
لتكن \(V=\{1,2,\dots,n\}\). نرمز إلى علاقة الأسرة بـ \(\beta:V\to V\)، وإلى علاقة المكاتب بـ \(\delta:V\to V\). وبما أنهما involution فإن
$$\beta(\beta(i))=i,\qquad \delta(\delta(i))=i,\qquad i\in V.$$
أي إعادة تسمية هي تبديل \(\pi\) على \(V\). ويكون هذا التبديل صالحًا إذا وفقط إذا حافظ على العلاقتين معًا، أي إذا تحقق
$$\pi(\beta(i))=\beta(\pi(i)),\qquad \pi(\delta(i))=\delta(\pi(i)),\qquad i\in V.$$
إذن نحن نعدّ جميع التبديلات التي تتبادل مع involutionي الأسرة والمكاتب في الوقت نفسه.
نصل كل رأس \(i\) بالرأس \(\beta(i)\) بحافة من نوع السرير، ونصله بالرأس \(\delta(i)\) بحافة من نوع المكتب. النقاط الثابتة مسموح بها، ولذلك قد يحمل الرأس حلقة ذاتية من أحد اللونين. وباحتساب الحلقات، يملك كل رأس حافة سرير واحدة بالضبط وحافة مكتب واحدة بالضبط.
هذا الرسم الملون ينقسم إلى مركبات متصلة. وكل تبديل صالح لا بد أن يرسل كل مركبة إلى مركبة أخرى لها البنية اللونية نفسها تمامًا. لذلك يتفكك العدّ الكلي إلى مساهمات مستقلة بحسب فئات التماثل البنيوي للمركبات.
خذ مركبة \(C\) حجمها \(m\)، وأعد ترقيم رؤوسها محليًا إلى \(0,1,\dots,m-1\). ثم خزّن جدولين محليين: جدولًا يعطي شريك السرير لكل فهرس محلي، وجدولًا يعطي شريك المكتب. بهذه الطريقة تختفي التسميات العالمية الأصلية ويبقى الشكل البنيوي فقط.
إذا كان \(f:C\to C'\) تقابلًا يحفظ اللونين، فلا بد أن يحقق
$$f(p_C(x))=p_{C'}(f(x)),\qquad f(q_C(x))=q_{C'}(f(x)).$$
ولأن المركبة متصلة، ولأن كل رأس يملك جارًا واحدًا فقط من كل لون، فإن اختيار صورة رأس ابتدائي واحد يفرض صور بقية الرؤوس كلها. إما أن يبقى الانتشار متسقًا فنحصل على تماثل صحيح، أو يظهر تناقض فيفشل هذا الاختيار.
وقبل البدء يجب أن يتطابق نمط الحلقات:
$$p_C(r)=r \iff p_{C'}(s)=s,\qquad q_C(r)=r \iff q_{C'}(s)=s.$$
وبتجربة جميع الصور الابتدائية الممكنة \(s\) نحصل على عدد جميع التماثلات من \(C\) إلى \(C'\).
لأي مركبة \(C\)، عرّف
$$a(C)=\left|\operatorname{Aut}(C)\right|,$$
وهو عدد التناظرات الذاتية التي تحفظ اللونين. وهذه هي القيمة التي تحسبها التطبيقات عندما تقارن مركبة بنفسها.
إذا كانت \(C\) و\(C'\) متماثلتين بنيويًا، فإن عدد التماثلات \(C\to C'\) يساوي أيضًا \(a(C)\). والسبب أن تثبيت تماثل واحد \(\varphi:C\to C'\) يجعل كل تماثل آخر يكتب بصورة وحيدة على شكل \(\varphi\circ \sigma\)، حيث \(\sigma\in \operatorname{Aut}(C)\).
افترض أن فئة تماثل معينة تظهر \(m_j\) مرة، وأن \(a_j\) هو عدد التناظرات الذاتية لمركبة ممثلة من هذه الفئة. عندئذ يستطيع التبديل الكلي الصالح أن يعيد ترتيب هذه النسخ \(m_j\) فيما بينها بعدد
$$m_j!$$
من الطرق. وبعد تحديد النسخة الهدف لكل نسخة مصدر، يبقى لكل انتقال عدد
$$a_j$$
من التقابلات الحافظة للألوان. لذلك تكون مساهمة هذه الفئة
$$a_j^{m_j}\cdot m_j!.$$
وإذا كانت فئات التماثل هي \(\mathcal{C}_1,\dots,\mathcal{C}_t\)، فإن الصيغة النهائية هي
$$\boxed{N=\prod_{j=1}^{t} a_j^{m_j}\cdot m_j! \pmod{P}.}$$
خذ الحالة \(n=4\)، مع إقران الأسرة \(2\leftrightarrow 3\)، وإقراني المكاتب \(1\leftrightarrow 3\) و\(2\leftrightarrow 4\). تحت علاقة الأسرة يكون \(1\) و\(4\) نقطتين ثابتتين، ولذلك يحمل الطرفان حلقتين من نوع السرير. البنية كلها تشكل مركبة متصلة واحدة، ويمكن كتابة شكلها الملون على هيئة مسار متناوب:
$$1 \overset{\delta}{\leftrightarrow} 3 \overset{\beta}{\leftrightarrow} 2 \overset{\delta}{\leftrightarrow} 4.$$
مع وجود حلقتي سرير عند الطرفين. لهذه المركبة تناظران ذاتيان فقط: الهوية، والانعكاس الذي يعكس المسار. ومن ثم يكون الجواب
$$2,$$
وهو تمامًا ما يطابق حالة الفحص الصغيرة في التطبيق.
تبدأ تطبيقات C++ وPython وJava بتخزين involutionي الأسرة والمكاتب في جدولين على المجموعة \(1,\dots,n\). وكل شخص لا يظهر صراحة في زوج معطى يُعدّ ثابتًا تلقائيًا. بعد ذلك تُستخرج جميع المركبات المتصلة باستخدام مكدس صريح يسير على علاقتي اللونين.
ثم يُعاد ترقيم كل مركبة محليًا حتى يمكن مقارنتها من غير الرجوع إلى التسميات العالمية الأصلية. وعند مقارنة مركبتين، يحاول التطبيق جميع الصور الممكنة لأول رأس محلي بشرط تطابق نمط الحلقات. ومن كل اختيار ينشر قيود الأسرة والمكاتب عبر المركبة كلها. فإذا ظهر تناقض رُفض الاختيار، وإذا اكتمل الانتشار باتساق عُدّ ذلك تماثلًا واحدًا.
وبعد تجميع المركبات في فئات التماثل، يحسب التطبيق لكل فئة العامل
$$a_j^{m_j}\cdot m_j! \pmod{P}$$
باستخدام رفع سريع للقوة modulo للحاصل \(a_j^{m_j}\)، وضرب modulo عادي لحد \(m_j!\). ولا يجري في أي مرحلة تعداد جميع التبديلات الممكنة وعددها \(n!\).
بناء جدولي involution واستخراج جميع المركبات المتصلة يكلف \(O(n)\) زمنًا و\(O(n)\) ذاكرة. وإذا كان لدينا مركبتان من الحجم \(s\)، فإن اختبار التماثل بينهما يجرب حتى \(s\) صور ابتدائية، وكل عملية انتشار تزور في أقصى الأحوال \(s\) رؤوس محلية. لذا فإن كلفة المقارنة الواحدة هي \(O(s^2)\) في أسوأ حالة.
إذا كانت أحجام المركبات \(s_1,\dots,s_r\)، فإن مرحلة التجميع تحدها المقارنات الزوجية بين المركبات ذات الحجم نفسه التي تنفذها الطريقة المباشرة؛ وبالنسبة إلى الحالة الفعلية \(n=500\) فهذا أكثر من كافٍ عمليًا. ويظل الاستهلاك الكلي للذاكرة خطيًا في \(n\).