For each \(n\), place the vertices of a regular \(n\)-gon on a circle and draw polygon edges as straight chords. The quantity \(T(n)\) is obtained by looking at every interior point where diagonals meet, counting how many undirected Hamiltonian cycles on the same \(n\) vertices use at least two diagonals through that point, and then summing those contributions over all such points.
The overall task is to evaluate
$$\sum_{n=3}^{60} T(n)\pmod{10^9+7}.$$
The key observation is that the computation separates cleanly into a geometric part, which classifies intersection points by how many diagonals pass through them, and a combinatorial part, which counts cycles containing selected diagonals.
Write \(M=10^9+7\). For a fixed \(n\), let \(P_n(r)\) denote the number of interior intersection points through which exactly \(r\) diagonals of the regular \(n\)-gon pass. The whole problem reduces to computing \(P_n(r)\) and then weighting each class by the number of Hamiltonian cycles that use at least two of those \(r\) diagonals.
Take indices \(a<b<c<d\). In a convex \(n\)-gon, the diagonals joining \(a\) to \(c\) and \(b\) to \(d\) cross at exactly one interior point. So every ordered quadruple \(a<b<c<d\) contributes one diagonal-intersection event.
If a point \(P\) is the common intersection of exactly \(r\) diagonals, then every pair of those diagonals determines one quadruple, and every such quadruple leads back to the same point. Therefore the number of quadruples producing \(P\) is
$$q=\binom{r}{2}.$$
This means that once equal geometric intersections have been grouped together, the concurrency \(r\) is recovered from the bucket size \(q\) by
$$r=\frac{1+\sqrt{1+8q}}{2}.$$
So the geometric layer does not need any deeper polygon theory: it is enough to enumerate all quadruples, group identical intersection coordinates, and convert each bucket size into a concurrency class \(r\).
Now fix one interior point \(P\) with concurrency \(r\). Any diagonals passing through the same interior point are pairwise disjoint as edges of the polygon: if two of them shared a vertex, they would meet on the boundary instead of in the interior.
For \(t\in\{0,1,\dots,r\}\), let \(A_n(t)\) be the number of undirected Hamiltonian cycles on the \(n\) labeled vertices that contain some fixed set of \(t\) diagonals through \(P\).
When \(t=0\), this is simply the number of Hamiltonian cycles in the complete graph on \(n\) labeled vertices:
$$A_n(0)=\frac{(n-1)!}{2}.$$
When \(t\ge 1\), contract each forced diagonal into a single block. Since the chosen diagonals are disjoint, this reduces the \(n\) vertices to \(n-t\) units. An undirected cyclic ordering of those units contributes
$$\frac{(n-t-1)!}{2}$$
possibilities, and each contracted diagonal can be traversed in two directions. Hence
$$A_n(t)=2^t\cdot \frac{(n-t-1)!}{2}=(n-t-1)!\,2^{t-1}\qquad (t\ge 1).$$
This is exactly the counting rule used by the implementations.
For a point with \(r\) available diagonals, let \(B_n(r)\) be the number of Hamiltonian cycles that use none of them. Standard inclusion-exclusion over the \(r\) forbidden diagonals gives
$$B_n(r)=\sum_{t=0}^{r}(-1)^t\binom{r}{t}A_n(t).$$
Next let \(C_n(r)\) be the number of Hamiltonian cycles that use exactly one of those \(r\) diagonals. Choose which diagonal is used, then exclude the remaining \(r-1\) diagonals by another inclusion-exclusion step:
$$C_n(r)=r\sum_{t=0}^{r-1}(-1)^t\binom{r-1}{t}A_n(t+1).$$
If \(D_n(r)\) denotes the number of Hamiltonian cycles that use at least two diagonals through the point, then
$$D_n(r)=A_n(0)-B_n(r)-C_n(r).$$
This formula is the combinatorial core of the solution.
Once the regular \(n\)-gon has been partitioned into concurrency classes, the total contribution for that \(n\) is
$$T(n)=\sum_{r\ge 2} P_n(r)\,D_n(r)\pmod{M}.$$
The lower bound \(r\ge 2\) is natural: an interior crossing point only matters when at least two diagonals pass through it. Each class contributes independently, so the program can first discover the multiplicities \(P_n(r)\) and then apply the same combinatorial formula to every observed \(r\).
In a regular pentagon there are five interior diagonal intersections, and each one is formed by exactly two diagonals. Therefore
$$P_5(2)=5.$$
The unrestricted number of undirected Hamiltonian cycles is
$$A_5(0)=\frac{4!}{2}=12.$$
For one fixed diagonal through a chosen intersection point,
$$A_5(1)=(5-2)!\,2^0=6,$$
and for both diagonals through that point,
$$A_5(2)=(5-3)!\,2^1=4.$$
So
$$B_5(2)=A_5(0)-2A_5(1)+A_5(2)=12-12+4=4,$$
$$C_5(2)=2\bigl(A_5(1)-A_5(2)\bigr)=2(6-4)=4,$$
and therefore
$$D_5(2)=12-4-4=4.$$
Multiplying by the five intersection points gives
$$T(5)=P_5(2)D_5(2)=5\cdot 4=20,$$
which matches the small check embedded in the solver.
The C++ implementation precomputes factorials, inverse factorials, and powers of \(2\) modulo \(10^9+7\) up to \(60\). That makes binomial coefficients and the values \(A_n(t)\) constant-time operations during the main loop.
For each \(n\), it places the vertices on the unit circle using high-precision trigonometric values, enumerates every quadruple \(a<b<c<d\), and computes the intersection of diagonals \(ac\) and \(bd\). Each intersection coordinate is scaled and rounded to a stable integer key so that coincident points fall into the same bucket.
After that grouping step, each bucket size \(q\) is converted to a concurrency value \(r\) through the triangular-number identity \(q=\binom{r}{2}\). The implementation then evaluates the inclusion-exclusion formulas above to obtain \(D_n(r)\), multiplies by the number of points in that class, and accumulates \(T(n)\) modulo \(10^9+7\).
The C++ implementation performs the full numeric computation directly. The Python and Java implementations delegate to that same compiled computation and only parse the final printed result.
For a fixed \(n\), the geometric stage examines every quadruple of vertices, so its running time is \(O(n^4)\). The intersection-grouping table stores one entry per distinct interior point, so the memory usage is \(O(U_n)\), where \(U_n\le \binom{n}{4}\).
The combinatorial stage is much smaller. The modular precomputation is \(O(n)\), and evaluating the inclusion-exclusion sums over the possible concurrency classes is at worst \(O(n^2)\) for one value of \(n\). Therefore the geometric enumeration dominates the total cost.
Across the full range \(3\le n\le 60\), the runtime is dominated by
$$\sum_{n=3}^{60} O(n^4),$$
which is entirely practical for this fixed bound.
Für jedes \(n\) werden die Ecken eines regelmäßigen \(n\)-Ecks auf einen Kreis gelegt und alle Polygonkanten als gerade Sehnen gezeichnet. Die Größe \(T(n)\) entsteht, indem man für jeden inneren Punkt, in dem sich Diagonalen schneiden, zählt, wie viele ungerichtete Hamiltonkreise auf denselben \(n\) Ecken mindestens zwei der durch diesen Punkt laufenden Diagonalen benutzen, und diese Beiträge dann über alle solchen Punkte aufsummiert.
Gesucht ist also
$$\sum_{n=3}^{60} T(n)\pmod{10^9+7}.$$
Die Lösung zerlegt das Problem in zwei saubere Teile: zuerst die Geometrie der Schnittpunkte und danach die kombinatorische Zählung der Kreise mit vorgegebenen Diagonalen.
Schreibe \(M=10^9+7\). Für festes \(n\) bezeichne \(P_n(r)\) die Anzahl innerer Schnittpunkte, durch die genau \(r\) Diagonalen des regelmäßigen \(n\)-Ecks verlaufen. Dann genügt es, für jede solche Klasse zu bestimmen, wie viele Hamiltonkreise mindestens zwei dieser \(r\) Diagonalen enthalten.
Wähle Indizes \(a<b<c<d\). In einem konvexen \(n\)-Eck schneiden sich die Diagonalen \(ac\) und \(bd\) dann in genau einem inneren Punkt. Jede geordnete Vierergruppe \(a<b<c<d\) liefert also genau ein Schnitt-Ereignis.
Schneiden sich in einem Punkt \(P\) genau \(r\) Diagonalen, dann bestimmt jedes Paar dieser Diagonalen genau eine Vierergruppe, und umgekehrt führt jede dieser Vierergruppen wieder zu \(P\). Die Anzahl der erzeugenden Vierergruppen ist daher
$$q=\binom{r}{2}.$$
Nach dem Gruppieren identischer Schnittpunkte kann man \(r\) also direkt aus der Bucket-Größe \(q\) zurückgewinnen:
$$r=\frac{1+\sqrt{1+8q}}{2}.$$
Mehr Geometrie braucht die Lösung nicht. Es reicht, alle Vierergruppen zu enumerieren, gleiche Schnittkoordinaten zusammenzufassen und aus der Häufigkeit die Vielfachheit \(r\) zu berechnen.
Fixiere nun einen inneren Schnittpunkt \(P\) mit Vielfachheit \(r\). Alle Diagonalen durch denselben inneren Punkt sind als Kanten paarweise disjunkt: würden zwei von ihnen einen Eckpunkt teilen, dann träfen sie sich am Rand und nicht im Inneren.
Für \(t\in\{0,1,\dots,r\}\) sei \(A_n(t)\) die Anzahl ungerichteter Hamiltonkreise auf den \(n\) markierten Ecken, die eine fest gewählte Menge von \(t\) Diagonalen durch \(P\) enthalten.
Für \(t=0\) ist das einfach die Gesamtzahl der Hamiltonkreise auf \(n\) markierten Ecken:
$$A_n(0)=\frac{(n-1)!}{2}.$$
Für \(t\ge 1\) kontrahiert man jede erzwungene Diagonale zu einem Block. Da die gewählten Diagonalen disjunkt sind, bleiben \(n-t\) Einheiten übrig. Deren ungerichtete zyklische Anordnung liefert
$$\frac{(n-t-1)!}{2}$$
Möglichkeiten, und jeder kontrahierte Block kann in zwei Richtungen durchlaufen werden. Also gilt
$$A_n(t)=2^t\cdot \frac{(n-t-1)!}{2}=(n-t-1)!\,2^{t-1}\qquad (t\ge 1).$$
Genau diese Formel steckt in den Implementierungen.
Für einen Punkt mit \(r\) verfügbaren Diagonalen sei \(B_n(r)\) die Anzahl der Hamiltonkreise, die keine von ihnen benutzen. Standard-Inklusion-Exklusion über die \(r\) verbotenen Diagonalen liefert
$$B_n(r)=\sum_{t=0}^{r}(-1)^t\binom{r}{t}A_n(t).$$
Weiter sei \(C_n(r)\) die Anzahl der Hamiltonkreise, die genau eine dieser \(r\) Diagonalen benutzen. Man wählt zuerst die verwendete Diagonale aus und schließt die restlichen \(r-1\) Diagonalen wieder per Inklusion-Exklusion aus:
$$C_n(r)=r\sum_{t=0}^{r-1}(-1)^t\binom{r-1}{t}A_n(t+1).$$
Wenn \(D_n(r)\) die Anzahl der Hamiltonkreise bezeichnet, die mindestens zwei Diagonalen durch den Punkt enthalten, dann ist
$$D_n(r)=A_n(0)-B_n(r)-C_n(r).$$
Das ist der kombinatorische Kern der gesamten Methode.
Sobald alle Schnittpunkte des regelmäßigen \(n\)-Ecks nach ihrer Vielfachheit sortiert sind, ergibt sich
$$T(n)=\sum_{r\ge 2} P_n(r)\,D_n(r)\pmod{M}.$$
Die untere Grenze \(r\ge 2\) ist selbstverständlich, denn ein relevanter innerer Schnittpunkt muss von mindestens zwei Diagonalen erzeugt werden. Jede Vielfachheitsklasse trägt unabhängig bei, deshalb kann man zuerst \(P_n(r)\) bestimmen und danach dieselbe kombinatorische Formel für jede beobachtete Klasse anwenden.
Im regelmäßigen Fünfeck gibt es fünf innere Diagonalenschnittpunkte, und jeder davon wird von genau zwei Diagonalen erzeugt. Also
$$P_5(2)=5.$$
Die Gesamtzahl der ungerichteten Hamiltonkreise ist
$$A_5(0)=\frac{4!}{2}=12.$$
Für eine fest gewählte Diagonale durch einen gegebenen Schnittpunkt gilt
$$A_5(1)=(5-2)!\,2^0=6,$$
und für beide Diagonalen durch diesen Punkt
$$A_5(2)=(5-3)!\,2^1=4.$$
Damit folgt
$$B_5(2)=A_5(0)-2A_5(1)+A_5(2)=12-12+4=4,$$
$$C_5(2)=2\bigl(A_5(1)-A_5(2)\bigr)=2(6-4)=4,$$
und somit
$$D_5(2)=12-4-4=4.$$
Multipliziert mit den fünf Schnittpunkten ergibt das
$$T(5)=P_5(2)D_5(2)=5\cdot 4=20,$$
genau den kleinen Kontrollwert des Solvers.
Die C++-Implementierung berechnet Fakultäten, inverse Fakultäten und Zweierpotenzen modulo \(10^9+7\) bis \(60\) vor. Dadurch werden Binomialkoeffizienten und die Werte \(A_n(t)\) im Hauptteil zu Konstantzeit-Operationen.
Für jedes \(n\) werden die Ecken des regelmäßigen \(n\)-Ecks mit hochpräziser Trigonometrie auf dem Einheitskreis erzeugt. Danach enumeriert die Implementierung alle Vierergruppen \(a<b<c<d\), berechnet den Schnittpunkt der Diagonalen \(ac\) und \(bd\) und skaliert beziehungsweise rundet die Koordinaten zu einem stabilen ganzzahligen Schlüssel, damit gleiche Punkte sicher zusammenfallen.
Aus jeder Bucket-Größe \(q\) wird dann über die Dreieckszahl-Identität \(q=\binom{r}{2}\) die Vielfachheit \(r\) rekonstruiert. Anschließend wertet die Implementierung die obigen Inklusions-Exklusions-Formeln für \(D_n(r)\) aus, multipliziert mit der Anzahl der Punkte dieser Klasse und akkumuliert \(T(n)\) modulo \(10^9+7\).
Die C++-Implementierung erledigt die gesamte numerische Arbeit direkt. Die Python- und Java-Implementierungen delegieren an dieselbe kompilierte Rechnung und lesen nur den am Ende ausgegebenen Wert aus.
Für festes \(n\) untersucht der geometrische Teil alle Vierergruppen von Ecken und benötigt daher \(O(n^4)\) Zeit. Die Tabelle der Schnittpunkte speichert einen Eintrag pro verschiedenem inneren Punkt, also \(O(U_n)\) Speicher mit \(U_n\le \binom{n}{4}\).
Der kombinatorische Teil ist deutlich kleiner. Die modulare Vorberechnung kostet \(O(n)\), und die Auswertung der Inklusions-Exklusions-Summen über alle möglichen Vielfachheiten ist für ein festes \(n\) höchstens \(O(n^2)\). Damit dominiert klar die geometrische Enumeration.
Über den gesamten Bereich \(3\le n\le 60\) wird die Laufzeit also im Wesentlichen durch
$$\sum_{n=3}^{60} O(n^4)$$
bestimmt, was für diese feste Schranke problemlos praktikabel ist.
Her \(n\) için, düzgün \(n\)-genin köşeleri bir çember üzerine yerleştirilir ve tüm kenarlar doğru parçası olarak çizilir. \(T(n)\) değeri, içeride köşegenlerin kesiştiği her nokta için, aynı \(n\) köşe üzerinde tanımlı yönsüz Hamilton çevrimlerinden kaç tanesinin o noktadan geçen köşegenlerden en az ikisini kullandığını sayıp bu katkıları toplamaktan oluşur.
Dolayısıyla hedef
$$\sum_{n=3}^{60} T(n)\pmod{10^9+7}$$
ifadesini hesaplamaktır. Çözüm, problemi temiz biçimde iki katmana ayırır: önce kesişim noktalarının geometrik çoklukları bulunur, sonra seçilmiş köşegenleri içeren çevrimler kombinatorik olarak sayılır.
\(M=10^9+7\) olsun. Sabit bir \(n\) için, düzgün \(n\)-gende tam olarak \(r\) köşegenin geçtiği iç kesişim noktalarının sayısını \(P_n(r)\) ile gösterelim. O zaman yapılması gereken, her \(r\) sınıfı için bu \(r\) köşegenden en az ikisini kullanan Hamilton çevrimlerinin sayısını hesaplamaktır.
\(a<b<c<d\) olacak şekilde dört köşe seçelim. Dışbükey bir \(n\)-gende \(ac\) ve \(bd\) köşegenleri tam bir iç noktada kesişir. Bu yüzden her sıralı dörtlü \(a<b<c<d\) tam bir köşegen-kesişim olayı üretir.
Eğer bir \(P\) noktası tam olarak \(r\) köşegenin ortak kesişimiyse, bu \(r\) köşegenin her ikilisi bir dörtlü belirler ve her böyle dörtlü yine aynı noktaya geri döner. Bu nedenle o noktayı üreten dörtlü sayısı
$$q=\binom{r}{2}$$
olur. Böylece aynı geometrik kesişimleri gruplayınca, eşzamanlı geçen köşegen sayısı \(r\) doğrudan
$$r=\frac{1+\sqrt{1+8q}}{2}$$
formülüyle geri kazanılır. Yani geometri tarafında gereken şey, tüm dörtlüleri gezmek, aynı koordinatları bir araya toplamak ve grup büyüklüğünden çokluğu çıkarmaktır.
Şimdi çokluğu \(r\) olan sabit bir iç nokta \(P\) seçelim. Aynı iç noktadan geçen köşegenler, çokgen kenarı olarak düşünüldüğünde ikişer ikişer ayrık olmalıdır; aksi halde ortak bir köşe paylaşırlar ve kesişme içeride değil sınırda gerçekleşirdi.
\(t\in\{0,1,\dots,r\}\) için, \(P\) noktasından geçen sabit seçilmiş \(t\) köşegeni içeren yönsüz Hamilton çevrimlerinin sayısını \(A_n(t)\) ile gösterelim.
\(t=0\) iken bu, \(n\) etiketli köşe üzerindeki toplam Hamilton çevrimi sayısıdır:
$$A_n(0)=\frac{(n-1)!}{2}.$$
\(t\ge 1\) olduğunda, zorunlu her köşegen tek bir blok gibi daraltılabilir. Seçilen köşegenler ayrık olduğu için \(n\) köşe \(n-t\) birime iner. Bu birimlerin yönsüz çevrimsel sıralanışı
$$\frac{(n-t-1)!}{2}$$
adet olasılık verir. Her blok iki yönde de geçilebilir olduğundan ek olarak \(2^t\) katsayısı gelir. Sonuç:
$$A_n(t)=2^t\cdot \frac{(n-t-1)!}{2}=(n-t-1)!\,2^{t-1}\qquad (t\ge 1).$$
Uygulamanın kullandığı temel sayım kuralı tam olarak budur.
\(r\) uygun köşegenli bir nokta için, bunların hiçbirini kullanmayan Hamilton çevrimlerinin sayısı \(B_n(r)\) olsun. \(r\) yasak köşegen üzerinde standart dahil et-çıkar uygulanırsa
$$B_n(r)=\sum_{t=0}^{r}(-1)^t\binom{r}{t}A_n(t)$$
elde edilir.
Ayrıca tam bir tanesini kullanan çevrimlerin sayısı \(C_n(r)\) olsun. Önce kullanılan köşegen seçilir, sonra kalan \(r-1\) köşegen yine dahil et-çıkar ile dışlanır:
$$C_n(r)=r\sum_{t=0}^{r-1}(-1)^t\binom{r-1}{t}A_n(t+1).$$
Eğer \(D_n(r)\), o noktadan geçen köşegenlerden en az ikisini kullanan Hamilton çevrimlerinin sayısıysa, o zaman
$$D_n(r)=A_n(0)-B_n(r)-C_n(r)$$
olur. Çözümün asıl kombinatorik omurgası budur.
Düzgün \(n\)-genin bütün iç kesişim noktaları çokluklarına göre ayrıldıktan sonra toplam katkı
$$T(n)=\sum_{r\ge 2} P_n(r)\,D_n(r)\pmod{M}$$
şeklindedir. Alt sınırın \(r\ge 2\) olması doğaldır; ilgilendiğimiz bir iç kesişim noktasında en az iki köşegen bulunmalıdır. Her çokluk sınıfı bağımsız katkı yaptığı için önce \(P_n(r)\) bulunur, sonra aynı formül her sınıfa uygulanır.
Düzgün beşgende beş tane iç köşegen kesişimi vardır ve bunların her biri tam iki köşegenden oluşur. Dolayısıyla
$$P_5(2)=5.$$
Serbest yönsüz Hamilton çevrimi sayısı
$$A_5(0)=\frac{4!}{2}=12$$
olur. Verilen kesişim noktasından geçen sabit bir köşegen için
$$A_5(1)=(5-2)!\,2^0=6,$$
aynı noktadaki iki köşegenin ikisi birden zorlandığında ise
$$A_5(2)=(5-3)!\,2^1=4.$$
Böylece
$$B_5(2)=A_5(0)-2A_5(1)+A_5(2)=12-12+4=4,$$
$$C_5(2)=2\bigl(A_5(1)-A_5(2)\bigr)=2(6-4)=4,$$
ve sonuç olarak
$$D_5(2)=12-4-4=4.$$
Beş kesişim noktasıyla çarpınca
$$T(5)=P_5(2)D_5(2)=5\cdot 4=20$$
elde edilir. Bu, çözücünün kullandığı küçük doğrulama değeriyle aynıdır.
C++ uygulaması önce \(60\)'a kadar faktöriyelleri, ters faktöriyelleri ve \(2\) kuvvetlerini \(10^9+7\) modunda önceden hesaplar. Böylece binom katsayıları ve \(A_n(t)\) değerleri ana döngü içinde sabit zamanda elde edilir.
Her \(n\) için köşeler birim çember üzerinde yüksek hassasiyetli trigonometrik değerlerle üretilir. Ardından tüm \(a<b<c<d\) dörtlüleri gezilir, \(ac\) ile \(bd\) köşegenlerinin kesişimi hesaplanır ve koordinatlar ölçeklenip yuvarlanarak kararlı bir tamsayı anahtara dönüştürülür. Bu sayede çakışan noktalar aynı grupta toplanır.
Her grubun boyutu \(q\) için, üçgensel sayı bağıntısı \(q=\binom{r}{2}\) kullanılarak çokluk \(r\) bulunur. Sonra dahil et-çıkar formülleri değerlendirilerek \(D_n(r)\) hesaplanır, sınıftaki nokta sayısıyla çarpılır ve \(T(n)\) değeri \(10^9+7\) modunda toplanır.
C++ uygulaması sayısal işi doğrudan yapar. Python ve Java uygulamaları ise aynı derlenmiş hesabı çağırıp yalnızca en sonda yazdırılan sonucu ayrıştırır.
Sabit bir \(n\) için geometrik bölüm bütün köşe dörtlülerini incelediği için zaman maliyeti \(O(n^4)\)'tür. Kesişim gruplama tablosu, farklı her iç nokta için bir kayıt tutar; dolayısıyla bellek kullanımı \(U_n\le \binom{n}{4}\) olmak üzere \(O(U_n)\) olur.
Kombinatorik bölüm çok daha küçüktür. Modüler önhesap \(O(n)\) sürer, olası çokluklar üzerindeki dahil et-çıkar toplamları ise tek bir \(n\) için en kötü durumda \(O(n^2)\) olur. Bu nedenle toplam maliyeti belirleyen kısım açık biçimde geometrik enumerasyondur.
\(3\le n\le 60\) aralığının tamamında çalışma süresi esas olarak
$$\sum_{n=3}^{60} O(n^4)$$
terimiyle belirlenir ve bu sabit üst sınır için rahatlıkla uygulanabilir düzeydedir.
Para cada \(n\), se colocan los vértices de un \(n\)-gono regular sobre una circunferencia y todas las aristas del polígono se dibujan como cuerdas rectas. La cantidad \(T(n)\) se obtiene recorriendo cada punto interior donde se cruzan diagonales, contando cuántos ciclos hamiltonianos no dirigidos sobre esos mismos \(n\) vértices usan al menos dos de las diagonales que pasan por ese punto, y sumando después todas esas contribuciones.
El objetivo total es calcular
$$\sum_{n=3}^{60} T(n)\pmod{10^9+7}.$$
La solución separa el trabajo en dos capas independientes: una geométrica, que clasifica los puntos de intersección por su multiplicidad, y otra combinatoria, que cuenta ciclos que contienen diagonales prescritas.
Escribamos \(M=10^9+7\). Para un \(n\) fijo, sea \(P_n(r)\) el número de puntos de intersección interiores por los que pasan exactamente \(r\) diagonales del \(n\)-gono regular. Entonces basta con averiguar, para cada clase \(r\), cuántos ciclos hamiltonianos contienen al menos dos de esas \(r\) diagonales.
Tomemos índices \(a<b<c<d\). En un \(n\)-gono convexo, las diagonales \(ac\) y \(bd\) se cortan en un único punto interior. Por tanto, cada cuádrupla ordenada \(a<b<c<d\) aporta exactamente un evento de intersección.
Si un punto \(P\) es la intersección común de exactamente \(r\) diagonales, cada par de esas diagonales determina una cuádrupla, y cada una de esas cuádruplas vuelve a producir el mismo punto. En consecuencia, el número de cuádruplas que generan \(P\) es
$$q=\binom{r}{2}.$$
Así, después de agrupar las intersecciones geométricamente idénticas, la concurrencia \(r\) se recupera a partir del tamaño del grupo \(q\) mediante
$$r=\frac{1+\sqrt{1+8q}}{2}.$$
La capa geométrica no necesita nada más sofisticado: basta con enumerar todas las cuádruplas, agrupar coordenadas iguales y convertir el tamaño de cada grupo en su clase de multiplicidad.
Fijemos ahora un punto interior \(P\) de concurrencia \(r\). Las diagonales que pasan por un mismo punto interior son disjuntas dos a dos como aristas del polígono; si compartieran un vértice, se encontrarían en la frontera y no en el interior.
Para \(t\in\{0,1,\dots,r\}\), definamos \(A_n(t)\) como el número de ciclos hamiltonianos no dirigidos sobre los \(n\) vértices etiquetados que contienen un conjunto fijo de \(t\) diagonales que pasan por \(P\).
Cuando \(t=0\), esto no es más que el número total de ciclos hamiltonianos sobre \(n\) vértices etiquetados:
$$A_n(0)=\frac{(n-1)!}{2}.$$
Cuando \(t\ge 1\), se contrae cada diagonal forzada en un bloque. Como las diagonales elegidas son disjuntas, los \(n\) vértices se reducen a \(n-t\) unidades. El número de ordenaciones cíclicas no dirigidas de esas unidades es
$$\frac{(n-t-1)!}{2},$$
y cada bloque puede recorrerse en dos sentidos. Por tanto,
$$A_n(t)=2^t\cdot \frac{(n-t-1)!}{2}=(n-t-1)!\,2^{t-1}\qquad (t\ge 1).$$
Ésta es exactamente la regla de conteo implementada en el programa.
Para un punto con \(r\) diagonales disponibles, sea \(B_n(r)\) el número de ciclos hamiltonianos que no usan ninguna de ellas. Aplicando inclusión-exclusión estándar sobre las \(r\) diagonales prohibidas, se obtiene
$$B_n(r)=\sum_{t=0}^{r}(-1)^t\binom{r}{t}A_n(t).$$
Sea ahora \(C_n(r)\) el número de ciclos hamiltonianos que usan exactamente una de esas \(r\) diagonales. Se elige primero cuál aparece y luego se excluyen las otras \(r-1\) con otra inclusión-exclusión:
$$C_n(r)=r\sum_{t=0}^{r-1}(-1)^t\binom{r-1}{t}A_n(t+1).$$
Si \(D_n(r)\) es el número de ciclos que usan al menos dos diagonales que pasan por el punto, entonces
$$D_n(r)=A_n(0)-B_n(r)-C_n(r).$$
Ése es el núcleo combinatorio de toda la solución.
Una vez clasificadas todas las intersecciones interiores del \(n\)-gono regular, la contribución total es
$$T(n)=\sum_{r\ge 2} P_n(r)\,D_n(r)\pmod{M}.$$
La cota inferior \(r\ge 2\) es natural: un punto interior relevante sólo existe cuando pasan por él al menos dos diagonales. Cada clase de multiplicidad contribuye de forma independiente, así que primero se hallan los valores \(P_n(r)\) y luego se aplica la misma fórmula combinatoria a cada clase observada.
En un pentágono regular hay cinco intersecciones interiores de diagonales, y cada una de ellas está formada por exactamente dos diagonales. Por lo tanto,
$$P_5(2)=5.$$
El número total de ciclos hamiltonianos no dirigidos es
$$A_5(0)=\frac{4!}{2}=12.$$
Para una diagonal fija que pasa por un punto de intersección dado,
$$A_5(1)=(5-2)!\,2^0=6,$$
y para las dos diagonales de ese punto,
$$A_5(2)=(5-3)!\,2^1=4.$$
Así,
$$B_5(2)=A_5(0)-2A_5(1)+A_5(2)=12-12+4=4,$$
$$C_5(2)=2\bigl(A_5(1)-A_5(2)\bigr)=2(6-4)=4,$$
y en consecuencia
$$D_5(2)=12-4-4=4.$$
Multiplicando por los cinco puntos de intersección se obtiene
$$T(5)=P_5(2)D_5(2)=5\cdot 4=20,$$
que coincide con la comprobación pequeña usada por el solucionador.
La implementación en C++ precalcula factoriales, factoriales inversos y potencias de \(2\) módulo \(10^9+7\) hasta \(60\). Con eso, los coeficientes binomiales y los valores \(A_n(t)\) se obtienen en tiempo constante durante el cálculo principal.
Para cada \(n\), coloca los vértices sobre la circunferencia unitaria usando trigonometría de alta precisión, enumera todas las cuádruplas \(a<b<c<d\) y calcula la intersección de las diagonales \(ac\) y \(bd\). Luego escala y redondea las coordenadas para formar una clave entera estable, de modo que los puntos coincidentes queden agrupados en la misma clase.
Después, a partir del tamaño de cada grupo \(q\), recupera la concurrencia \(r\) usando la identidad triangular \(q=\binom{r}{2}\). A continuación evalúa las fórmulas de inclusión-exclusión para obtener \(D_n(r)\), multiplica por el número de puntos de esa clase y acumula \(T(n)\) módulo \(10^9+7\).
La implementación en C++ realiza todo el trabajo numérico directamente. Las implementaciones en Python y Java delegan en ese mismo cálculo compilado y sólo extraen el resultado final impreso.
Para un \(n\) fijo, la etapa geométrica recorre todas las cuádruplas de vértices, así que su tiempo es \(O(n^4)\). La tabla de agrupación de intersecciones almacena una entrada por punto interior distinto, por lo que el uso de memoria es \(O(U_n)\), donde \(U_n\le \binom{n}{4}\).
La etapa combinatoria es mucho menor. La precomputación modular cuesta \(O(n)\), y evaluar las sumas de inclusión-exclusión sobre las posibles multiplicidades cuesta como mucho \(O(n^2)\) para un \(n\) dado. Por tanto, la enumeración geométrica domina claramente el coste total.
En todo el rango \(3\le n\le 60\), el tiempo queda dominado por
$$\sum_{n=3}^{60} O(n^4),$$
lo cual es completamente manejable para este límite fijo.
对每个 \(n\)，把正 \(n\) 边形的顶点放在同一个圆上，并把所有多边形边都当作直线弦来画。量 \(T(n)\) 的定义可以理解为：遍历所有由对角线形成的内部交点，对每个交点统计有多少个建立在同一组 \(n\) 个顶点上的无向哈密顿回路至少使用了经过该点的两条对角线，然后把这些贡献全部加起来。
整个题目的目标是计算
$$\sum_{n=3}^{60} T(n)\pmod{10^9+7}.$$
实现所利用的关键分解是：先做几何分类，判断每个交点有多少条对角线并发；再做组合计数，求包含指定若干条对角线的哈密顿回路有多少个。两部分独立完成后再相乘汇总。
记 \(M=10^9+7\)。对固定的 \(n\)，用 \(P_n(r)\) 表示正 \(n\) 边形内部那些恰好有 \(r\) 条对角线通过的交点个数。这样一来，问题就转化成：对每个可能的 \(r\)，求出经过该类交点的 \(r\) 条对角线中，至少选中两条时所能形成的无向哈密顿回路数。
取顶点指标 \(a<b<c<d\)。在凸正 \(n\) 边形中，连接 \(a\) 与 \(c\) 的对角线和连接 \(b\) 与 \(d\) 的对角线一定在内部恰好相交一次。因此，每一个按顺序排列的四元组 \(a<b<c<d\) 都对应一个内部对角线交点事件。
如果某个内部点 \(P\) 恰好是 \(r\) 条对角线的公共交点，那么这 \(r\) 条对角线任意选出两条，都会对应一个产生同一交点的四元组；反过来，每个这样的四元组又都来自这 \(r\) 条对角线中的一对。因此，落在 \(P\) 这个桶里的四元组数量满足
$$q=\binom{r}{2}.$$
这说明，只要先把几何上重合的交点合并，再查看某个桶出现了多少次，就可以通过
$$r=\frac{1+\sqrt{1+8q}}{2}$$
把该点的并发条数 \(r\) 直接恢复出来。也就是说，几何部分并不需要额外的深层定理，只需要枚举全部四元组、把相同交点归并，并把桶大小转换成并发数。
现在固定一个并发数为 \(r\) 的内部点 \(P\)。经过同一个内部点的这些对角线，作为多边形边来看是两两不共享端点的；如果两条线段共享端点，那么它们相遇的位置会落在边界顶点，而不是内部交点。
对 \(t\in\{0,1,\dots,r\}\)，定义 \(A_n(t)\) 为：在这 \(n\) 个带标号顶点上，包含某个固定的 \(t\) 条经过 \(P\) 的对角线集合的无向哈密顿回路数量。
当 \(t=0\) 时，这就是 \(n\) 个带标号顶点上全部无向哈密顿回路的数量：
$$A_n(0)=\frac{(n-1)!}{2}.$$
当 \(t\ge 1\) 时，可以把每一条被强制选入的对角线压缩成一个块。由于这些对角线彼此不相交且不共端点，压缩后总共有 \(n-t\) 个单位需要在一个环上排列。它们的无向循环排列数是
$$\frac{(n-t-1)!}{2},$$
而每个被压缩的块都可以用两种方向穿过，所以额外乘上 \(2^t\)。于是得到
$$A_n(t)=2^t\cdot \frac{(n-t-1)!}{2}=(n-t-1)!\,2^{t-1}\qquad (t\ge 1).$$
这正是程序在组合层里反复调用的计数公式。
对一个拥有 \(r\) 条候选对角线的交点，设 \(B_n(r)\) 为“不使用其中任何一条”的无向哈密顿回路数量。把这 \(r\) 条对角线都视为禁用边，对它们做标准容斥，可得
$$B_n(r)=\sum_{t=0}^{r}(-1)^t\binom{r}{t}A_n(t).$$
再设 \(C_n(r)\) 为“恰好使用其中一条”的回路数量。先选出那一条真正被使用的对角线，再对剩下的 \(r-1\) 条继续做容斥，就得到
$$C_n(r)=r\sum_{t=0}^{r-1}(-1)^t\binom{r-1}{t}A_n(t+1).$$
如果用 \(D_n(r)\) 表示“至少使用其中两条”的回路数量，那么它就是总数减去不用任何一条和恰好用一条的两部分：
$$D_n(r)=A_n(0)-B_n(r)-C_n(r).$$
这一步给出了整个算法最重要的组合骨架。
一旦把正 \(n\) 边形的所有内部交点按并发数分好类，总贡献就写成
$$T(n)=\sum_{r\ge 2} P_n(r)\,D_n(r)\pmod{M}.$$
这里从 \(r\ge 2\) 开始是自然的，因为一个有意义的内部交点至少要由两条对角线形成。每个并发类之间互不干扰，所以程序可以先完成几何统计 \(P_n(r)\)，再对每个出现过的 \(r\) 套用同一套容斥公式。
在正五边形中，内部一共有五个对角线交点，而且每个交点都恰好由两条对角线构成，所以
$$P_5(2)=5.$$
不加任何限制时，无向哈密顿回路总数为
$$A_5(0)=\frac{4!}{2}=12.$$
对某个固定交点来说，若只强制经过其中一条对角线，则
$$A_5(1)=(5-2)!\,2^0=6,$$
若强制经过该点的两条对角线，则
$$A_5(2)=(5-3)!\,2^1=4.$$
因此
$$B_5(2)=A_5(0)-2A_5(1)+A_5(2)=12-12+4=4,$$
$$C_5(2)=2\bigl(A_5(1)-A_5(2)\bigr)=2(6-4)=4,$$
于是
$$D_5(2)=12-4-4=4.$$
再乘上五个同类交点，就得到
$$T(5)=P_5(2)D_5(2)=5\cdot 4=20,$$
这与实现中使用的小规模校验完全一致。
C++ 实现先在模 \(10^9+7\) 下预计算到 \(60\) 为止的阶乘、逆阶乘和 \(2\) 的幂，因此二项式系数以及上面的 \(A_n(t)\) 都能在主循环里常数时间取得。
对每个 \(n\)，它会用高精度三角函数把顶点放到单位圆上，然后枚举所有 \(a<b<c<d\) 的四元组，计算对角线 \(ac\) 与 \(bd\) 的交点。交点坐标会先按一个大的固定尺度放大，再舍入成稳定的整数键，这样几何上重合的点就会落入同一个分组。
对每个分组，若它包含 \(q\) 次出现，就利用三角数关系 \(q=\binom{r}{2}\) 反推出该交点的并发数 \(r\)。随后程序代入上面的容斥公式求出 \(D_n(r)\)，再乘以这一类交点的数量并在模 \(10^9+7\) 下累加得到 \(T(n)\)。
C++ 实现直接完成全部数值计算。Python 和 Java 实现则调用同一份已编译的计算核心，只负责读取并解析最终输出的答案。
对固定的 \(n\)，几何阶段需要检查所有顶点四元组，因此时间复杂度是 \(O(n^4)\)。交点分组表为每个不同的内部交点保留一项，所以空间复杂度是 \(O(U_n)\)，其中 \(U_n\le \binom{n}{4}\)。
组合阶段要小得多。模运算预处理是 \(O(n)\)，而对可能的并发数逐类做容斥求和，对单个 \(n\) 来说最坏不超过 \(O(n^2)\)。因此整体瓶颈非常明显地落在几何枚举上。
在全部范围 \(3\le n\le 60\) 内，总运行时间主要由
$$\sum_{n=3}^{60} O(n^4)$$
控制。由于上界是固定的，这个成本在实践中完全可接受。
Для каждого \(n\) вершины правильного \(n\)-угольника располагаются на окружности, а все рёбра многоугольника проводятся как прямые хорды. Величина \(T(n)\) строится так: для каждой внутренней точки пересечения диагоналей нужно посчитать, сколько неориентированных гамильтоновых циклов на тех же \(n\) вершинах используют как минимум две диагонали, проходящие через эту точку, а затем просуммировать вклад по всем таким точкам.
Итоговая цель состоит в вычислении
$$\sum_{n=3}^{60} T(n)\pmod{10^9+7}.$$
Решение естественно распадается на две части: геометрическую классификацию внутренних точек по кратности пересечения и комбинаторный подсчёт циклов с фиксированными диагоналями.
Обозначим \(M=10^9+7\). Для фиксированного \(n\) пусть \(P_n(r)\) означает число внутренних точек, через которые проходят ровно \(r\) диагоналей правильного \(n\)-угольника. Тогда задача сводится к тому, чтобы для каждого \(r\) определить, сколько гамильтоновых циклов содержат хотя бы две из этих \(r\) диагоналей.
Возьмём индексы \(a<b<c<d\). В выпуклом \(n\)-угольнике диагонали \(ac\) и \(bd\) пересекаются ровно в одной внутренней точке. Значит, каждая упорядоченная четвёрка \(a<b<c<d\) даёт одно событие пересечения диагоналей.
Если точка \(P\) является общей точкой ровно для \(r\) диагоналей, то каждая пара из этих \(r\) диагоналей определяет одну четвёрку, и каждая такая четвёрка приводит обратно к той же точке. Поэтому число четвёрок, порождающих \(P\), равно
$$q=\binom{r}{2}.$$
После группировки совпадающих геометрических пересечений кратность \(r\) восстанавливается по размеру группы \(q\) формулой
$$r=\frac{1+\sqrt{1+8q}}{2}.$$
Таким образом, геометрическая часть предельно прямолинейна: перечислить все четвёрки, объединить одинаковые точки и по размеру каждой группы определить число сходящихся диагоналей.
Теперь зафиксируем внутреннюю точку \(P\) кратности \(r\). Все диагонали, проходящие через один и тот же внутренний пункт, попарно не имеют общих концов как рёбра многоугольника; иначе они встретились бы в вершине на границе, а не внутри.
Для \(t\in\{0,1,\dots,r\}\) обозначим через \(A_n(t)\) число неориентированных гамильтоновых циклов на \(n\) размеченных вершинах, которые содержат некоторый фиксированный набор из \(t\) диагоналей, проходящих через \(P\).
При \(t=0\) это просто общее число гамильтоновых циклов на \(n\) размеченных вершинах:
$$A_n(0)=\frac{(n-1)!}{2}.$$
При \(t\ge 1\) каждую обязательную диагональ можно стянуть в один блок. Так как выбранные диагонали попарно не пересекаются по концам, после стягивания остаётся \(n-t\) объектов. Число их неориентированных циклических порядков равно
$$\frac{(n-t-1)!}{2},$$
а каждый блок можно пройти в двух направлениях. Значит,
$$A_n(t)=2^t\cdot \frac{(n-t-1)!}{2}=(n-t-1)!\,2^{t-1}\qquad (t\ge 1).$$
Именно эта формула лежит в основе комбинаторной части реализации.
Пусть для точки с \(r\) доступными диагоналями величина \(B_n(r)\) обозначает число гамильтоновых циклов, не использующих ни одной из них. Стандартный принцип включения-исключения по \(r\) запрещённым диагоналям даёт
$$B_n(r)=\sum_{t=0}^{r}(-1)^t\binom{r}{t}A_n(t).$$
Пусть далее \(C_n(r)\) - число гамильтоновых циклов, использующих ровно одну из этих \(r\) диагоналей. Сначала выбирается эта единственная диагональ, а затем остальные \(r-1\) снова исключаются по включению-исключению:
$$C_n(r)=r\sum_{t=0}^{r-1}(-1)^t\binom{r-1}{t}A_n(t+1).$$
Если \(D_n(r)\) обозначает число циклов, содержащих хотя бы две диагонали через точку, то
$$D_n(r)=A_n(0)-B_n(r)-C_n(r).$$
Это и есть главный комбинаторный каркас решения.
После того как все внутренние точки правильного \(n\)-угольника разбиты по кратности, полный вклад равен
$$T(n)=\sum_{r\ge 2} P_n(r)\,D_n(r)\pmod{M}.$$
Нижняя граница \(r\ge 2\) очевидна: интересующая нас внутренняя точка должна быть пересечением как минимум двух диагоналей. Все классы кратности независимы, поэтому сначала вычисляются числа \(P_n(r)\), а затем к каждому наблюдаемому \(r\) применяется одна и та же формула.
У правильного пятиугольника имеется пять внутренних точек пересечения диагоналей, и каждая из них образована ровно двумя диагоналями. Следовательно,
$$P_5(2)=5.$$
Общее число неориентированных гамильтоновых циклов равно
$$A_5(0)=\frac{4!}{2}=12.$$
Для одной фиксированной диагонали через выбранную точку пересечения получаем
$$A_5(1)=(5-2)!\,2^0=6,$$
а для обеих диагоналей этой точки
$$A_5(2)=(5-3)!\,2^1=4.$$
Отсюда
$$B_5(2)=A_5(0)-2A_5(1)+A_5(2)=12-12+4=4,$$
$$C_5(2)=2\bigl(A_5(1)-A_5(2)\bigr)=2(6-4)=4,$$
и поэтому
$$D_5(2)=12-4-4=4.$$
Умножая на пять точек пересечения, получаем
$$T(5)=P_5(2)D_5(2)=5\cdot 4=20,$$
что совпадает с малой контрольной проверкой решателя.
Реализация на C++ заранее вычисляет факториалы, обратные факториалы и степени двойки по модулю \(10^9+7\) до \(60\). Благодаря этому биномиальные коэффициенты и значения \(A_n(t)\) получаются за постоянное время во время основного расчёта.
Для каждого \(n\) вершины помещаются на единичную окружность с помощью высокоточной тригонометрии. Затем программа перебирает все четвёрки \(a<b<c<d\), вычисляет точку пересечения диагоналей \(ac\) и \(bd\), масштабирует координаты и округляет их до устойчивого целочисленного ключа, чтобы совпадающие точки гарантированно попадали в одну группу.
По размеру каждой группы \(q\) кратность \(r\) восстанавливается через тождество треугольных чисел \(q=\binom{r}{2}\). После этого реализация вычисляет по формулам включения-исключения значение \(D_n(r)\), умножает его на число точек соответствующего класса и накапливает \(T(n)\) по модулю \(10^9+7\).
Реализация на C++ выполняет всё численное вычисление напрямую. Реализации на Python и Java передают работу тому же скомпилированному вычислению и лишь извлекают напечатанный в конце результат.
Для фиксированного \(n\) геометрический этап перебирает все четвёрки вершин, поэтому требует \(O(n^4)\) времени. Таблица группировки пересечений хранит по одной записи на каждую различную внутреннюю точку, так что память равна \(O(U_n)\), где \(U_n\le \binom{n}{4}\).
Комбинаторный этап значительно меньше. Модульная предобработка стоит \(O(n)\), а суммирование по возможным кратностям для одного \(n\) в худшем случае требует \(O(n^2)\). Следовательно, основную стоимость полностью задаёт геометрический перебор.
На всём диапазоне \(3\le n\le 60\) время работы определяется прежде всего суммой
$$\sum_{n=3}^{60} O(n^4),$$
что вполне практично при такой фиксированной границе.
لكل قيمة \(n\)، نضع رؤوس مضلع منتظم ذي \(n\) أضلاع على دائرة، ثم نرسم جميع أضلاع المضلع كأوتار مستقيمة. الكمية \(T(n)\) تُبنى على النحو الآتي: نمر على كل نقطة داخلية تتقاطع عندها أقطار، ونعدّ عدد الدورات الهاملتونية غير الموجهة على الرؤوس نفسها التي تستخدم ضلعين قطريين على الأقل من الأقطار المارة بتلك النقطة، ثم نجمع هذه المساهمات على جميع نقاط التقاطع الداخلية.
إذن المطلوب النهائي هو حساب
$$\sum_{n=3}^{60} T(n)\pmod{10^9+7}.$$
الفكرة الأساسية هي فصل المسألة إلى طبقتين مستقلتين نسبيًا: طبقة هندسية لتصنيف نقاط التقاطع بحسب عدد الأقطار المارة فيها، وطبقة تركيبية لعدّ الدورات التي تحتوي على مجموعة محددة من الأقطار.
لنكتب \(M=10^9+7\). ولعدد ثابت \(n\)، لِنرمز بـ \(P_n(r)\) إلى عدد نقاط التقاطع الداخلية التي تمر بها بالضبط \(r\) أقطار من المضلع المنتظم ذي \(n\) أضلاع. عندئذٍ تصبح المهمة هي: لكل قيمة ممكنة لـ \(r\)، كم عدد الدورات الهاملتونية التي تحتوي على قطرين على الأقل من هذه الأقطار \(r\)؟
خذ فهارس \(a<b<c<d\). في مضلع محدب، يتقاطع القطران \(ac\) و\(bd\) في نقطة داخلية واحدة بالضبط. لذلك فإن كل رباعية مرتبة \(a<b<c<d\) تنتج حادثة تقاطع واحدة للأقطار.
إذا كانت نقطة داخلية \(P\) هي نقطة التقاطع المشتركة لعدد \(r\) من الأقطار، فإن كل زوج من هذه الأقطار يحدد رباعية واحدة، وكل رباعية من هذا النوع تعود إلى النقطة نفسها. لذلك يكون عدد الرباعيات التي تنتج \(P\) هو
$$q=\binom{r}{2}.$$
وبعد تجميع نقاط التقاطع المتطابقة هندسيًا، يمكن استرجاع عدد الأقطار المتزامنة \(r\) مباشرة من حجم المجموعة \(q\) عبر
$$r=\frac{1+\sqrt{1+8q}}{2}.$$
وهذا يعني أن الجزء الهندسي لا يحتاج إلى صياغة أعقد من ذلك: يكفي تعداد جميع الرباعيات، ثم دمج الإحداثيات المتساوية، ثم تحويل حجم كل مجموعة إلى قيمة \(r\).
الآن ثبّت نقطة داخلية \(P\) لها تعددية \(r\). الأقطار المارة بنقطة داخلية واحدة تكون متباينة طرفيًا كحواف في المضلع؛ فلو اشترك اثنان منها في رأس واحد لكان التقاؤهما على الحدود لا في الداخل.
لكل \(t\in\{0,1,\dots,r\}\)، نعرّف \(A_n(t)\) بأنه عدد الدورات الهاملتونية غير الموجهة على الرؤوس \(n\) المعلَّمة التي تحتوي على مجموعة ثابتة من \(t\) أقطار تمر بالنقطة \(P\).
عندما \(t=0\)، فهذا مجرد العدد الكلي للدورات الهاملتونية غير الموجهة على \(n\) رؤوس معلَّمة:
$$A_n(0)=\frac{(n-1)!}{2}.$$
وعندما \(t\ge 1\)، يمكن ضغط كل قطر مفروض إلى كتلة واحدة. وبما أن الأقطار المختارة متباينة، ينخفض عدد الوحدات من \(n\) إلى \(n-t\). عدد الترتيبات الدورية غير الموجهة لهذه الوحدات هو
$$\frac{(n-t-1)!}{2},$$
وكل كتلة يمكن عبورها في اتجاهين. لذلك نحصل على
$$A_n(t)=2^t\cdot \frac{(n-t-1)!}{2}=(n-t-1)!\,2^{t-1}\qquad (t\ge 1).$$
وهذه هي بالضبط قاعدة العدّ التي تعتمدها التطبيقات.
لنعرّف \(B_n(r)\) بأنه عدد الدورات الهاملتونية التي لا تستخدم أيًا من الأقطار \(r\) المارة بالنقطة. بتطبيق مبدأ الاشتمال والاستبعاد على هذه الأقطار الممنوعة نحصل على
$$B_n(r)=\sum_{t=0}^{r}(-1)^t\binom{r}{t}A_n(t).$$
ولنعرّف \(C_n(r)\) بأنه عدد الدورات التي تستخدم قطرًا واحدًا فقط من هذه الأقطار \(r\). نختار أولًا القطر المستخدم، ثم نستبعد الأقطار \(r-1\) الأخرى مرة أخرى بالاشتمال والاستبعاد:
$$C_n(r)=r\sum_{t=0}^{r-1}(-1)^t\binom{r-1}{t}A_n(t+1).$$
إذا كانت \(D_n(r)\) تمثل عدد الدورات التي تحتوي على قطرين على الأقل من الأقطار المارة بالنقطة، فإن
$$D_n(r)=A_n(0)-B_n(r)-C_n(r).$$
هذه هي الصيغة التركيبية المركزية في الحل.
بعد تصنيف جميع نقاط التقاطع الداخلية في المضلع المنتظم بحسب تعدديتها، يصبح المجموع الكلي
$$T(n)=\sum_{r\ge 2} P_n(r)\,D_n(r)\pmod{M}.$$
والشرط \(r\ge 2\) طبيعي لأن نقطة التقاطع الداخلية المهمة لا بد أن تمر بها على الأقل قطريان. وكل فئة تعددية تسهم بصورة مستقلة، ولذلك يمكن أولًا حساب \(P_n(r)\)، ثم تطبيق الصيغة التركيبية نفسها على كل قيمة \(r\) تظهر فعليًا.
في الخماسي المنتظم توجد خمس نقاط تقاطع داخلية للأقطار، وكل نقطة منها ناتجة عن قطرين بالضبط. لذلك
$$P_5(2)=5.$$
أما العدد الكلي للدورات الهاملتونية غير الموجهة فهو
$$A_5(0)=\frac{4!}{2}=12.$$
ولقطر ثابت واحد يمر بنقطة تقاطع مختارة نحصل على
$$A_5(1)=(5-2)!\,2^0=6,$$
وللقطرين المارين بالنقطة نفسها معًا نحصل على
$$A_5(2)=(5-3)!\,2^1=4.$$
إذن
$$B_5(2)=A_5(0)-2A_5(1)+A_5(2)=12-12+4=4,$$
$$C_5(2)=2\bigl(A_5(1)-A_5(2)\bigr)=2(6-4)=4,$$
ومن ثم
$$D_5(2)=12-4-4=4.$$
وبالضرب في عدد نقاط التقاطع الخمس نحصل على
$$T(5)=P_5(2)D_5(2)=5\cdot 4=20,$$
وهو بالضبط الاختبار الصغير الذي تتحقق منه أداة الحل.
تقوم نسخة C++ أولًا بحساب المضاريب، والمضاريب العكسية، وقوى العدد \(2\) modulo \(10^9+7\) حتى \(60\). وبهذا تصبح معاملات ثنائية الحد والقيم \(A_n(t)\) متاحة بزمن ثابت داخل الجزء الرئيسي من الحساب.
لكل \(n\)، توضع الرؤوس على دائرة الوحدة باستخدام قيم مثلثية عالية الدقة، ثم تُعدَّد جميع الرباعيات \(a<b<c<d\)، ويُحسب تقاطع القطرين \(ac\) و\(bd\). بعد ذلك تُضرب الإحداثيات في مقياس ثابت كبير وتُقرَّب إلى مفاتيح صحيحة مستقرة، حتى تُجمَّع النقاط المتطابقة في الحاوية نفسها.
من حجم كل مجموعة \(q\)، يُستعاد عدد الأقطار المتزامنة \(r\) باستعمال علاقة الأعداد المثلثية \(q=\binom{r}{2}\). ثم تُقيَّم صيغ الاشتمال والاستبعاد السابقة للحصول على \(D_n(r)\)، وتُضرب في عدد النقاط من الفئة نفسها، ثم يُراكَم \(T(n)\) modulo \(10^9+7\).
تنفذ نسخة C++ كامل الحساب العددي مباشرة. أما نسختا Python وJava فتستدعيان الحساب المترجم نفسه وتكتفيان بقراءة القيمة النهائية المطبوعة.
عند تثبيت \(n\)، تفحص المرحلة الهندسية جميع رباعيات الرؤوس، ولذلك يكون زمنها \(O(n^4)\). أما بنية تجميع نقاط التقاطع فتنشئ مدخلًا لكل نقطة داخلية متميزة، لذا يكون استهلاك الذاكرة \(O(U_n)\) حيث \(U_n\le \binom{n}{4}\).
المرحلة التركيبية أصغر بكثير. فالمعالجة المسبقة المعيارية تكلف \(O(n)\)، بينما تقييم مجاميع الاشتمال والاستبعاد على قيم التعددية الممكنة لا يتجاوز في أسوأ الحالات \(O(n^2)\) لقيمة ثابتة من \(n\). لذلك تظل كلفة التعداد الهندسي هي المسيطرة بوضوح.
وعلى المجال الكامل \(3\le n\le 60\)، يهيمن على زمن التنفيذ الحد
$$\sum_{n=3}^{60} O(n^4),$$
وهو عملي تمامًا لأن الحد الأعلى ثابت وصغير نسبيًا.