For each unordered pair of labelled vertices \(1,\dots,n\), exactly one of four edge types is chosen: a red directed edge, a blue directed edge in the opposite direction, a green undirected edge, or a brown undirected edge. A graph is called beautiful when red edges occur in a cycle if and only if blue edges also occur in a cycle, and no triangle is monochromatic in green or monochromatic in brown.
Let \(G(n)\) be the number of beautiful graphs on \(n\) labelled vertices. The target value is \(G(10^7)\bmod(10^9+7)\). Direct enumeration is completely infeasible, so the implementations rely on a short linear recurrence that already packages the structural counting into five constants.
The implementations use the fact that all problem-specific structure can be summarized by five coefficients
$$A_1=1,\qquad A_2=2,\qquad A_3=6,\qquad A_4=18,\qquad A_5=12.$$
Everything else follows from turning those constants into a recurrence that is stable under modular arithmetic.
Write \(G(0)=1\) for the empty graph. The structural reduction encoded in the implementations gives the recurrence
$$\boxed{G(n)=\sum_{j=1}^{\min(5,n)} A_j \binom{n}{j} G(n-j)\qquad (n\ge 1).}$$
The binomial factor chooses which \(j\) labels participate in the final contribution, while \(A_j\) counts the admissible local configurations of that size. The key practical fact is that only sizes \(1,2,3,4,5\) appear, so the recurrence has fixed width.
The binomial coefficient introduces an \(n!\)-scale growth, so the implementations normalize by
$$H_n=\frac{G(n)}{n!},\qquad H_0=1.$$
Substituting \(G(n)=n!H_n\) into the previous formula gives
$$n!H_n=\sum_{j=1}^{\min(5,n)} A_j \frac{n!}{j!(n-j)!}(n-j)!H_{n-j},$$
and after cancelling \(n!\) we obtain
$$H_n=\sum_{j=1}^{\min(5,n)} \frac{A_j}{j!} H_{n-j}.$$
This is the decisive simplification: the coefficients no longer depend on \(n\).
Now compute the five normalized coefficients:
$$\frac{A_1}{1!}=1,\qquad \frac{A_2}{2!}=1,\qquad \frac{A_3}{3!}=1,\qquad \frac{A_4}{4!}=\frac{18}{24}=\frac{3}{4},\qquad \frac{A_5}{5!}=\frac{12}{120}=\frac{1}{10}.$$
Therefore, for \(n\ge 5\),
$$\boxed{H_n=H_{n-1}+H_{n-2}+H_{n-3}+\frac{3}{4}H_{n-4}+\frac{1}{10}H_{n-5}.}$$
For \(n<5\), the same formula is simply truncated at \(j=n\). This is exactly the recurrence used by the C++, Python, and Java implementations.
Let
$$H(x)=\sum_{n\ge 0} H_n x^n.$$
Multiplying the recurrence by \(x^n\) and summing over \(n\ge 1\) yields
$$H(x)-1=\left(x+x^2+x^3+\frac{3}{4}x^4+\frac{1}{10}x^5\right)H(x).$$
Hence
$$\boxed{H(x)=\frac{1}{1-x-x^2-x^3-\frac{3}{4}x^4-\frac{1}{10}x^5}.}$$
This rational form explains why only the previous five values are needed: the denominator has degree \(5\), so the normalized sequence satisfies a linear recurrence of order \(5\).
The computations are carried out modulo
$$p=10^9+7,$$
which is prime. Therefore every nonzero denominator up to \(5!\) has a modular inverse. In particular,
$$\frac{3}{4}\pmod p=3\cdot 4^{p-2}\pmod p,\qquad \frac{1}{10}\pmod p=10^{p-2}\pmod p.$$
The implementations obtain these values from modular inverses of the small factorials \(1!,2!,3!,4!,5!\), so the recurrence is evaluated entirely with integer modular arithmetic.
Using the raw recurrence for \(G(n)\), we get:
$$G(1)=A_1\binom{1}{1}G(0)=1.$$
$$G(2)=A_1\binom{2}{1}G(1)+A_2\binom{2}{2}G(0)=1\cdot 2\cdot 1+2\cdot 1\cdot 1=4.$$
$$G(3)=A_1\binom{3}{1}G(2)+A_2\binom{3}{2}G(1)+A_3\binom{3}{3}G(0)=12+6+6=24.$$
$$G(4)=A_1\binom{4}{1}G(3)+A_2\binom{4}{2}G(2)+A_3\binom{4}{3}G(1)+A_4\binom{4}{4}G(0)=96+48+24+18=186.$$
$$G(5)=A_1\binom{5}{1}G(4)+A_2\binom{5}{2}G(3)+A_3\binom{5}{3}G(2)+A_4\binom{5}{4}G(1)+A_5\binom{5}{5}G(0)=930+480+240+90+12=1752.$$
Dividing by \(n!\) gives
$$H_0=1,\qquad H_1=1,\qquad H_2=2,\qquad H_3=4,\qquad H_4=\frac{31}{4},\qquad H_5=\frac{73}{5},$$
and these values indeed satisfy the normalized recurrence above.
The C++, Python, and Java implementations all follow the same plan. First they precompute the small factorials \(1!,\dots,5!\) and their modular inverses using fast exponentiation, because the modulus is prime. Multiplying the five structural constants by those inverse factorials produces the recurrence coefficients \(1,1,1,\frac{3}{4},\frac{1}{10}\) in modular form.
Next, the implementation builds the normalized sequence from \(H_0=1\) up to \(H_{10^7}\). For each \(n\), it sums at most five earlier terms, so the transition cost is constant. At the same time it maintains the running factorial \(n!\bmod(10^9+7)\). After the loop finishes, it multiplies the final normalized value by \(10^7!\) to recover \(G(10^7)\bmod(10^9+7)\).
For target \(N=10^7\), each state update uses at most five modular products and additions, so the running time is \(O(N)\). The modular inverse setup for the small factorials is constant-size overhead. The current implementations store the whole normalized table up to \(N\), which uses \(O(N)\) memory, although the recurrence itself only needs the previous five values and could be reduced to \(O(1)\) memory with a rolling window.
Für jedes ungeordnete Paar der markierten Knoten \(1,\dots,n\) wird genau einer von vier Kantentypen gewählt: eine rote gerichtete Kante, eine blaue gerichtete Kante in Gegenrichtung, eine grüne ungerichtete Kante oder eine braune ungerichtete Kante. Ein Graph heißt beautiful, wenn rote Kanten genau dann in einem Zyklus vorkommen, wenn auch blaue Kanten in einem Zyklus vorkommen, und wenn kein Dreieck vollständig grün oder vollständig braun ist.
Sei \(G(n)\) die Anzahl solcher beautiful Graphen auf \(n\) markierten Knoten. Gesucht ist \(G(10^7)\bmod(10^9+7)\). Direkte Enumeration ist ausgeschlossen; stattdessen benutzen die Implementierungen eine kurze lineare Rekurrenz, in der die gesamte problemabhängige Struktur bereits in fünf Konstanten zusammengefasst ist.
Die Implementierungen arbeiten mit den fünf problemabhängigen Koeffizienten
$$A_1=1,\qquad A_2=2,\qquad A_3=6,\qquad A_4=18,\qquad A_5=12.$$
Aus diesen Werten entsteht eine Rekurrenz, die sich anschließend bequem modulo \(10^9+7\) auswerten lässt.
Für den leeren Graphen gilt \(G(0)=1\). Die in den Implementierungen kodierte Strukturaussage führt auf
$$\boxed{G(n)=\sum_{j=1}^{\min(5,n)} A_j \binom{n}{j} G(n-j)\qquad (n\ge 1).}$$
Der Binomialkoeffizient wählt aus, welche \(j\) Labels zum letzten Beitrag gehören, und \(A_j\) zählt die zulässigen lokalen Muster dieser Größe. Praktisch entscheidend ist: Es treten nur die Größen \(1\) bis \(5\) auf, also besitzt die Rekurrenz feste Breite.
Wegen des Binomialkoeffizienten wächst \(G(n)\) natürlich auf der Skala von \(n!\). Deshalb normieren die Implementierungen mit
$$H_n=\frac{G(n)}{n!},\qquad H_0=1.$$
Setzt man \(G(n)=n!H_n\) in die vorige Formel ein, so erhält man
$$n!H_n=\sum_{j=1}^{\min(5,n)} A_j \frac{n!}{j!(n-j)!}(n-j)!H_{n-j},$$
und nach Kürzen von \(n!\) folgt
$$H_n=\sum_{j=1}^{\min(5,n)} \frac{A_j}{j!} H_{n-j}.$$
Das ist die zentrale Vereinfachung: Die Koeffizienten hängen nun nicht mehr von \(n\) ab.
Die normierten Koeffizienten lauten
$$\frac{A_1}{1!}=1,\qquad \frac{A_2}{2!}=1,\qquad \frac{A_3}{3!}=1,\qquad \frac{A_4}{4!}=\frac{18}{24}=\frac{3}{4},\qquad \frac{A_5}{5!}=\frac{12}{120}=\frac{1}{10}.$$
Damit gilt für \(n\ge 5\)
$$\boxed{H_n=H_{n-1}+H_{n-2}+H_{n-3}+\frac{3}{4}H_{n-4}+\frac{1}{10}H_{n-5}.}$$
Für \(n<5\) wird dieselbe Summe einfach bei \(j=n\) abgeschnitten. Genau diese Rekurrenz berechnen die C++-, Python- und Java-Implementierungen.
Definiere
$$H(x)=\sum_{n\ge 0} H_n x^n.$$
Multipliziert man die Rekurrenz mit \(x^n\) und summiert über \(n\ge 1\), so ergibt sich
$$H(x)-1=\left(x+x^2+x^3+\frac{3}{4}x^4+\frac{1}{10}x^5\right)H(x).$$
Also
$$\boxed{H(x)=\frac{1}{1-x-x^2-x^3-\frac{3}{4}x^4-\frac{1}{10}x^5}.}$$
Diese rationale Form erklärt unmittelbar, warum nur die letzten fünf Werte benötigt werden: Der Nenner hat Grad \(5\), also erfüllt die normierte Folge eine lineare Rekurrenz fünfter Ordnung.
Gerechnet wird modulo
$$p=10^9+7,$$
und \(p\) ist prim. Deshalb besitzt jeder von \(0\) verschiedene Nenner bis \(5!\) ein multiplikatives Inverses. Insbesondere gilt
$$\frac{3}{4}\pmod p=3\cdot 4^{p-2}\pmod p,\qquad \frac{1}{10}\pmod p=10^{p-2}\pmod p.$$
Die Implementierungen gewinnen diese Werte aus den modularen Inversen der kleinen Fakultäten \(1!,2!,3!,4!,5!\), sodass die gesamte Rekurrenz mit ganzzahliger modularer Arithmetik ausgewertet wird.
Mit der rohen Rekurrenz für \(G(n)\) erhält man:
$$G(1)=A_1\binom{1}{1}G(0)=1.$$
$$G(2)=A_1\binom{2}{1}G(1)+A_2\binom{2}{2}G(0)=1\cdot 2\cdot 1+2\cdot 1\cdot 1=4.$$
$$G(3)=A_1\binom{3}{1}G(2)+A_2\binom{3}{2}G(1)+A_3\binom{3}{3}G(0)=12+6+6=24.$$
$$G(4)=A_1\binom{4}{1}G(3)+A_2\binom{4}{2}G(2)+A_3\binom{4}{3}G(1)+A_4\binom{4}{4}G(0)=96+48+24+18=186.$$
$$G(5)=A_1\binom{5}{1}G(4)+A_2\binom{5}{2}G(3)+A_3\binom{5}{3}G(2)+A_4\binom{5}{4}G(1)+A_5\binom{5}{5}G(0)=930+480+240+90+12=1752.$$
Nach Division durch \(n!\) folgt
$$H_0=1,\qquad H_1=1,\qquad H_2=2,\qquad H_3=4,\qquad H_4=\frac{31}{4},\qquad H_5=\frac{73}{5},$$
und genau diese Werte erfüllen die normierte Rekurrenz.
Die C++-, Python- und Java-Implementierungen verfolgen denselben Ablauf. Zuerst berechnen sie die kleinen Fakultäten \(1!,\dots,5!\) sowie deren modulare Inverse per schneller Potenzierung, weil der Modul prim ist. Multipliziert man die fünf Strukturkonstanten mit diesen inversen Fakultäten, entstehen die Rekurrenzkoeffizienten \(1,1,1,\frac{3}{4},\frac{1}{10}\) in modularer Darstellung.
Danach wird die normierte Folge von \(H_0=1\) bis \(H_{10^7}\) aufgebaut. Für jedes \(n\) müssen höchstens fünf frühere Werte addiert werden; die Übergangskosten sind also konstant. Parallel dazu wird das laufende Fakultätsprodukt \(n!\bmod(10^9+7)\) aktualisiert. Am Ende wird der letzte normierte Wert mit \(10^7!\) multipliziert, um \(G(10^7)\bmod(10^9+7)\) zurückzugewinnen.
Für das Ziel \(N=10^7\) benötigt jeder Zustand höchstens fünf modulare Multiplikationen und Additionen, also insgesamt \(O(N)\) Zeit. Die Vorbereitung der modularen Inversen ist nur konstanter Zusatzaufwand. Die aktuellen Implementierungen speichern die gesamte normierte Tabelle bis \(N\) und verbrauchen daher \(O(N)\) Speicher. Die Rekurrenz selbst bräuchte jedoch nur die letzten fünf Werte und ließe sich deshalb auch mit \(O(1)\) Speicher ausführen.
Etiketli \(1,\dots,n\) düğümlerinin her sırasız çifti için dört kenar tipinden tam biri seçilir: kırmızı yönlü kenar, ters yönde mavi yönlü kenar, yeşil yönsüz kenar veya kahverengi yönsüz kenar. Bir grafik, kırmızı kenarlar bir çevrimde ancak ve ancak mavi kenarlar da bir çevrimde ortaya çıkıyorsa ve hiçbir üçgen tamamen yeşil ya da tamamen kahverengi değilse beautiful olarak adlandırılır.
\(G(n)\), \(n\) etiketli düğüm üzerindeki beautiful grafiklerin sayısı olsun. Hedef değer \(G(10^7)\bmod(10^9+7)\) olduğundan, doğrudan grafik saymak imkansızdır. Bu yüzden uygulamalar, problem yapısını beş sabitte özetleyen kısa bir doğrusal bağıntı kullanır.
Uygulamalar, probleme özgü tüm sayımı şu beş katsayıya indirger:
$$A_1=1,\qquad A_2=2,\qquad A_3=6,\qquad A_4=18,\qquad A_5=12.$$
Geri kalan adımlar bu katsayılardan sabit katsayılı bir bağıntı çıkarmaktır.
Boş grafik için \(G(0)=1\) alınır. Uygulamaların kullandığı yapısal indirgeme şu bağıntıyı verir:
$$\boxed{G(n)=\sum_{j=1}^{\min(5,n)} A_j \binom{n}{j} G(n-j)\qquad (n\ge 1).}$$
Buradaki binom katsayısı, son katkıya dahil olan \(j\) etiketi seçer; \(A_j\) ise bu büyüklükteki izinli yerel desen sayısını verir. Hesaplama açısından kritik nokta, yalnızca \(1,2,3,4,5\) boyutlarının görünmesidir; böylece bağıntının genişliği sabit kalır.
Binom katsayısı nedeniyle \(G(n)\) doğal olarak \(n!\) ölçeğinde büyür. Bu yüzden uygulamalar
$$H_n=\frac{G(n)}{n!},\qquad H_0=1$$
normalizasyonunu yapar. \(G(n)=n!H_n\) yazıp önceki formüle koyarsak
$$n!H_n=\sum_{j=1}^{\min(5,n)} A_j \frac{n!}{j!(n-j)!}(n-j)!H_{n-j}$$
elde edilir. \(n!\) sadeleşince
$$H_n=\sum_{j=1}^{\min(5,n)} \frac{A_j}{j!}H_{n-j}$$
kalır. Asıl sadeleşme budur: katsayılar artık \(n\)'ye bağlı değildir.
Şimdi normalleştirilmiş katsayıları yazalım:
$$\frac{A_1}{1!}=1,\qquad \frac{A_2}{2!}=1,\qquad \frac{A_3}{3!}=1,\qquad \frac{A_4}{4!}=\frac{18}{24}=\frac{3}{4},\qquad \frac{A_5}{5!}=\frac{12}{120}=\frac{1}{10}.$$
Böylece \(n\ge 5\) için
$$\boxed{H_n=H_{n-1}+H_{n-2}+H_{n-3}+\frac{3}{4}H_{n-4}+\frac{1}{10}H_{n-5}.}$$
\(n<5\) olduğunda toplam sadece \(j=n\)'ye kadar kesilir. C++, Python ve Java uygulamaları tam olarak bu normalize bağıntıyı hesaplar.
Şunu tanımlayalım:
$$H(x)=\sum_{n\ge 0} H_n x^n.$$
Bağıntıyı \(x^n\) ile çarpıp \(n\ge 1\) için toplarsak
$$H(x)-1=\left(x+x^2+x^3+\frac{3}{4}x^4+\frac{1}{10}x^5\right)H(x)$$
elde edilir. Buradan
$$\boxed{H(x)=\frac{1}{1-x-x^2-x^3-\frac{3}{4}x^4-\frac{1}{10}x^5}.}$$
Bu rasyonel form, neden yalnızca son beş terimin yeterli olduğunu açıklar: paydanın derecesi \(5\) olduğu için dizi beşinci dereceden doğrusal bağıntı sağlar.
Hesaplar
$$p=10^9+7$$
asal modunda yapılır. Bu nedenle \(5!\)'e kadar olan tüm sıfırdan farklı paydaların modüler tersi vardır. Özellikle
$$\frac{3}{4}\pmod p=3\cdot 4^{p-2}\pmod p,\qquad \frac{1}{10}\pmod p=10^{p-2}\pmod p.$$
Uygulamalar bu değerleri küçük faktöriyellerin modüler terslerinden üretir; böylece tüm bağıntı yalnızca tamsayı modüler aritmetik ile yürütülür.
\(G(n)\) için ham bağıntıyı kullanırsak:
$$G(1)=A_1\binom{1}{1}G(0)=1.$$
$$G(2)=A_1\binom{2}{1}G(1)+A_2\binom{2}{2}G(0)=1\cdot 2\cdot 1+2\cdot 1\cdot 1=4.$$
$$G(3)=A_1\binom{3}{1}G(2)+A_2\binom{3}{2}G(1)+A_3\binom{3}{3}G(0)=12+6+6=24.$$
$$G(4)=A_1\binom{4}{1}G(3)+A_2\binom{4}{2}G(2)+A_3\binom{4}{3}G(1)+A_4\binom{4}{4}G(0)=96+48+24+18=186.$$
$$G(5)=A_1\binom{5}{1}G(4)+A_2\binom{5}{2}G(3)+A_3\binom{5}{3}G(2)+A_4\binom{5}{4}G(1)+A_5\binom{5}{5}G(0)=930+480+240+90+12=1752.$$
Bunları \(n!\)'e böldüğümüzde
$$H_0=1,\qquad H_1=1,\qquad H_2=2,\qquad H_3=4,\qquad H_4=\frac{31}{4},\qquad H_5=\frac{73}{5}$$
elde edilir ve bu değerler normalize bağıntıyı aynen sağlar.
C++, Python ve Java uygulamalarının planı aynıdır. Önce \(1!,\dots,5!\) değerleri ve bunların modüler tersleri hızlı üs alma ile hesaplanır; çünkü mod asal sayıdır. Ardından beş yapısal sabit bu ters faktöriyellerle çarpılarak \(1,1,1,\frac{3}{4},\frac{1}{10}\) katsayılarının modüler karşılıkları elde edilir.
Sonra normalize dizi \(H_0=1\)'den \(H_{10^7}\)'ye kadar oluşturulur. Her \(n\) için en fazla beş önceki değer toplandığından adım maliyeti sabittir. Aynı döngü içinde \(n!\bmod(10^9+7)\) da kademeli olarak güncellenir. Döngü bittiğinde son normalize değer ile \(10^7!\) çarpılarak \(G(10^7)\bmod(10^9+7)\) bulunur.
Hedef \(N=10^7\) için her güncelleme en fazla beş modüler çarpma ve toplama içerir; dolayısıyla toplam süre \(O(N)\)'dir. Küçük faktöriyellerin terslerini hazırlamak sabit boyutlu ek masraftır. Mevcut uygulamalar normalize dizinin tamamını sakladığı için bellek kullanımı \(O(N)\)'dir. Oysa bağıntının kendisi yalnızca son beş değeri gerektirir; bu yüzden kayan pencere ile \(O(1)\) belleğe de indirgenebilir.
Para cada par no ordenado de vértices etiquetados \(1,\dots,n\), se elige exactamente uno de cuatro tipos de arista: una arista roja dirigida, una arista azul dirigida en la dirección opuesta, una arista verde no dirigida o una arista marrón no dirigida. Un grafo se llama beautiful cuando las aristas rojas aparecen en un ciclo si y solo si las aristas azules también aparecen en un ciclo, y además ningún triángulo es totalmente verde ni totalmente marrón.
Sea \(G(n)\) el número de grafos beautiful sobre \(n\) vértices etiquetados. El objetivo es calcular \(G(10^7)\bmod(10^9+7)\). Enumerar grafos directamente es imposible, así que las implementaciones usan una recurrencia lineal corta que ya incorpora toda la información estructural del problema en cinco constantes.
Las implementaciones condensan toda la parte específica del problema en los cinco coeficientes
$$A_1=1,\qquad A_2=2,\qquad A_3=6,\qquad A_4=18,\qquad A_5=12.$$
A partir de estos valores se obtiene una recurrencia con coeficientes constantes, adecuada para el cálculo modular.
Para el grafo vacío se toma \(G(0)=1\). La reducción estructural codificada en las implementaciones conduce a
$$\boxed{G(n)=\sum_{j=1}^{\min(5,n)} A_j \binom{n}{j} G(n-j)\qquad (n\ge 1).}$$
El coeficiente binomial elige qué \(j\) etiquetas participan en la contribución final, mientras que \(A_j\) cuenta los patrones locales admisibles de ese tamaño. El dato práctico importante es que solo aparecen tamaños \(1,2,3,4,5\), de modo que la anchura de la recurrencia es fija.
Debido al coeficiente binomial, \(G(n)\) crece naturalmente a escala \(n!\). Por eso las implementaciones normalizan mediante
$$H_n=\frac{G(n)}{n!},\qquad H_0=1.$$
Al sustituir \(G(n)=n!H_n\) en la fórmula anterior, se obtiene
$$n!H_n=\sum_{j=1}^{\min(5,n)} A_j \frac{n!}{j!(n-j)!}(n-j)!H_{n-j},$$
y al cancelar \(n!\) queda
$$H_n=\sum_{j=1}^{\min(5,n)} \frac{A_j}{j!}H_{n-j}.$$
Ésta es la simplificación clave: los coeficientes ya no dependen de \(n\).
Los cinco coeficientes normalizados son
$$\frac{A_1}{1!}=1,\qquad \frac{A_2}{2!}=1,\qquad \frac{A_3}{3!}=1,\qquad \frac{A_4}{4!}=\frac{18}{24}=\frac{3}{4},\qquad \frac{A_5}{5!}=\frac{12}{120}=\frac{1}{10}.$$
Por tanto, para \(n\ge 5\),
$$\boxed{H_n=H_{n-1}+H_{n-2}+H_{n-3}+\frac{3}{4}H_{n-4}+\frac{1}{10}H_{n-5}.}$$
Cuando \(n<5\), la misma suma se recorta en \(j=n\). Ésta es exactamente la relación que evalúan las implementaciones en C++, Python y Java.
Definimos
$$H(x)=\sum_{n\ge 0}H_nx^n.$$
Multiplicando la recurrencia por \(x^n\) y sumando sobre \(n\ge 1\), resulta
$$H(x)-1=\left(x+x^2+x^3+\frac{3}{4}x^4+\frac{1}{10}x^5\right)H(x).$$
Así,
$$\boxed{H(x)=\frac{1}{1-x-x^2-x^3-\frac{3}{4}x^4-\frac{1}{10}x^5}.}$$
Esta forma racional explica por qué solo hacen falta cinco valores anteriores: el denominador tiene grado \(5\), por lo que la secuencia normalizada satisface una recurrencia lineal de orden \(5\).
Todos los cálculos se realizan módulo
$$p=10^9+7,$$
que es primo. Por ello, todo denominador no nulo hasta \(5!\) tiene inverso modular. En particular,
$$\frac{3}{4}\pmod p=3\cdot 4^{p-2}\pmod p,\qquad \frac{1}{10}\pmod p=10^{p-2}\pmod p.$$
Las implementaciones obtienen estos valores a partir de los inversos modulares de \(1!,2!,3!,4!,5!\), de modo que la recurrencia se evalúa enteramente con aritmética modular entera.
Aplicando la recurrencia original para \(G(n)\), obtenemos:
$$G(1)=A_1\binom{1}{1}G(0)=1.$$
$$G(2)=A_1\binom{2}{1}G(1)+A_2\binom{2}{2}G(0)=1\cdot 2\cdot 1+2\cdot 1\cdot 1=4.$$
$$G(3)=A_1\binom{3}{1}G(2)+A_2\binom{3}{2}G(1)+A_3\binom{3}{3}G(0)=12+6+6=24.$$
$$G(4)=A_1\binom{4}{1}G(3)+A_2\binom{4}{2}G(2)+A_3\binom{4}{3}G(1)+A_4\binom{4}{4}G(0)=96+48+24+18=186.$$
$$G(5)=A_1\binom{5}{1}G(4)+A_2\binom{5}{2}G(3)+A_3\binom{5}{3}G(2)+A_4\binom{5}{4}G(1)+A_5\binom{5}{5}G(0)=930+480+240+90+12=1752.$$
Al dividir por \(n!\), se obtiene
$$H_0=1,\qquad H_1=1,\qquad H_2=2,\qquad H_3=4,\qquad H_4=\frac{31}{4},\qquad H_5=\frac{73}{5},$$
y estos valores satisfacen exactamente la recurrencia normalizada.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero precalculan los factoriales pequeños \(1!,\dots,5!\) y sus inversos modulares mediante exponenciación rápida, aprovechando que el módulo es primo. Al multiplicar las cinco constantes estructurales por esos inversos factoriales, se obtienen en forma modular los coeficientes \(1,1,1,\frac{3}{4},\frac{1}{10}\).
Después construyen la secuencia normalizada desde \(H_0=1\) hasta \(H_{10^7}\). Para cada \(n\), solo se suman como máximo cinco términos anteriores, por lo que el costo por estado es constante. En paralelo, se mantiene el factorial acumulado \(n!\bmod(10^9+7)\). Al final del bucle, se multiplica el último valor normalizado por \(10^7!\) para recuperar \(G(10^7)\bmod(10^9+7)\).
Para el objetivo \(N=10^7\), cada transición realiza a lo sumo cinco productos y sumas modulares, así que el tiempo total es \(O(N)\). La preparación de inversos modulares para factoriales pequeños es un costo constante. Las implementaciones actuales almacenan toda la tabla normalizada hasta \(N\), de modo que usan \(O(N)\) memoria, aunque la recurrencia en sí solo necesita los últimos cinco valores y podría reducirse a \(O(1)\) con una ventana deslizante.
对标号顶点 \(1,\dots,n\) 的每一对无序顶点，都必须恰好指定四种边型之一：红色有向边、反方向的蓝色有向边、绿色无向边，或者棕色无向边。如果一个图满足下面两个条件，就称它为 beautiful：红边出现在某个环中当且仅当蓝边也出现在某个环中；并且不存在全绿三角形，也不存在全棕三角形。
记 \(G(n)\) 为 \(n\) 个标号顶点上的 beautiful 图的总数。目标是求 \(G(10^7)\bmod(10^9+7)\)。显然不可能直接枚举所有图，所以实现采用的是一个很短的线性递推；与图结构有关的复杂分类已经被压缩进五个常数中。
实现所依赖的核心事实是：问题的结构信息可以浓缩为下面五个系数
$$A_1=1,\qquad A_2=2,\qquad A_3=6,\qquad A_4=18,\qquad A_5=12.$$
一旦这些值已知，后面的推导就变成把它们改写成一个常系数递推，并在模数下稳定地计算。
空图记作 \(G(0)=1\)。实现中编码的结构化结论可以写成
$$\boxed{G(n)=\sum_{j=1}^{\min(5,n)} A_j \binom{n}{j} G(n-j)\qquad (n\ge 1).}$$
这里的二项式系数 \(\binom{n}{j}\) 负责从 \(n\) 个标号中选出最后这一块贡献所涉及的 \(j\) 个顶点，而 \(A_j\) 则表示大小为 \(j\) 的允许局部结构数量。对算法而言，最关键的是只会出现 \(j=1,2,3,4,5\) 这五种大小，因此递推的宽度是固定的。
由于含有二项式系数，\(G(n)\) 自然带有 \(n!\) 量级的增长。为此，实现先做归一化：
$$H_n=\frac{G(n)}{n!},\qquad H_0=1.$$
把 \(G(n)=n!H_n\) 代回上式，得到
$$n!H_n=\sum_{j=1}^{\min(5,n)} A_j \frac{n!}{j!(n-j)!}(n-j)!H_{n-j}.$$
两边消去 \(n!\) 后，就得到
$$H_n=\sum_{j=1}^{\min(5,n)} \frac{A_j}{j!}H_{n-j}.$$
这是整个做法中最重要的一步，因为递推系数从“依赖 \(n\)”变成了“完全常数”。
现在直接计算五个归一化系数：
$$\frac{A_1}{1!}=1,\qquad \frac{A_2}{2!}=1,\qquad \frac{A_3}{3!}=1,\qquad \frac{A_4}{4!}=\frac{18}{24}=\frac{3}{4},\qquad \frac{A_5}{5!}=\frac{12}{120}=\frac{1}{10}.$$
因此当 \(n\ge 5\) 时，递推可以写成
$$\boxed{H_n=H_{n-1}+H_{n-2}+H_{n-3}+\frac{3}{4}H_{n-4}+\frac{1}{10}H_{n-5}.}$$
若 \(n<5\)，同一公式只需把求和截断到 \(j=n\) 即可。这正是 C++、Python 和 Java 实现实际计算的归一化递推。
定义
$$H(x)=\sum_{n\ge 0}H_nx^n.$$
把递推式乘以 \(x^n\)，再对所有 \(n\ge 1\) 求和，有
$$H(x)-1=\left(x+x^2+x^3+\frac{3}{4}x^4+\frac{1}{10}x^5\right)H(x).$$
于是
$$\boxed{H(x)=\frac{1}{1-x-x^2-x^3-\frac{3}{4}x^4-\frac{1}{10}x^5}.}$$
这说明 \(H_n\) 的普通生成函数是一个分母次数为 \(5\) 的有理函数，所以只需要保留前五项状态，算法就足够了。换句话说，递推的有限记忆性质正是由这个分母决定的。
所有计算都在
$$p=10^9+7$$
这个素数模数下进行。因为 \(p\) 是素数，所以 \(1!,2!,3!,4!,5!\) 这些分母都存在模逆元。特别地，
$$\frac{3}{4}\pmod p=3\cdot 4^{p-2}\pmod p,\qquad \frac{1}{10}\pmod p=10^{p-2}\pmod p.$$
实现并不是把分数当作浮点数处理，而是先求出小阶乘的模逆，再把它们与 \(A_j\) 相乘，从而得到完全精确的整数模运算系数。
先用原始递推来计算 \(G(n)\)：
$$G(1)=A_1\binom{1}{1}G(0)=1.$$
$$G(2)=A_1\binom{2}{1}G(1)+A_2\binom{2}{2}G(0)=1\cdot 2\cdot 1+2\cdot 1\cdot 1=4.$$
$$G(3)=A_1\binom{3}{1}G(2)+A_2\binom{3}{2}G(1)+A_3\binom{3}{3}G(0)=12+6+6=24.$$
$$G(4)=A_1\binom{4}{1}G(3)+A_2\binom{4}{2}G(2)+A_3\binom{4}{3}G(1)+A_4\binom{4}{4}G(0)=96+48+24+18=186.$$
$$G(5)=A_1\binom{5}{1}G(4)+A_2\binom{5}{2}G(3)+A_3\binom{5}{3}G(2)+A_4\binom{5}{4}G(1)+A_5\binom{5}{5}G(0)=930+480+240+90+12=1752.$$
再除以 \(n!\)，得到
$$H_0=1,\qquad H_1=1,\qquad H_2=2,\qquad H_3=4,\qquad H_4=\frac{31}{4},\qquad H_5=\frac{73}{5}.$$
这些值完全满足前面的归一化递推，因此既能验证公式，也能验证生成函数展开的前几项。
C++、Python 和 Java 实现都采用同一流程。第一步，预先计算 \(1!,\dots,5!\) 以及它们在模 \(10^9+7\) 下的逆元；由于模数是素数，可以用快速幂来完成。随后，把五个结构常数分别乘以这些逆阶乘，就得到了归一化递推所需的五个模意义系数 \(1,1,1,\frac{3}{4},\frac{1}{10}\)。
第二步，从 \(H_0=1\) 开始递推到 \(H_{10^7}\)。每一个新状态最多只依赖前五个状态，因此单步代价是常数。同时，程序还会维护当前的 \(n!\bmod(10^9+7)\)。循环结束后，把最终的归一化值与 \(10^7!\) 相乘，就恢复出 \(G(10^7)\bmod(10^9+7)\)。
当目标是 \(N=10^7\) 时，每一步最多执行五次模乘和模加，所以总时间复杂度是 \(O(N)\)。小阶乘逆元的预处理只有常数规模开销。当前实现把整个归一化序列表保存到 \(N\)，因此空间复杂度是 \(O(N)\)。不过从递推本身看，只保留最近五项就足够，因此理论上可以用滚动数组把空间降到 \(O(1)\)。
Для каждой неупорядоченной пары помеченных вершин \(1,\dots,n\) выбирается ровно один из четырёх типов ребра: красное ориентированное ребро, синее ориентированное ребро в противоположном направлении, зелёное неориентированное ребро или коричневое неориентированное ребро. Граф называется beautiful, если красные рёбра входят в цикл тогда и только тогда, когда в цикл входят и синие рёбра, а также если не существует треугольника, целиком зелёного или целиком коричневого.
Обозначим через \(G(n)\) число beautiful-графов на \(n\) помеченных вершинах. Нужно найти \(G(10^7)\bmod(10^9+7)\). Полный перебор невозможен, поэтому реализации используют короткую линейную рекурсию, в которой вся специальная структура задачи уже сведена к пяти константам.
Ключевой факт, зашитый в реализации, состоит в том, что всю структурную часть задачи можно представить через пять коэффициентов
$$A_1=1,\qquad A_2=2,\qquad A_3=6,\qquad A_4=18,\qquad A_5=12.$$
После этого задача сводится к преобразованию этих чисел в рекурсию с постоянными коэффициентами.
Для пустого графа полагаем \(G(0)=1\). Структурное разложение, используемое в реализациях, даёт формулу
$$\boxed{G(n)=\sum_{j=1}^{\min(5,n)} A_j \binom{n}{j} G(n-j)\qquad (n\ge 1).}$$
Биномиальный коэффициент выбирает, какие \(j\) меток участвуют в последнем локальном вкладе, а число \(A_j\) считает допустимые локальные шаблоны такого размера. Практически важно то, что появляются только размеры \(1,2,3,4,5\), поэтому ширина рекурсии фиксирована.
Из-за биномиального коэффициента величина \(G(n)\) естественно растёт на масштабе \(n!\). Поэтому реализации переходят к нормированной последовательности
$$H_n=\frac{G(n)}{n!},\qquad H_0=1.$$
Подставляя \(G(n)=n!H_n\) в предыдущую формулу, получаем
$$n!H_n=\sum_{j=1}^{\min(5,n)} A_j \frac{n!}{j!(n-j)!}(n-j)!H_{n-j},$$
и после сокращения \(n!\) остаётся
$$H_n=\sum_{j=1}^{\min(5,n)} \frac{A_j}{j!}H_{n-j}.$$
Это главный шаг упрощения: коэффициенты перестают зависеть от \(n\).
Вычислим нормированные коэффициенты:
$$\frac{A_1}{1!}=1,\qquad \frac{A_2}{2!}=1,\qquad \frac{A_3}{3!}=1,\qquad \frac{A_4}{4!}=\frac{18}{24}=\frac{3}{4},\qquad \frac{A_5}{5!}=\frac{12}{120}=\frac{1}{10}.$$
Следовательно, при \(n\ge 5\)
$$\boxed{H_n=H_{n-1}+H_{n-2}+H_{n-3}+\frac{3}{4}H_{n-4}+\frac{1}{10}H_{n-5}.}$$
Если \(n<5\), сумма просто обрезается на \(j=n\). Именно эту нормированную рекурсию и считают реализации на C++, Python и Java.
Положим
$$H(x)=\sum_{n\ge 0}H_nx^n.$$
Если умножить рекурсию на \(x^n\) и просуммировать по \(n\ge 1\), то получим
$$H(x)-1=\left(x+x^2+x^3+\frac{3}{4}x^4+\frac{1}{10}x^5\right)H(x).$$
Отсюда
$$\boxed{H(x)=\frac{1}{1-x-x^2-x^3-\frac{3}{4}x^4-\frac{1}{10}x^5}.}$$
Эта рациональная форма сразу объясняет, почему достаточно хранить только пять предыдущих значений: знаменатель имеет степень \(5\), значит нормированная последовательность удовлетворяет линейной рекурсии пятого порядка.
Все вычисления ведутся по модулю
$$p=10^9+7,$$
и это простое число. Поэтому любой ненулевой знаменатель до \(5!\) имеет обратный элемент. В частности,
$$\frac{3}{4}\pmod p=3\cdot 4^{p-2}\pmod p,\qquad \frac{1}{10}\pmod p=10^{p-2}\pmod p.$$
Реализации получают эти коэффициенты через модульные обратные к малым факториалам \(1!,2!,3!,4!,5!\), так что никаких вещественных чисел в вычислении нет: используется только точная целочисленная модульная арифметика.
Посчитаем сначала \(G(n)\) по исходной рекурсии:
$$G(1)=A_1\binom{1}{1}G(0)=1.$$
$$G(2)=A_1\binom{2}{1}G(1)+A_2\binom{2}{2}G(0)=1\cdot 2\cdot 1+2\cdot 1\cdot 1=4.$$
$$G(3)=A_1\binom{3}{1}G(2)+A_2\binom{3}{2}G(1)+A_3\binom{3}{3}G(0)=12+6+6=24.$$
$$G(4)=A_1\binom{4}{1}G(3)+A_2\binom{4}{2}G(2)+A_3\binom{4}{3}G(1)+A_4\binom{4}{4}G(0)=96+48+24+18=186.$$
$$G(5)=A_1\binom{5}{1}G(4)+A_2\binom{5}{2}G(3)+A_3\binom{5}{3}G(2)+A_4\binom{5}{4}G(1)+A_5\binom{5}{5}G(0)=930+480+240+90+12=1752.$$
После деления на \(n!\) получаем
$$H_0=1,\qquad H_1=1,\qquad H_2=2,\qquad H_3=4,\qquad H_4=\frac{31}{4},\qquad H_5=\frac{73}{5},$$
и эти значения точно удовлетворяют нормированной рекурсии.
Реализации на C++, Python и Java делают одно и то же. Сначала они заранее вычисляют малые факториалы \(1!,\dots,5!\) и их модульные обратные с помощью быстрого возведения в степень, поскольку модуль прост. Затем пять структурных коэффициентов умножаются на эти обратные факториалы, и получаются модульные коэффициенты рекурсии \(1,1,1,\frac{3}{4},\frac{1}{10}\).
После этого нормированная последовательность строится от \(H_0=1\) до \(H_{10^7}\). Для каждого \(n\) требуется не более пяти предыдущих значений, поэтому стоимость одного шага постоянна. Одновременно поддерживается текущее значение \(n!\bmod(10^9+7)\). После завершения цикла последний нормированный член умножается на \(10^7!\), и так восстанавливается \(G(10^7)\bmod(10^9+7)\).
Для целевого \(N=10^7\) каждое обновление выполняет не более пяти модульных умножений и сложений, значит общее время равно \(O(N)\). Подготовка модульных обратных для малых факториалов даёт только константный накладной расход. Текущие реализации хранят всю таблицу нормированной последовательности до \(N\), поэтому используют \(O(N)\) памяти. Однако сама рекурсия зависит лишь от пяти последних значений, так что при желании память можно сократить до \(O(1)\).
لكل زوج غير مرتب من الرؤوس المعلَّمة \(1,\dots,n\) نختار بالضبط واحدًا من أربعة أنواع للحواف: حافة حمراء موجهة، أو حافة زرقاء موجهة في الاتجاه المعاكس، أو حافة خضراء غير موجهة، أو حافة بنية غير موجهة. يسمى الرسم beautiful إذا ظهرت الحواف الحمراء في دورة إذا وفقط إذا ظهرت الحواف الزرقاء أيضًا في دورة، وإذا لم يوجد أي مثلث كل أضلاعه خضراء أو كل أضلاعه بنية.
لنرمز بعدد الرسوم beautiful على \(n\) رؤوس معلَّمة بالرمز \(G(n)\). المطلوب هو حساب \(G(10^7)\bmod(10^9+7)\). العد المباشر غير ممكن عمليًا، لذلك تعتمد التطبيقات على علاقة خطية قصيرة تختزل البنية الخاصة بالمسألة في خمس ثوابت فقط.
الحقيقة الأساسية التي تعتمد عليها التطبيقات هي أن الجزء التركيبي الخاص بالمسألة يمكن تلخيصه في المعاملات الخمسة الآتية:
$$A_1=1,\qquad A_2=2,\qquad A_3=6,\qquad A_4=18,\qquad A_5=12.$$
وبعد معرفة هذه القيم، يصبح العمل الأساسي هو تحويلها إلى علاقة عودية ذات معاملات ثابتة يمكن تنفيذها بدقة تحت الحساب المعياري.
للرسم الفارغ نأخذ \(G(0)=1\). والتحليل البنيوي المضمَّن في التطبيقات يعطي الصيغة
$$\boxed{G(n)=\sum_{j=1}^{\min(5,n)} A_j \binom{n}{j} G(n-j)\qquad (n\ge 1).}$$
المعامل الثنائي \(\binom{n}{j}\) يحدد أي \(j\) من الرؤوس تدخل في المساهمة الأخيرة، بينما يحسب \(A_j\) عدد الأنماط المحلية المسموح بها من هذا الحجم. والنقطة العملية الأهم هي أن الأحجام الممكنة محصورة في \(1,2,3,4,5\)، ولذلك تبقى سعة العلاقة العودية ثابتة.
بسبب وجود المعامل الثنائي، ينمو \(G(n)\) طبيعيًا على مقياس \(n!\). لذلك تقوم التطبيقات بالتطبيع عبر
$$H_n=\frac{G(n)}{n!},\qquad H_0=1.$$
إذا عوضنا \(G(n)=n!H_n\) في العلاقة السابقة نحصل على
$$n!H_n=\sum_{j=1}^{\min(5,n)} A_j \frac{n!}{j!(n-j)!}(n-j)!H_{n-j},$$
وبعد اختصار \(n!\) تصبح الصيغة
$$H_n=\sum_{j=1}^{\min(5,n)} \frac{A_j}{j!}H_{n-j}.$$
هذه هي الخطوة الحاسمة، لأن معاملات العلاقة لم تعد تعتمد على \(n\).
نحسب الآن القيم المطبَّعة للمعاملات:
$$\frac{A_1}{1!}=1,\qquad \frac{A_2}{2!}=1,\qquad \frac{A_3}{3!}=1,\qquad \frac{A_4}{4!}=\frac{18}{24}=\frac{3}{4},\qquad \frac{A_5}{5!}=\frac{12}{120}=\frac{1}{10}.$$
إذًا عندما \(n\ge 5\) نحصل على
$$\boxed{H_n=H_{n-1}+H_{n-2}+H_{n-3}+\frac{3}{4}H_{n-4}+\frac{1}{10}H_{n-5}.}$$
أما إذا كان \(n<5\) فنكتفي بقطع المجموع عند \(j=n\). وهذه بالضبط هي العلاقة المطبعَّة التي تنفذها تطبيقات C++ وPython وJava.
نعرف
$$H(x)=\sum_{n\ge 0}H_nx^n.$$
بضرب العلاقة في \(x^n\) ثم الجمع على جميع \(n\ge 1\) نحصل على
$$H(x)-1=\left(x+x^2+x^3+\frac{3}{4}x^4+\frac{1}{10}x^5\right)H(x).$$
ومن ثم
$$\boxed{H(x)=\frac{1}{1-x-x^2-x^3-\frac{3}{4}x^4-\frac{1}{10}x^5}.}$$
هذه الصيغة الكسرية تفسر مباشرة سبب الاكتفاء بخمس قيم سابقة فقط: مقام دالة التوليد درجته \(5\)، ولذلك تحقق المتتالية المطبعَّة علاقة خطية من الرتبة الخامسة.
كل الحسابات تتم بترديد
$$p=10^9+7,$$
وهو عدد أولي. لذلك فكل مقام غير صفري حتى \(5!\) يملك معكوسًا ضربيًا معياريًا. وبخاصة
$$\frac{3}{4}\pmod p=3\cdot 4^{p-2}\pmod p,\qquad \frac{1}{10}\pmod p=10^{p-2}\pmod p.$$
التطبيقات لا تتعامل مع هذه الكسور كأعداد عشرية، بل تحسب معكوسات العوامل الصغيرة \(1!,2!,3!,4!,5!\) ثم تضرب بها، ولذلك تبقى العملية كلها ضمن الحساب الصحيح المعياري الدقيق.
لنحسب أولًا \(G(n)\) من العلاقة الأصلية:
$$G(1)=A_1\binom{1}{1}G(0)=1.$$
$$G(2)=A_1\binom{2}{1}G(1)+A_2\binom{2}{2}G(0)=1\cdot 2\cdot 1+2\cdot 1\cdot 1=4.$$
$$G(3)=A_1\binom{3}{1}G(2)+A_2\binom{3}{2}G(1)+A_3\binom{3}{3}G(0)=12+6+6=24.$$
$$G(4)=A_1\binom{4}{1}G(3)+A_2\binom{4}{2}G(2)+A_3\binom{4}{3}G(1)+A_4\binom{4}{4}G(0)=96+48+24+18=186.$$
$$G(5)=A_1\binom{5}{1}G(4)+A_2\binom{5}{2}G(3)+A_3\binom{5}{3}G(2)+A_4\binom{5}{4}G(1)+A_5\binom{5}{5}G(0)=930+480+240+90+12=1752.$$
وبالقسمة على \(n!\) نحصل على
$$H_0=1,\qquad H_1=1,\qquad H_2=2,\qquad H_3=4,\qquad H_4=\frac{31}{4},\qquad H_5=\frac{73}{5},$$
وهذه القيم تحقق تمامًا العلاقة المطبعة المذكورة أعلاه.
تتبع تطبيقات C++ وPython وJava الخطة نفسها. في البداية تُحسب القيم الصغيرة \(1!,\dots,5!\) ومعكوساتها المعيارية باستعمال الأس السريع لأن المود أولي. بعد ذلك تُضرب الثوابت الخمس في معكوسات العوامل المناسبة للحصول على معاملات العلاقة العودية \(1,1,1,\frac{3}{4},\frac{1}{10}\) بصيغتها المعيارية.
ثم تبني الشيفرة المتتالية المطبعة من \(H_0=1\) حتى \(H_{10^7}\). في كل خطوة نحتاج إلى خمسة حدود سابقة كحد أقصى، لذلك تكون كلفة الانتقال ثابتة. وبالتوازي مع ذلك يُحدَّث أيضًا العامل الجاري \(n!\bmod(10^9+7)\). وبعد انتهاء الحلقة، يُضرب الحد المطبع الأخير في \(10^7!\) لاسترجاع \(G(10^7)\bmod(10^9+7)\).
عند الهدف \(N=10^7\)، تتطلب كل خطوة ما لا يزيد على خمس عمليات ضرب وجمع معيارية، لذا يكون الزمن الكلي \(O(N)\). أما حساب المعكوسات المعيارية للعوامل الصغيرة فهو كلفة ثابتة فقط. التطبيقات الحالية تخزن الجدول الكامل للمتتالية المطبعة حتى \(N\)، ولذلك تستخدم \(O(N)\) ذاكرة. لكن العلاقة نفسها لا تحتاج إلا إلى آخر خمس قيم، وبالتالي يمكن نظريًا تخفيض الذاكرة إلى \(O(1)\) بنافذة منزلقة.