We are given an array of \(2n\) elements in which every value occurs exactly twice. The two positions of a value form a chord (an interval) over the row. The array is called connectable when all its chords can be drawn above the row without any two of them crossing.
From one array we may form \(2^n\) new arrays by independently keeping or deleting both occurrences of each value. The connectivity number is the number of those \(2^n\) sub-arrays that are connectable. Equivalently, it counts the subsets of the \(n\) chords that are pairwise non-crossing. The required answer is this count modulo
$$M=1\,003\,443\,221.$$
For example \([0,1,0,1]\) has connectivity number \(3\), and the \(20\)-element array \([0,1,2,3,1,4,0,5,4,2,6,7,3,8,6,5,9,8,9,7]\) has connectivity number \(86\). The target instance is a \(40\,000\)-element array, i.e. \(n=20\,000\) chords.
The number of non-crossing subsets is astronomically large (up to \(2^n\)), so it is accumulated modulo \(M\); brute force over all \(2^n\) subsets is only used to validate the fast method on tiny inputs.
If a value sits at positions \(p \lt q\), its chord is the interval \([p,q]\). Two chords \([a,b]\) and \([c,d]\) with \(a \lt c\) cross exactly when they interleave,
$$a \lt c \lt b \lt d.$$
If they do not interleave they are either nested (one interval contains the other) or disjoint. A set of chords is drawable above the line without crossings precisely when no two of them cross, so the connectivity number equals the number of crossing-free subsets, including the empty subset. In graph terms, build the crossing graph whose vertices are the chords and whose edges join crossing pairs; the connectivity number is the number of independent sets of that graph.
Any pairwise non-crossing collection of chords is a laminar family: any two members are nested or disjoint, never interleaved. Laminar families are exactly the forests of the containment order, and it is this nesting structure — absent in a general graph — that turns the count into a polynomial-time dynamic program rather than an intractable independent-set count.
The fast method does not explicitly build the whole crossing graph. A chord that opens inside \([\ell_i,r_i]\) and closes after \(r_i\) crosses chord \(i\), so it cannot appear in a subset that also contains \(i\). At the instant chord \(i\) closes, every chord fully nested inside it has already closed, while every chord that crosses it is still open. Thus the value already accumulated at slot \(i+1\) is exactly the count of admissible inner choices that can be combined with chord \(i\).
Sort the chords by left endpoint, \(\ell_0 \lt \ell_1 \lt \dots \lt \ell_{n-1}\) (all endpoints are distinct), and write \(r_i\) for the right endpoint of chord \(i\). For each chord define
$$\operatorname{next}(i)=\min\{\,j : \ell_j \gt r_i\,\},$$
the first chord lying entirely to the right of chord \(i\). The chords with index in \((i,\operatorname{next}(i))\) are precisely those that open inside chord \(i\); among them the nested ones close before \(r_i\) while the crossing ones close after \(r_i\).
The algorithm processes chords in order of increasing right endpoint and maintains an array \(\textit{ways}\) (initialised to all ones) together with a companion array \(\textit{delta}\). When chord \(i\) closes, every chord nested inside it has already closed, so the value
$$\textit{inside}(i)=\textit{ways}[i+1]$$
is the number of non-crossing subsets that live strictly inside chord \(i\). The subsets that include chord \(i\) are then obtained by freely combining one such inner configuration with any non-crossing configuration drawn from the chords entirely to its right:
$$\textit{inc}=\textit{inside}(i)\cdot \textit{ways}[\operatorname{next}(i)].$$
This increment is recorded in \(\textit{delta}[i]\) and added into \(\textit{ways}[i]\). It must also reach every earlier chord \(p \lt i\) that is still open and whose nested region has already been passed (\(\operatorname{next}(p)\le i\)): for such a \(p\), the freshly closed chord \(i\) extends the subsets that include \(p\) through the term \(\textit{inside}(p)\cdot \textit{delta}[\operatorname{next}(p)]\). Propagating this contribution down to all earlier slots takes \(O(n)\) work per closing chord, and after the last chord closes the accumulated total is
$$\text{connectivity number}=\textit{ways}[0]\bmod M.$$
The two array entries \(\textit{ways}[i]\) and \(\textit{delta}[i]\) thus encode, respectively, the running count of valid subsets anchored at slot \(i\) and the most recent increment to be forwarded — the bookkeeping that lets a single linear sweep per chord account for both the "nested inside" and "continues to the right" choices.
ways and deltaThink of slot \(s\) as the boundary just before chord \(s\) in left-endpoint order. After each closing event, \(\textit{ways}[s]\) contains all valid selections whose next available left endpoint is at or after slot \(s\), restricted to chords already closed by the sweep. The companion value \(\textit{delta}[s]\) stores only the newest contribution that still has to be forwarded to earlier open ancestors. This separation prevents double-counting: older contributions have already been absorbed into \(\textit{ways}\), while the loop over \(p=i-1,\dots,0\) propagates only the fresh \(\textit{delta}\) term created by the chord that just closed.
Value \(0\) sits at positions \(0,2\) and value \(1\) at positions \(1,3\), giving chords \([0,2]\) and \([1,3]\). Since \(0 \lt 1 \lt 2 \lt 3\) they interleave, so they cross. The crossing-free subsets are therefore \(\varnothing\), \(\{[0,2]\}\) and \(\{[1,3]\}\) — the full pair is excluded — for a connectivity number of \(3\), matching the stated value.
The C++, Python, and Java implementations share the same pipeline. load_csv reads the comma-separated array. build_intervals records the two positions of each value, forms the chords \([p,q]\), sorts them by left endpoint, and asserts that the left endpoints are strictly increasing.
connectivity_number builds \(\operatorname{next}(i)\) with a binary search (upper_bound over the sorted left endpoints), orders the chords by right endpoint, and runs the sweep above using the \(\textit{ways}\), \(\textit{delta}\), \(\textit{inside}\), and \(\textit{active}\) arrays, with all arithmetic carried out modulo \(M\) through add_mod and mul_mod (the latter widening to \(128\) bits in C++; \(64\) bits already suffice in Java and Python since the factors are below \(M\)).
crosses and brute_connectivity form the validation path: the latter simply enumerates all \(2^n\) subsets and counts those with no crossing pair. run_checkpoints checks the published values \(3,8,5,8,86\) on five small arrays and confirms that the fast result equals the brute-force count reduced modulo \(M\); main then evaluates the \(40\,000\)-element instance.
Building the chords costs \(O(n)\) plus \(O(n\log n)\) for the two sorts and the binary searches. The closing sweep performs an \(O(n)\) propagation for each of the \(n\) chords, so the dominant cost is
$$O(n^2)$$
time with \(O(n)\) memory. For \(n=20\,000\) this is a few hundred million constant-time modular operations, comfortably fast in C++. The brute-force checker is exponential, \(O(2^n\cdot n^2)\), and is restricted to the small checkpoint arrays only.
Gegeben ist ein Array mit \(2n\) Elementen, in dem jeder Wert genau zweimal vorkommt. Die beiden Positionen eines Wertes bilden eine Sehne (ein Intervall) über der Zeile. Das Array heißt verbindbar, wenn alle seine Sehnen oberhalb der Zeile gezeichnet werden können, ohne dass sich zwei von ihnen kreuzen.
Aus einem Array können wir \(2^n\) neue Arrays bilden, indem wir die beiden Vorkommen jedes Wertes unabhängig voneinander behalten oder löschen. Die Verbindungszahl ist die Anzahl jener \(2^n\) Teil-Arrays, die verbindbar sind. Äquivalent dazu zählt sie die Teilmengen der \(n\) Sehnen, die paarweise kreuzungsfrei sind. Die gesuchte Antwort ist diese Anzahl modulo
$$M=1\,003\,443\,221.$$
Zum Beispiel hat \([0,1,0,1]\) die Verbindungszahl \(3\), und das \(20\)-elementige Array \([0,1,2,3,1,4,0,5,4,2,6,7,3,8,6,5,9,8,9,7]\) hat die Verbindungszahl \(86\). Die Zielinstanz ist ein \(40\,000\)-elementiges Array, d. h. \(n=20\,000\) Sehnen.
Die Anzahl der kreuzungsfreien Teilmengen ist astronomisch groß (bis zu \(2^n\)), daher wird sie modulo \(M\) akkumuliert; das brachiale Durchprobieren aller \(2^n\) Teilmengen wird nur verwendet, um die schnelle Methode auf winzigen Eingaben zu validieren.
Wenn ein Wert an den Positionen \(p \lt q\) sitzt, ist seine Sehne das Intervall \([p,q]\). Zwei Sehnen \([a,b]\) und \([c,d]\) mit \(a \lt c\) kreuzen sich genau dann, wenn sie sich verschränken,
$$a \lt c \lt b \lt d.$$
Wenn sie sich nicht verschränken, sind sie entweder verschachtelt (ein Intervall enthält das andere) oder disjunkt. Eine Menge von Sehnen ist genau dann oberhalb der Linie kreuzungsfrei zeichenbar, wenn sich keine zwei von ihnen kreuzen, sodass die Verbindungszahl gleich der Anzahl der kreuzungsfreien Teilmengen ist, einschließlich der leeren Teilmenge. In Graphenbegriffen bildet man den Kreuzungsgraphen, dessen Knoten die Sehnen sind und dessen Kanten kreuzende Paare verbinden; die Verbindungszahl ist die Anzahl der unabhängigen Mengen dieses Graphen.
Jede paarweise kreuzungsfreie Ansammlung von Sehnen ist eine laminare Familie: Je zwei Mitglieder sind verschachtelt oder disjunkt, niemals verschränkt. Laminare Familien sind genau die Wälder der Enthaltensordnung, und es ist diese Verschachtelungsstruktur — die in einem allgemeinen Graphen fehlt —, die die Zählung in ein polynomzeitliches dynamisches Programm verwandelt statt in eine unlösbare Zählung unabhängiger Mengen.
Die schnelle Methode baut den gesamten Kreuzungsgraphen nicht explizit auf. Eine Sehne, die innerhalb von \([\ell_i,r_i]\) öffnet und erst nach \(r_i\) schließt, kreuzt die Sehne \(i\) und kann daher nicht in einer Teilmenge vorkommen, die \(i\) ebenfalls enthält. In dem Moment, in dem \(i\) schließt, sind alle vollständig in \(i\) verschachtelten Sehnen bereits geschlossen, während jede \(i\) kreuzende Sehne noch offen ist. Der bis dahin an Platz \(i+1\) angesammelte Wert zählt deshalb genau die zulässigen inneren Auswahlen, die mit Sehne \(i\) kombiniert werden dürfen.
Sortiere die Sehnen nach ihrem linken Endpunkt, \(\ell_0 \lt \ell_1 \lt \dots \lt \ell_{n-1}\) (alle Endpunkte sind verschieden), und schreibe \(r_i\) für den rechten Endpunkt der Sehne \(i\). Für jede Sehne definiere
$$\operatorname{next}(i)=\min\{\,j : \ell_j \gt r_i\,\},$$
die erste Sehne, die vollständig rechts von der Sehne \(i\) liegt. Die Sehnen mit Index in \((i,\operatorname{next}(i))\) sind genau jene, die sich innerhalb der Sehne \(i\) öffnen; unter ihnen schließen die verschachtelten vor \(r_i\), während die kreuzenden nach \(r_i\) schließen.
Der Algorithmus verarbeitet die Sehnen in der Reihenfolge zunehmender rechter Endpunkte und verwaltet ein Array \(\textit{ways}\) (mit lauter Einsen initialisiert) zusammen mit einem begleitenden Array \(\textit{delta}\). Wenn die Sehne \(i\) schließt, hat jede in ihr verschachtelte Sehne bereits geschlossen, sodass der Wert
$$\textit{inside}(i)=\textit{ways}[i+1]$$
die Anzahl der kreuzungsfreien Teilmengen ist, die streng innerhalb der Sehne \(i\) liegen. Die Teilmengen, die die Sehne \(i\) enthalten, erhält man dann, indem man eine solche innere Konfiguration frei mit einer beliebigen kreuzungsfreien Konfiguration aus den vollständig rechts davon liegenden Sehnen kombiniert:
$$\textit{inc}=\textit{inside}(i)\cdot \textit{ways}[\operatorname{next}(i)].$$
Dieser Zuwachs wird in \(\textit{delta}[i]\) festgehalten und zu \(\textit{ways}[i]\) hinzuaddiert. Er muss außerdem jede frühere Sehne \(p \lt i\) erreichen, die noch offen ist und deren verschachtelter Bereich bereits durchlaufen wurde (\(\operatorname{next}(p)\le i\)): Für ein solches \(p\) erweitert die soeben geschlossene Sehne \(i\) die Teilmengen, die \(p\) enthalten, durch den Term \(\textit{inside}(p)\cdot \textit{delta}[\operatorname{next}(p)]\). Diesen Beitrag zu allen früheren Plätzen hinunter weiterzugeben kostet \(O(n)\) Arbeit pro schließender Sehne, und nachdem die letzte Sehne geschlossen hat, ist die akkumulierte Gesamtzahl
$$\text{Verbindungszahl}=\textit{ways}[0]\bmod M.$$
Die beiden Array-Einträge \(\textit{ways}[i]\) und \(\textit{delta}[i]\) kodieren somit jeweils die laufende Anzahl gültiger Teilmengen, die am Platz \(i\) verankert sind, und den jüngsten weiterzugebenden Zuwachs — die Buchführung, die es einem einzigen linearen Durchlauf pro Sehne erlaubt, sowohl die Wahl „innen verschachtelt“ als auch „setzt sich nach rechts fort“ zu berücksichtigen.
ways und deltaMan kann Platz \(s\) als Grenze unmittelbar vor Sehne \(s\) in der Reihenfolge der linken Endpunkte lesen. Nach jedem Schließereignis enthält \(\textit{ways}[s]\) alle gültigen Auswahlen, deren nächster verfügbarer linker Endpunkt bei oder nach Platz \(s\) liegt, beschränkt auf die Sehnen, die der Sweep bereits geschlossen hat. Der Begleitwert \(\textit{delta}[s]\) enthält nur den neuesten Beitrag, der noch zu früheren offenen Vorfahren weitergereicht werden muss. Diese Trennung verhindert Doppelzählung: ältere Beiträge sind schon in \(\textit{ways}\) aufgenommen, während die Schleife über \(p=i-1,\dots,0\) nur den frischen \(\textit{delta}\)-Term der soeben geschlossenen Sehne propagiert.
Der Wert \(0\) sitzt an den Positionen \(0,2\) und der Wert \(1\) an den Positionen \(1,3\), was die Sehnen \([0,2]\) und \([1,3]\) ergibt. Da \(0 \lt 1 \lt 2 \lt 3\), verschränken sie sich, kreuzen sich also. Die kreuzungsfreien Teilmengen sind daher \(\varnothing\), \(\{[0,2]\}\) und \(\{[1,3]\}\) — das vollständige Paar ist ausgeschlossen — für eine Verbindungszahl von \(3\), was dem angegebenen Wert entspricht.
Die C++-, Python- und Java-Implementierungen teilen sich dieselbe Pipeline. load_csv liest das kommagetrennte Array. build_intervals erfasst die beiden Positionen jedes Wertes, bildet die Sehnen \([p,q]\), sortiert sie nach dem linken Endpunkt und stellt sicher, dass die linken Endpunkte streng wachsend sind.
connectivity_number baut \(\operatorname{next}(i)\) mit einer binären Suche auf (upper_bound über die sortierten linken Endpunkte), ordnet die Sehnen nach dem rechten Endpunkt und führt den oben beschriebenen Durchlauf mit den Arrays \(\textit{ways}\), \(\textit{delta}\), \(\textit{inside}\) und \(\textit{active}\) aus, wobei alle Rechnungen modulo \(M\) über add_mod und mul_mod ausgeführt werden (Letzteres erweitert in C++ auf \(128\) Bit; in Java und Python genügen bereits \(64\) Bit, da die Faktoren kleiner als \(M\) sind).
crosses und brute_connectivity bilden den Validierungspfad: Letzteres zählt einfach alle \(2^n\) Teilmengen auf und zählt jene ohne kreuzendes Paar. run_checkpoints überprüft die veröffentlichten Werte \(3,8,5,8,86\) auf fünf kleinen Arrays und bestätigt, dass das schnelle Ergebnis gleich der modulo \(M\) reduzierten brachialen Zählung ist; main wertet anschließend die \(40\,000\)-elementige Instanz aus.
Der Aufbau der Sehnen kostet \(O(n)\) plus \(O(n\log n)\) für die beiden Sortierungen und die binären Suchen. Der Schließ-Durchlauf führt für jede der \(n\) Sehnen eine \(O(n)\)-Weitergabe aus, sodass die dominierenden Kosten
$$O(n^2)$$
Zeit bei \(O(n)\) Speicher betragen. Für \(n=20\,000\) sind das einige hundert Millionen modulare Operationen konstanter Zeit, in C++ bequem schnell. Der brachiale Prüfer ist exponentiell, \(O(2^n\cdot n^2)\), und ist nur auf die kleinen Kontrollpunkt-Arrays beschränkt.
Bize, her değerin tam olarak iki kez geçtiği \(2n\) elemandan oluşan bir dizi verilmiştir. Bir değerin iki konumu, satır üzerinde bir kiriş (bir aralık) oluşturur. Tüm kirişleri, hiçbir ikisi kesişmeyecek şekilde satırın üzerine çizilebiliyorsa diziye bağlanabilir denir.
Bir diziden, her değerin iki geçişini de bağımsız olarak tutarak veya silerek \(2^n\) yeni dizi oluşturabiliriz. Bağlanabilirlik sayısı, bu \(2^n\) alt dizisinden bağlanabilir olanların sayısıdır. Eşdeğer olarak, \(n\) kirişten oluşan ve ikişer ikişer kesişmeyen alt kümelerin sayısını sayar. İstenen cevap, bu sayının şu modülüne göre değeridir:
$$M=1\,003\,443\,221.$$
Örneğin \([0,1,0,1]\) dizisinin bağlanabilirlik sayısı \(3\)'tür ve \(20\) elemanlı \([0,1,2,3,1,4,0,5,4,2,6,7,3,8,6,5,9,8,9,7]\) dizisinin bağlanabilirlik sayısı \(86\)'dır. Hedef örnek, \(40\,000\) elemanlı bir dizidir, yani \(n=20\,000\) kiriş.
Kesişmeyen alt kümelerin sayısı astronomik olarak büyüktür (\(2^n\) değerine kadar çıkar), bu nedenle \(M\) modülüne göre biriktirilir; tüm \(2^n\) alt küme üzerinde kaba kuvvet yöntemi yalnızca hızlı yöntemi küçük girdilerde doğrulamak için kullanılır.
Bir değer \(p \lt q\) konumlarında bulunuyorsa, kirişi \([p,q]\) aralığıdır. \(a \lt c\) olan iki kiriş \([a,b]\) ve \([c,d]\), tam olarak iç içe geçtiklerinde kesişir,
$$a \lt c \lt b \lt d.$$
İç içe geçmiyorlarsa ya yuvalanmış (bir aralık diğerini içerir) ya da ayrıktırlar. Bir kiriş kümesi, tam olarak hiçbir ikisi kesişmediğinde çizgi üzerine kesişmeden çizilebilir; dolayısıyla bağlanabilirlik sayısı, boş alt küme dahil olmak üzere kesişmesiz alt kümelerin sayısına eşittir. Çizge terimleriyle, köşeleri kirişler olan ve kenarları kesişen çiftleri birleştiren kesişme çizgesini kurun; bağlanabilirlik sayısı, bu çizgenin bağımsız kümelerinin sayısıdır.
İkişer ikişer kesişmeyen herhangi bir kiriş topluluğu bir laminer ailedir: herhangi iki üye yuvalanmış veya ayrıktır, asla iç içe geçmez. Laminer aileler tam olarak içerme sıralamasının ormanlarıdır ve sayımı, çözülemez bir bağımsız küme sayımı yerine polinom zamanlı bir dinamik programlamaya dönüştüren — genel bir çizgede bulunmayan — işte bu yuvalanma yapısıdır.
Hızlı yöntem tüm kesişme çizgesini açıkça kurmaz. \([\ell_i,r_i]\) içinde açılıp \(r_i\)'den sonra kapanan bir kiriş, \(i\) kirişiyle kesişir; bu yüzden \(i\)'yi içeren bir alt kümede yer alamaz. \(i\) kirişi kapandığı anda, onun içinde tamamen yuvalanmış her kiriş zaten kapanmıştır, fakat onu kesen her kiriş hâlâ açıktır. Dolayısıyla \(i+1\) yuvasında o ana kadar birikmiş değer, \(i\) kirişiyle birleştirilebilecek uygun iç seçimlerin tam sayısıdır.
Kirişleri sol uç noktalarına göre sıralayın, \(\ell_0 \lt \ell_1 \lt \dots \lt \ell_{n-1}\) (tüm uç noktalar farklıdır) ve \(i\) kirişinin sağ uç noktasını \(r_i\) ile gösterin. Her kiriş için şunu tanımlayın:
$$\operatorname{next}(i)=\min\{\,j : \ell_j \gt r_i\,\},$$
bu, tamamen \(i\) kirişinin sağında yer alan ilk kiriştir. İndisi \((i,\operatorname{next}(i))\) içinde olan kirişler tam olarak \(i\) kirişinin içinde açılanlardır; bunların arasında yuvalanmış olanlar \(r_i\)'den önce kapanırken, kesişenler \(r_i\)'den sonra kapanır.
Algoritma, kirişleri artan sağ uç noktası sırasıyla işler ve bir yardımcı dizi \(\textit{delta}\) ile birlikte bir \(\textit{ways}\) dizisini (tümü birlere ilklenmiş) tutar. \(i\) kirişi kapandığında, içine yuvalanmış her kiriş zaten kapanmış olur, dolayısıyla şu değer
$$\textit{inside}(i)=\textit{ways}[i+1]$$
\(i\) kirişinin tam olarak içinde yaşayan kesişmeyen alt kümelerin sayısıdır. \(i\) kirişini içeren alt kümeler ise, böyle bir iç yapılandırmayı, tamamen sağındaki kirişlerden çizilen herhangi bir kesişmeyen yapılandırmayla serbestçe birleştirerek elde edilir:
$$\textit{inc}=\textit{inside}(i)\cdot \textit{ways}[\operatorname{next}(i)].$$
Bu artış \(\textit{delta}[i]\) içinde kaydedilir ve \(\textit{ways}[i]\) içine eklenir. Bunun ayrıca, hâlâ açık olan ve yuvalanmış bölgesi zaten geçilmiş olan (\(\operatorname{next}(p)\le i\)) her önceki \(p \lt i\) kirişine de ulaşması gerekir: böyle bir \(p\) için, yeni kapanmış \(i\) kirişi, \(p\) kirişini içeren alt kümeleri \(\textit{inside}(p)\cdot \textit{delta}[\operatorname{next}(p)]\) terimi aracılığıyla genişletir. Bu katkıyı tüm önceki yuvalara doğru yaymak, kapanan kiriş başına \(O(n)\) işlem alır ve son kiriş kapandıktan sonra birikmiş toplam şudur:
$$\text{bağlanabilirlik sayısı}=\textit{ways}[0]\bmod M.$$
İki dizi girdisi \(\textit{ways}[i]\) ve \(\textit{delta}[i]\), böylece sırasıyla, \(i\) yuvasına dayanan geçerli alt kümelerin çalışan sayısını ve iletilecek en son artışı kodlar — kiriş başına tek bir doğrusal taramanın hem "içine yuvalanmış" hem de "sağa devam eder" seçimlerini hesaba katmasını sağlayan defter tutma işlemi.
ways ve delta arkasındaki değişmez\(s\) yuvasını, sol uç noktası sırasındaki \(s\) kirişinden hemen önceki sınır gibi düşünün. Her kapanış olayından sonra \(\textit{ways}[s]\), sıradaki kullanılabilir sol uç noktası \(s\) yuvasında veya sonrasında olan tüm geçerli seçimleri içerir; bu seçimler yalnızca taramanın o ana kadar kapattığı kirişlerden oluşur. Eşlik eden \(\textit{delta}[s]\) değeri ise daha önceki açık atalara aktarılması gereken en yeni katkıyı tutar. Bu ayrım çift saymayı önler: eski katkılar zaten \(\textit{ways}\) içine alınmıştır, \(p=i-1,\dots,0\) döngüsü yalnızca yeni kapanan kirişin ürettiği taze \(\textit{delta}\) terimini taşır.
\(0\) değeri \(0,2\) konumlarında ve \(1\) değeri \(1,3\) konumlarında bulunur, bu da \([0,2]\) ve \([1,3]\) kirişlerini verir. \(0 \lt 1 \lt 2 \lt 3\) olduğundan iç içe geçerler, dolayısıyla kesişirler. Bu nedenle kesişmesiz alt kümeler \(\varnothing\), \(\{[0,2]\}\) ve \(\{[1,3]\}\)'tür — tam çift hariç tutulur — bu da belirtilen değerle eşleşen \(3\) bağlanabilirlik sayısını verir.
C++, Python ve Java uygulamaları aynı işlem hattını paylaşır. load_csv virgülle ayrılmış diziyi okur. build_intervals her değerin iki konumunu kaydeder, \([p,q]\) kirişlerini oluşturur, bunları sol uç noktalarına göre sıralar ve sol uç noktaların kesinlikle artan olduğunu doğrular.
connectivity_number, \(\operatorname{next}(i)\)'yi bir ikili arama ile (sıralanmış sol uç noktalar üzerinde upper_bound) oluşturur, kirişleri sağ uç noktaya göre sıralar ve yukarıdaki taramayı \(\textit{ways}\), \(\textit{delta}\), \(\textit{inside}\) ve \(\textit{active}\) dizilerini kullanarak çalıştırır; tüm aritmetik, add_mod ve mul_mod aracılığıyla \(M\) modülüne göre yürütülür (ikincisi C++'ta \(128\) bite genişler; çarpanlar \(M\)'nin altında olduğundan Java ve Python'da \(64\) bit zaten yeterlidir).
crosses ve brute_connectivity doğrulama yolunu oluşturur: ikincisi basitçe tüm \(2^n\) alt kümeyi numaralandırır ve kesişen çifti olmayanları sayar. run_checkpoints, beş küçük dizi üzerinde yayınlanmış \(3,8,5,8,86\) değerlerini kontrol eder ve hızlı sonucun, \(M\) modülüne göre indirgenmiş kaba kuvvet sayımına eşit olduğunu doğrular; main ardından \(40\,000\) elemanlı örneği değerlendirir.
Kirişlerin oluşturulması \(O(n)\) artı iki sıralama ve ikili aramalar için \(O(n\log n)\) maliyete sahiptir. Kapanış taraması, \(n\) kirişin her biri için \(O(n)\) bir yayılma gerçekleştirir, dolayısıyla baskın maliyet şudur:
$$O(n^2)$$
\(O(n)\) bellek ile zaman. \(n=20\,000\) için bu, birkaç yüz milyon sabit zamanlı modüler işlemdir ve C++'ta rahatça hızlıdır. Kaba kuvvet denetleyicisi üsteldir, \(O(2^n\cdot n^2)\), ve yalnızca küçük kontrol noktası dizileriyle sınırlıdır.
Se nos da un arreglo de \(2n\) elementos en el que cada valor aparece exactamente dos veces. Las dos posiciones de un valor forman una cuerda (un intervalo) sobre la fila. El arreglo se denomina conectable cuando todas sus cuerdas pueden dibujarse por encima de la fila sin que ninguna de ellas se cruce.
A partir de un arreglo podemos formar \(2^n\) nuevos arreglos conservando o eliminando de forma independiente ambas apariciones de cada valor. El número de conectividad es el número de esos \(2^n\) subarreglos que son conectables. De forma equivalente, cuenta los subconjuntos de las \(n\) cuerdas que no se cruzan entre sí por pares. La respuesta requerida es este conteo módulo
$$M=1\,003\,443\,221.$$
Por ejemplo, \([0,1,0,1]\) tiene número de conectividad \(3\), y el arreglo de \(20\) elementos \([0,1,2,3,1,4,0,5,4,2,6,7,3,8,6,5,9,8,9,7]\) tiene número de conectividad \(86\). La instancia objetivo es un arreglo de \(40\,000\) elementos, es decir, \(n=20\,000\) cuerdas.
El número de subconjuntos sin cruces es astronómicamente grande (hasta \(2^n\)), por lo que se acumula módulo \(M\); la fuerza bruta sobre todos los \(2^n\) subconjuntos solo se usa para validar el método rápido en entradas diminutas.
Si un valor se ubica en las posiciones \(p \lt q\), su cuerda es el intervalo \([p,q]\). Dos cuerdas \([a,b]\) y \([c,d]\) con \(a \lt c\) se cruzan exactamente cuando se entrelazan,
$$a \lt c \lt b \lt d.$$
Si no se entrelazan, están anidadas (un intervalo contiene al otro) o son disjuntas. Un conjunto de cuerdas puede dibujarse por encima de la línea sin cruces precisamente cuando ningún par de ellas se cruza, de modo que el número de conectividad es igual al número de subconjuntos libres de cruces, incluyendo el subconjunto vacío. En términos de grafos, se construye el grafo de cruces cuyos vértices son las cuerdas y cuyas aristas unen los pares que se cruzan; el número de conectividad es el número de conjuntos independientes de ese grafo.
Cualquier colección de cuerdas que no se crucen por pares es una familia laminar: dos miembros cualesquiera están anidados o son disjuntos, nunca entrelazados. Las familias laminares son exactamente los bosques del orden de contención, y es esta estructura de anidamiento — ausente en un grafo general — la que convierte el conteo en un programa dinámico de tiempo polinómico en lugar de un intratable conteo de conjuntos independientes.
El método rápido no construye explícitamente todo el grafo de cruces. Una cuerda que se abre dentro de \([\ell_i,r_i]\) y se cierra después de \(r_i\) cruza a la cuerda \(i\), por lo que no puede aparecer en un subconjunto que también contenga a \(i\). En el instante en que \(i\) se cierra, toda cuerda completamente anidada en ella ya se ha cerrado, mientras que toda cuerda que la cruza sigue abierta. Por eso el valor acumulado en la ranura \(i+1\) cuenta exactamente las elecciones internas admisibles que pueden combinarse con la cuerda \(i\).
Ordene las cuerdas por extremo izquierdo, \(\ell_0 \lt \ell_1 \lt \dots \lt \ell_{n-1}\) (todos los extremos son distintos), y escriba \(r_i\) para el extremo derecho de la cuerda \(i\). Para cada cuerda defina
$$\operatorname{next}(i)=\min\{\,j : \ell_j \gt r_i\,\},$$
la primera cuerda que se sitúa enteramente a la derecha de la cuerda \(i\). Las cuerdas con índice en \((i,\operatorname{next}(i))\) son precisamente aquellas que abren dentro de la cuerda \(i\); entre ellas las anidadas cierran antes de \(r_i\) mientras que las que se cruzan cierran después de \(r_i\).
El algoritmo procesa las cuerdas en orden de extremo derecho creciente y mantiene un arreglo \(\textit{ways}\) (inicializado todo a unos) junto con un arreglo acompañante \(\textit{delta}\). Cuando la cuerda \(i\) cierra, toda cuerda anidada dentro de ella ya ha cerrado, de modo que el valor
$$\textit{inside}(i)=\textit{ways}[i+1]$$
es el número de subconjuntos sin cruces que viven estrictamente dentro de la cuerda \(i\). Los subconjuntos que incluyen la cuerda \(i\) se obtienen entonces combinando libremente una de tales configuraciones internas con cualquier configuración sin cruces extraída de las cuerdas situadas enteramente a su derecha:
$$\textit{inc}=\textit{inside}(i)\cdot \textit{ways}[\operatorname{next}(i)].$$
Este incremento se registra en \(\textit{delta}[i]\) y se añade a \(\textit{ways}[i]\). También debe alcanzar a toda cuerda anterior \(p \lt i\) que siga abierta y cuya región anidada ya haya sido superada (\(\operatorname{next}(p)\le i\)): para tal \(p\), la cuerda recién cerrada \(i\) extiende los subconjuntos que incluyen a \(p\) mediante el término \(\textit{inside}(p)\cdot \textit{delta}[\operatorname{next}(p)]\). Propagar esta contribución hacia abajo a todas las ranuras anteriores requiere \(O(n)\) de trabajo por cada cuerda que cierra, y después de que cierra la última cuerda el total acumulado es
$$\text{número de conectividad}=\textit{ways}[0]\bmod M.$$
Las dos entradas del arreglo \(\textit{ways}[i]\) y \(\textit{delta}[i]\) codifican así, respectivamente, el conteo en curso de subconjuntos válidos anclados en la ranura \(i\) y el incremento más reciente que se va a propagar — la contabilidad que permite que un único barrido lineal por cuerda dé cuenta tanto de la elección "anidado dentro" como de la elección "continúa a la derecha".
ways y deltaPiense en la ranura \(s\) como la frontera justo antes de la cuerda \(s\) en el orden de extremos izquierdos. Tras cada cierre, \(\textit{ways}[s]\) contiene todas las selecciones válidas cuyo siguiente extremo izquierdo disponible está en la ranura \(s\) o después, restringidas a las cuerdas ya cerradas por el barrido. El valor \(\textit{delta}[s]\) guarda solo la contribución más reciente que todavía debe propagarse hacia ancestros abiertos anteriores. Esta separación evita contar dos veces: las contribuciones antiguas ya fueron absorbidas por \(\textit{ways}\), y el bucle sobre \(p=i-1,\dots,0\) propaga únicamente el término \(\textit{delta}\) recién creado por la cuerda que acaba de cerrarse.
El valor \(0\) se ubica en las posiciones \(0,2\) y el valor \(1\) en las posiciones \(1,3\), dando las cuerdas \([0,2]\) y \([1,3]\). Como \(0 \lt 1 \lt 2 \lt 3\) se entrelazan, por lo que se cruzan. Los subconjuntos libres de cruces son por tanto \(\varnothing\), \(\{[0,2]\}\) y \(\{[1,3]\}\) — el par completo queda excluido — para un número de conectividad de \(3\), coincidiendo con el valor indicado.
Las implementaciones en C++, Python y Java comparten la misma canalización. load_csv lee el arreglo separado por comas. build_intervals registra las dos posiciones de cada valor, forma las cuerdas \([p,q]\), las ordena por extremo izquierdo, y verifica que los extremos izquierdos sean estrictamente crecientes.
connectivity_number construye \(\operatorname{next}(i)\) con una búsqueda binaria (upper_bound sobre los extremos izquierdos ordenados), ordena las cuerdas por extremo derecho, y ejecuta el barrido anterior usando los arreglos \(\textit{ways}\), \(\textit{delta}\), \(\textit{inside}\) y \(\textit{active}\), con toda la aritmética efectuada módulo \(M\) a través de add_mod y mul_mod (este último ampliando a \(128\) bits en C++; \(64\) bits ya bastan en Java y Python ya que los factores están por debajo de \(M\)).
crosses y brute_connectivity forman la ruta de validación: este último simplemente enumera todos los \(2^n\) subconjuntos y cuenta aquellos sin ningún par que se cruce. run_checkpoints comprueba los valores publicados \(3,8,5,8,86\) en cinco arreglos pequeños y confirma que el resultado rápido es igual al conteo por fuerza bruta reducido módulo \(M\); main evalúa entonces la instancia de \(40\,000\) elementos.
Construir las cuerdas cuesta \(O(n)\) más \(O(n\log n)\) por los dos ordenamientos y las búsquedas binarias. El barrido de cierre realiza una propagación \(O(n)\) por cada una de las \(n\) cuerdas, de modo que el costo dominante es
$$O(n^2)$$
de tiempo con \(O(n)\) de memoria. Para \(n=20\,000\) esto representa unos pocos cientos de millones de operaciones modulares de tiempo constante, cómodamente rápido en C++. El verificador por fuerza bruta es exponencial, \(O(2^n\cdot n^2)\), y se restringe únicamente a los pequeños arreglos de control.
给定一个包含 \(2n\) 个元素的数组，其中每个值恰好出现两次。某个值的两个位置在该行上构成一条弦（一个区间）。当一个数组的所有弦都可以画在该行上方且任意两条弦都不相交时，称这个数组是可连接的。
从一个数组出发，我们可以通过独立地保留或删除每个值的两次出现来构造出 \(2^n\) 个新数组。连通数是这 \(2^n\) 个子数组中可连接的个数。等价地，它统计了 \(n\) 条弦中两两不相交的子集的数量。所求答案是这个计数对下式取模
$$M=1\,003\,443\,221.$$
例如 \([0,1,0,1]\) 的连通数为 \(3\)，而 \(20\) 元素数组 \([0,1,2,3,1,4,0,5,4,2,6,7,3,8,6,5,9,8,9,7]\) 的连通数为 \(86\)。目标实例是一个 \(40\,000\) 元素的数组，即 \(n=20\,000\) 条弦。
不相交子集的数量大得惊人（至多 \(2^n\)），因此累加时对 \(M\) 取模；对全部 \(2^n\) 个子集进行的暴力枚举仅用于在极小输入上验证快速方法。
若某个值位于位置 \(p \lt q\)，则它的弦是区间 \([p,q]\)。两条弦 \([a,b]\) 和 \([c,d]\)（其中 \(a \lt c\)）相交当且仅当它们交错，即
$$a \lt c \lt b \lt d.$$
若它们不交错，则要么是嵌套的（一个区间包含另一个），要么是不相交的。一组弦可以画在直线上方且彼此不相交，当且仅当其中任意两条都不相交，因此连通数等于无相交子集的数量，包括空子集。用图论的语言来说，构造一个相交图，其顶点是各条弦，其边连接相交的弦对；连通数就是该图的独立集数量。
任何两两不相交的弦的集合都是一个层状族：任意两个成员要么嵌套，要么不相交，绝不交错。层状族恰好是包含序的森林，正是这种嵌套结构——在一般图中并不存在——使得这个计数变成了多项式时间的动态规划，而非难解的独立集计数。
快速方法并不显式构造整个相交图。如果一条弦在 \([\ell_i,r_i]\) 内部开启、却在 \(r_i\) 之后闭合，那么它与弦 \(i\) 相交，因此不能出现在同时包含 \(i\) 的子集中。当弦 \(i\) 闭合时，完全嵌套在它内部的弦都已经闭合，而所有与它相交的弦仍然是开启状态。因此，位置 \(i+1\) 已经累积的值，正好就是可以与弦 \(i\) 组合的合法内部选择数。
将各条弦按左端点排序，\(\ell_0 \lt \ell_1 \lt \dots \lt \ell_{n-1}\)（所有端点都各不相同），并记 \(r_i\) 为弦 \(i\) 的右端点。对每条弦定义
$$\operatorname{next}(i)=\min\{\,j : \ell_j \gt r_i\,\},$$
即完全位于弦 \(i\) 右侧的第一条弦。索引在 \((i,\operatorname{next}(i))\) 范围内的弦正是那些在弦 \(i\) 内部开启的弦；其中嵌套的弦在 \(r_i\) 之前闭合，而相交的弦在 \(r_i\) 之后闭合。
算法按右端点递增的顺序处理各条弦，并维护一个数组 \(\textit{ways}\)（初始化为全 1）以及一个配套数组 \(\textit{delta}\)。当弦 \(i\) 闭合时，嵌套在它内部的每条弦都已经闭合，因此值
$$\textit{inside}(i)=\textit{ways}[i+1]$$
就是严格位于弦 \(i\) 内部的不相交子集的数量。然后，包含弦 \(i\) 的那些子集可以通过将这样一个内部配置与从其右侧所有弦中选取的任意不相交配置自由组合得到：
$$\textit{inc}=\textit{inside}(i)\cdot \textit{ways}[\operatorname{next}(i)].$$
这个增量被记录在 \(\textit{delta}[i]\) 中，并加入到 \(\textit{ways}[i]\) 内。它还必须传递到每一条更早的、仍然开启且其嵌套区域已被越过（\(\operatorname{next}(p)\le i\)）的弦 \(p \lt i\)：对于这样的 \(p\)，刚刚闭合的弦 \(i\) 通过项 \(\textit{inside}(p)\cdot \textit{delta}[\operatorname{next}(p)]\) 扩展了包含 \(p\) 的那些子集。将这一贡献向下传播到所有更早的位置，每闭合一条弦需要 \(O(n)\) 的工作量，而在最后一条弦闭合之后，累积的总数为
$$\text{连通数}=\textit{ways}[0]\bmod M.$$
因此，两个数组元素 \(\textit{ways}[i]\) 和 \(\textit{delta}[i]\) 分别编码了以位置 \(i\) 为锚点的有效子集的运行计数，以及待向前传递的最近一次增量——正是这种记账方式，使得对每条弦进行单次线性扫描就能同时处理“嵌套于内部”和“向右继续”这两种选择。
ways 与 delta 的不变量可以把位置 \(s\) 看成按左端点排序时弦 \(s\) 之前的边界。每次闭合事件之后，\(\textit{ways}[s]\) 包含所有下一个可用左端点位于位置 \(s\) 或其后的合法选择，并且只使用扫描已经闭合的弦。配套的 \(\textit{delta}[s]\) 只保存仍需传给更早开启祖先的最新贡献。这种分离避免了重复计数：旧贡献已经进入 \(\textit{ways}\)，而循环 \(p=i-1,\dots,0\) 只传播刚闭合的那条弦产生的新 \(\textit{delta}\) 项。
值 \(0\) 位于位置 \(0,2\)，值 \(1\) 位于位置 \(1,3\)，从而给出弦 \([0,2]\) 和 \([1,3]\)。由于 \(0 \lt 1 \lt 2 \lt 3\)，它们交错，因此相交。于是无相交的子集为 \(\varnothing\)、\(\{[0,2]\}\) 和 \(\{[1,3]\}\)——完整的一对被排除——连通数为 \(3\)，与所给的值相符。
C++、Python 和 Java 的实现共享同一条流水线。load_csv 读取以逗号分隔的数组。build_intervals 记录每个值的两个位置，构造弦 \([p,q]\)，按左端点对它们排序，并断言左端点严格递增。
connectivity_number 用二分查找（在已排序的左端点上执行 upper_bound）构造 \(\operatorname{next}(i)\)，按右端点对各条弦排序，并使用 \(\textit{ways}\)、\(\textit{delta}\)、\(\textit{inside}\) 和 \(\textit{active}\) 数组运行上述扫描，所有算术运算都通过 add_mod 和 mul_mod 在模 \(M\) 下进行（后者在 C++ 中扩展到 \(128\) 位；由于各因子都小于 \(M\)，在 Java 和 Python 中 \(64\) 位已经足够）。
crosses 和 brute_connectivity 构成验证路径：后者只是枚举全部 \(2^n\) 个子集并统计其中没有相交对的子集数量。run_checkpoints 在五个小数组上核对已公布的值 \(3,8,5,8,86\)，并确认快速结果等于暴力计数对 \(M\) 取模后的值；main 随后对 \(40\,000\) 元素的实例进行求值。
构造各条弦花费 \(O(n)\)，再加上两次排序和二分查找所需的 \(O(n\log n)\)。闭合扫描对 \(n\) 条弦中的每一条执行一次 \(O(n)\) 的传播，因此主导开销为
$$O(n^2)$$
时间，配以 \(O(n)\) 的内存。对于 \(n=20\,000\)，这相当于几亿次常数时间的模运算，在 C++ 中可以轻松快速完成。暴力检查器是指数级的，\(O(2^n\cdot n^2)\)，仅限用于小型检查点数组。
Дан массив из \(2n\) элементов, в котором каждое значение встречается ровно дважды. Две позиции одного значения образуют хорду (интервал) над строкой. Массив называется соединимым, когда все его хорды можно нарисовать над строкой так, чтобы никакие две из них не пересекались.
Из одного массива можно образовать \(2^n\) новых массивов, независимо сохраняя или удаляя оба вхождения каждого значения. Число связности — это количество тех из \(2^n\) подмассивов, которые являются соединимыми. Эквивалентно, оно подсчитывает подмножества из \(n\) хорд, которые попарно не пересекаются. Искомый ответ — это количество по модулю
$$M=1\,003\,443\,221.$$
Например, у \([0,1,0,1]\) число связности равно \(3\), а у массива из \(20\) элементов \([0,1,2,3,1,4,0,5,4,2,6,7,3,8,6,5,9,8,9,7]\) число связности равно \(86\). Целевой экземпляр — это массив из \(40\,000\) элементов, то есть \(n=20\,000\) хорд.
Количество непересекающихся подмножеств астрономически велико (вплоть до \(2^n\)), поэтому оно накапливается по модулю \(M\); полный перебор по всем \(2^n\) подмножествам используется лишь для проверки быстрого метода на крошечных входных данных.
Если значение находится на позициях \(p \lt q\), его хорда — это интервал \([p,q]\). Две хорды \([a,b]\) и \([c,d]\), где \(a \lt c\), пересекаются ровно тогда, когда они чередуются,
$$a \lt c \lt b \lt d.$$
Если они не чередуются, то они либо вложены (один интервал содержит другой), либо не пересекаются (разделены). Множество хорд можно нарисовать над линией без пересечений в точности тогда, когда никакие две из них не пересекаются, поэтому число связности равно количеству подмножеств без пересечений, включая пустое подмножество. В терминах графов построим граф пересечений, вершинами которого являются хорды, а рёбра соединяют пересекающиеся пары; число связности — это количество независимых множеств этого графа.
Любая попарно непересекающаяся совокупность хорд является ламинарным семейством: любые два её члена вложены или разделены, никогда не чередуются. Ламинарные семейства — это в точности леса порядка вложенности, и именно эта структура вложенности — отсутствующая в общем графе — превращает подсчёт в полиномиальную по времени динамическую программу, а не в неразрешимый подсчёт независимых множеств.
Быстрый метод не строит весь граф пересечений явно. Хорда, которая открывается внутри \([\ell_i,r_i]\), но закрывается после \(r_i\), пересекает хорду \(i\), поэтому не может входить в подмножество, содержащее \(i\). В момент закрытия хорды \(i\) все хорды, полностью вложенные в неё, уже закрыты, а все хорды, пересекающие её, ещё открыты. Поэтому значение, уже накопленное в слоте \(i+1\), ровно считает допустимые внутренние выборы, которые можно сочетать с хордой \(i\).
Упорядочим хорды по левому концу, \(\ell_0 \lt \ell_1 \lt \dots \lt \ell_{n-1}\) (все концы различны), и обозначим через \(r_i\) правый конец хорды \(i\). Для каждой хорды определим
$$\operatorname{next}(i)=\min\{\,j : \ell_j \gt r_i\,\},$$
первую хорду, лежащую целиком справа от хорды \(i\). Хорды с индексом из \((i,\operatorname{next}(i))\) — это в точности те, которые открываются внутри хорды \(i\); среди них вложенные закрываются раньше \(r_i\), а пересекающиеся закрываются позже \(r_i\).
Алгоритм обрабатывает хорды в порядке возрастания правого конца и поддерживает массив \(\textit{ways}\) (инициализированный всеми единицами) вместе с сопутствующим массивом \(\textit{delta}\). Когда хорда \(i\) закрывается, каждая вложенная внутри неё хорда уже закрыта, поэтому величина
$$\textit{inside}(i)=\textit{ways}[i+1]$$
— это количество непересекающихся подмножеств, которые целиком лежат внутри хорды \(i\). Подмножества, которые включают хорду \(i\), затем получаются свободным комбинированием одной такой внутренней конфигурации с любой непересекающейся конфигурацией, составленной из хорд, целиком лежащих справа от неё:
$$\textit{inc}=\textit{inside}(i)\cdot \textit{ways}[\operatorname{next}(i)].$$
Этот прирост записывается в \(\textit{delta}[i]\) и добавляется к \(\textit{ways}[i]\). Он также должен достичь каждой более ранней хорды \(p \lt i\), которая всё ещё открыта и чья вложенная область уже пройдена (\(\operatorname{next}(p)\le i\)): для такой \(p\) только что закрывшаяся хорда \(i\) расширяет подмножества, включающие \(p\), через член \(\textit{inside}(p)\cdot \textit{delta}[\operatorname{next}(p)]\). Распространение этого вклада вниз на все более ранние ячейки требует \(O(n)\) работы на каждую закрывающуюся хорду, и после закрытия последней хорды накопленный итог равен
$$\text{число связности}=\textit{ways}[0]\bmod M.$$
Таким образом, две записи массива \(\textit{ways}[i]\) и \(\textit{delta}[i]\) кодируют, соответственно, текущий счёт допустимых подмножеств, привязанных к ячейке \(i\), и самый последний прирост для передачи дальше — учёт, который позволяет одному линейному проходу на хорду охватить как выбор «вложено внутрь», так и выбор «продолжается справа».
ways и deltaСлот \(s\) можно понимать как границу непосредственно перед хордой \(s\) в порядке левых концов. После каждого закрытия \(\textit{ways}[s]\) содержит все допустимые выборы, у которых следующий доступный левый конец находится в слоте \(s\) или правее, с ограничением на хорды, уже закрытые развёрткой. Величина \(\textit{delta}[s]\) хранит только самый новый вклад, который ещё надо передать более ранним открытым предкам. Это разделение предотвращает двойной счёт: старые вклады уже поглощены \(\textit{ways}\), а цикл по \(p=i-1,\dots,0\) передаёт только свежий член \(\textit{delta}\), созданный только что закрытой хордой.
Значение \(0\) находится на позициях \(0,2\), а значение \(1\) на позициях \(1,3\), что даёт хорды \([0,2]\) и \([1,3]\). Поскольку \(0 \lt 1 \lt 2 \lt 3\), они чередуются, поэтому они пересекаются. Подмножества без пересечений — это, следовательно, \(\varnothing\), \(\{[0,2]\}\) и \(\{[1,3]\}\) — полная пара исключена — что даёт число связности \(3\), совпадающее с указанным значением.
Реализации на C++, Python и Java используют один и тот же конвейер. load_csv считывает массив, разделённый запятыми. build_intervals записывает две позиции каждого значения, формирует хорды \([p,q]\), сортирует их по левому концу и проверяет, что левые концы строго возрастают.
connectivity_number строит \(\operatorname{next}(i)\) с помощью двоичного поиска (upper_bound по отсортированным левым концам), упорядочивает хорды по правому концу и выполняет описанный выше проход, используя массивы \(\textit{ways}\), \(\textit{delta}\), \(\textit{inside}\) и \(\textit{active}\), причём вся арифметика выполняется по модулю \(M\) через add_mod и mul_mod (последний расширяется до \(128\) бит в C++; \(64\) бит уже достаточно в Java и Python, поскольку множители меньше \(M\)).
crosses и brute_connectivity образуют путь проверки: последний просто перечисляет все \(2^n\) подмножеств и подсчитывает те, у которых нет пересекающейся пары. run_checkpoints проверяет опубликованные значения \(3,8,5,8,86\) на пяти небольших массивах и подтверждает, что быстрый результат равен счёту полного перебора, приведённому по модулю \(M\); main затем вычисляет экземпляр из \(40\,000\) элементов.
Построение хорд стоит \(O(n)\) плюс \(O(n\log n)\) на две сортировки и двоичные поиски. Закрывающий проход выполняет \(O(n)\) распространение для каждой из \(n\) хорд, поэтому доминирующая стоимость составляет
$$O(n^2)$$
времени при \(O(n)\) памяти. Для \(n=20\,000\) это несколько сотен миллионов модульных операций постоянного времени, вполне быстро на C++. Проверщик полным перебором экспоненциален, \(O(2^n\cdot n^2)\), и ограничен только небольшими контрольными массивами.
لدينا مصفوفة من \(2n\) عنصرًا تظهر فيها كل قيمة مرتين بالضبط. يشكّل الموضعان لقيمة ما وترًا (فترة) فوق الصف. تُسمى المصفوفة قابلة للوصل عندما يمكن رسم جميع أوتارها فوق الصف دون أن يتقاطع أي وترين منها.
من مصفوفة واحدة يمكننا تكوين \(2^n\) مصفوفة جديدة بالإبقاء على كلا ظهوري كل قيمة أو حذفهما بشكل مستقل. عدد الوصل هو عدد تلك المصفوفات الجزئية \(2^n\) التي تكون قابلة للوصل. وبصورة مكافئة، فهو يحصي المجموعات الجزئية من الأوتار \(n\) التي تكون غير متقاطعة بشكل ثنائي. الإجابة المطلوبة هي هذا العدد بمقياس
$$M=1\,003\,443\,221.$$
على سبيل المثال، \([0,1,0,1]\) لها عدد وصل يساوي \(3\)، والمصفوفة المكونة من \(20\) عنصرًا \([0,1,2,3,1,4,0,5,4,2,6,7,3,8,6,5,9,8,9,7]\) لها عدد وصل يساوي \(86\). الحالة المستهدفة هي مصفوفة من \(40\,000\) عنصر، أي \(n=20\,000\) وترًا.
عدد المجموعات الجزئية غير المتقاطعة كبير بشكل فلكي (يصل إلى \(2^n\))، لذا يُجمَّع بمقياس \(M\)؛ ولا تُستخدم القوة الغاشمة على جميع المجموعات الجزئية \(2^n\) إلا للتحقق من صحة الطريقة السريعة على المدخلات الصغيرة جدًا.
إذا كانت قيمة ما تقع في الموضعين \(p \lt q\)، فإن وترها هو الفترة \([p,q]\). يتقاطع وتران \([a,b]\) و\([c,d]\) حيث \(a \lt c\) تقاطعًا تمامًا عندما يتداخلان،
$$a \lt c \lt b \lt d.$$
إذا لم يتداخلا فهما إما متداخلان داخليًا (إحدى الفترتين تحتوي الأخرى) أو منفصلان. تكون مجموعة من الأوتار قابلة للرسم فوق الخط دون تقاطعات تمامًا عندما لا يتقاطع أي وترين منها، لذا فإن عدد الوصل يساوي عدد المجموعات الجزئية الخالية من التقاطع، بما في ذلك المجموعة الجزئية الفارغة. وبلغة المخططات (الغراف)، نبني غراف التقاطع الذي تكون رؤوسه هي الأوتار وحوافه تربط بين الأزواج المتقاطعة؛ وعدد الوصل هو عدد المجموعات المستقلة في ذلك الغراف.
أي مجموعة من الأوتار غير المتقاطعة بشكل ثنائي تكون عائلة صفائحية: أي عضوين منها إما متداخلان داخليًا أو منفصلان، ولا يتداخلان تشابكيًا أبدًا. والعائلات الصفائحية هي بالضبط غابات ترتيب الاحتواء، وهذا التركيب التداخلي — الغائب في الغراف العام — هو ما يحوّل العدّ إلى برمجة ديناميكية بزمن متعدد الحدود بدلًا من عدّ مجموعات مستقلة عسير الحل.
لا تبني الطريقة السريعة مخطط التقاطعات كاملاً بصورة صريحة. فالوتر الذي يفتح داخل \([\ell_i,r_i]\) ويغلق بعد \(r_i\) يتقاطع مع الوتر \(i\)، ولذلك لا يمكن أن يظهر في مجموعة جزئية تحتوي أيضاً على \(i\). عند لحظة إغلاق الوتر \(i\)، تكون كل الأوتار المتداخلة بالكامل داخله قد أغلقت، بينما تبقى كل الأوتار التي تتقاطع معه مفتوحة. لذلك فإن القيمة المتراكمة عند الخانة \(i+1\) تعد بالضبط الاختيارات الداخلية المسموحة التي يمكن ضمها إلى الوتر \(i\).
رتّب الأوتار حسب الطرف الأيسر، \(\ell_0 \lt \ell_1 \lt \dots \lt \ell_{n-1}\) (جميع الأطراف متمايزة)، واكتب \(r_i\) للطرف الأيمن للوتر \(i\). لكل وتر عرّف
$$\operatorname{next}(i)=\min\{\,j : \ell_j \gt r_i\,\},$$
وهو أول وتر يقع بالكامل إلى يمين الوتر \(i\). الأوتار التي تقع فهارسها في \((i,\operatorname{next}(i))\) هي بالضبط تلك التي تُفتح داخل الوتر \(i\)؛ ومن بينها يُغلق المتداخلون داخليًا قبل \(r_i\) بينما يُغلق المتقاطعون بعد \(r_i\).
تعالج الخوارزمية الأوتار بترتيب تصاعدي للطرف الأيمن وتحتفظ بمصفوفة \(\textit{ways}\) (مهيأة بالكامل إلى آحاد) إلى جانب مصفوفة مرافقة \(\textit{delta}\). عندما يُغلق الوتر \(i\)، يكون كل وتر متداخل داخله قد أُغلق بالفعل، لذا فإن القيمة
$$\textit{inside}(i)=\textit{ways}[i+1]$$
هي عدد المجموعات الجزئية غير المتقاطعة التي تقع تمامًا داخل الوتر \(i\). أما المجموعات الجزئية التي تتضمن الوتر \(i\) فيُحصل عليها بالدمج الحر بين أحد هذه التهيئات الداخلية مع أي تهيئة غير متقاطعة مأخوذة من الأوتار الواقعة بالكامل إلى يمينه:
$$\textit{inc}=\textit{inside}(i)\cdot \textit{ways}[\operatorname{next}(i)].$$
تُسجَّل هذه الزيادة في \(\textit{delta}[i]\) وتُضاف إلى \(\textit{ways}[i]\). كما يجب أن تصل إلى كل وتر سابق \(p \lt i\) لا يزال مفتوحًا وقد مُرّ بمنطقته المتداخلة بالفعل (\(\operatorname{next}(p)\le i\)): فبالنسبة لمثل هذا \(p\)، يوسّع الوتر \(i\) المغلق حديثًا المجموعات الجزئية التي تتضمن \(p\) عبر الحد \(\textit{inside}(p)\cdot \textit{delta}[\operatorname{next}(p)]\). يستغرق نشر هذه المساهمة نزولًا إلى جميع الخانات السابقة عملًا بمقدار \(O(n)\) لكل وتر يُغلق، وبعد أن يُغلق الوتر الأخير يكون الإجمالي المتراكم هو
$$\text{connectivity number}=\textit{ways}[0]\bmod M.$$
وهكذا فإن مدخلتي المصفوفة \(\textit{ways}[i]\) و\(\textit{delta}[i]\) تُرمّزان، على التوالي، العدّ الجاري للمجموعات الجزئية الصالحة المرتكزة عند الخانة \(i\) وأحدث زيادة يُراد تمريرها — وهي مسك الدفاتر الذي يتيح لمسحة خطية واحدة لكل وتر أن تأخذ في الحسبان كلًّا من خياري "متداخل داخليًا" و"يستمر إلى اليمين".
ways وdeltaيمكن النظر إلى الخانة \(s\) كحد يقع مباشرة قبل الوتر \(s\) في ترتيب الأطراف اليسرى. بعد كل حدث إغلاق تحتوي \(\textit{ways}[s]\) على كل الاختيارات الصالحة التي يكون طرفها الأيسر التالي عند الخانة \(s\) أو بعدها، مع الاقتصار على الأوتار التي أغلقها المسح حتى الآن. أما \(\textit{delta}[s]\) فتخزن فقط أحدث مساهمة ما زالت تحتاج إلى تمريرها إلى الأسلاف المفتوحين السابقين. هذا الفصل يمنع العد المكرر: المساهمات القديمة امتصتها \(\textit{ways}\) بالفعل، والحلقة على \(p=i-1,\dots,0\) تمرر فقط حد \(\textit{delta}\) الجديد الذي أنشأه الوتر المغلق لتوه.
القيمة \(0\) تقع في الموضعين \(0,2\) والقيمة \(1\) في الموضعين \(1,3\)، مما يعطي الوترين \([0,2]\) و\([1,3]\). وبما أن \(0 \lt 1 \lt 2 \lt 3\) فإنهما يتداخلان، إذن يتقاطعان. ولذلك تكون المجموعات الجزئية الخالية من التقاطع هي \(\varnothing\) و\(\{[0,2]\}\) و\(\{[1,3]\}\) — مع استبعاد الزوج الكامل — بعدد وصل يساوي \(3\)، وهو ما يطابق القيمة المذكورة.
تتشارك التنفيذات بلغات C++ وPython وJava نفس خط المعالجة. يقرأ load_csv المصفوفة المفصولة بفواصل. ويسجّل build_intervals موضعي كل قيمة، ويشكّل الأوتار \([p,q]\)، ويرتّبها حسب الطرف الأيسر، ويتحقق بشكل تأكيدي من أن الأطراف اليسرى متزايدة تمامًا.
يبني connectivity_number الدالة \(\operatorname{next}(i)\) بواسطة بحث ثنائي (upper_bound على الأطراف اليسرى المرتبة)، ويرتّب الأوتار حسب الطرف الأيمن، ويشغّل المسحة المذكورة أعلاه باستخدام المصفوفات \(\textit{ways}\) و\(\textit{delta}\) و\(\textit{inside}\) و\(\textit{active}\)، مع إجراء جميع العمليات الحسابية بمقياس \(M\) عبر add_mod وmul_mod (الأخيرة تتوسّع إلى \(128\) بتًا في C++؛ بينما يكفي \(64\) بتًا أصلًا في Java وPython لأن العوامل أصغر من \(M\)).
تشكّل crosses وbrute_connectivity مسار التحقق: فالأخيرة تعدّد ببساطة جميع المجموعات الجزئية \(2^n\) وتحصي تلك الخالية من أي زوج متقاطع. ويتحقق run_checkpoints من القيم المنشورة \(3,8,5,8,86\) على خمس مصفوفات صغيرة ويؤكد أن النتيجة السريعة تساوي عدّ القوة الغاشمة مُختزلًا بمقياس \(M\)؛ ثم يقيّم main بعد ذلك الحالة المكونة من \(40\,000\) عنصر.
يكلّف بناء الأوتار \(O(n)\) إضافةً إلى \(O(n\log n)\) للترتيبين والبحثين الثنائيين. تجري مسحة الإغلاق نشرًا بمقدار \(O(n)\) لكل وتر من الأوتار \(n\)، لذا فإن الكلفة المهيمنة هي
$$O(n^2)$$
من حيث الزمن مع ذاكرة بمقدار \(O(n)\). بالنسبة إلى \(n=20\,000\) فإن هذا يمثّل بضع مئات من ملايين العمليات الموديولية ذات الزمن الثابت، وهو سريع بشكل مريح في C++. أما مدقّق القوة الغاشمة فهو أُسّي، \(O(2^n\cdot n^2)\)، ويقتصر على مصفوفات نقاط التحقق الصغيرة فقط.