Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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.

Step 1: Start from the raw counting recurrence

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.

Step 2: Remove the factorial growth

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\).

Step 3: Read off the constant coefficients

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.

Step 4: Turn the recurrence into a generating function

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\).

Step 5: Interpret the fractions modulo \(10^9+7\)

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.

Worked Example: The first few values

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.

How the Code Works

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)\).

Complexity Analysis

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.

Footnotes and References

1. Problem page: Project Euler 857
2. Recurrence relation: Wikipedia - Recurrence relation
3. Generating function: Wikipedia - Generating function
4. Binomial coefficient: Wikipedia - Binomial coefficient
5. Modular multiplicative inverse: Wikipedia - Modular multiplicative inverse