Detailed mathematical approach

Problem Summary

For each \(n\), the solution evaluates a quantity \(M(n)\) and then forms

$S(N)=\sum_{n=2}^{N} M(n)\pmod{10^9+7}.$

The counting argument is encoded by cyclic words of length \(2n\) over the alphabet \(\{0,1,2\}\). Symbol \(0\) means that no special local structure is forced at that place, while \(1\) and \(2\) are the two oriented marker types used by the inclusion-exclusion step. The hard part is therefore to count which cyclic marker patterns are legal, and then attach the multiplicative weight that each legal pattern contributes.

Mathematical Approach

Let \(C_{L,k}\) denote the number of cyclic words \(a_1,\dots,a_L\in\{0,1,2\}\) with exactly \(k\) nonzero symbols, where indices are read modulo \(L\), and which satisfy the local restrictions

$a_{i-1}\neq 0 \Rightarrow a_i=0,$

$a_{i-2}=2 \Rightarrow a_i\neq 1.$

Only even lengths \(L=2n\) are used in the final answer.

Step 1: Encode the Inclusion-Exclusion Data

The implementation rewrites the original counting problem as a signed sum over sets of forced local structures. Each chosen structure is recorded by placing a nonzero marker in one position of a cyclic word. There are two oriented types, represented by \(1\) and \(2\), so a configuration with \(k\) chosen structures becomes a cyclic word with exactly \(k\) nonzero symbols.

The two local rules above say exactly which selections can coexist. The first rule forbids two neighboring nonzero markers, so chosen structures cannot overlap immediately. The second rule removes one more forbidden interaction at distance two: a marker of type \(2\) cannot be followed two steps later by a marker of type \(1\).

Step 2: Count Legal Marker Cycles

Because the legality of a new symbol depends only on the previous two symbols, a transfer-state dynamic program is enough. Fix the first two symbols \((a_1,a_2)\), and let

$D(\ell,s,t,k)$

be the number of length-\(\ell\) prefixes whose first two symbols are fixed, whose last two symbols are \((s,t)\), which already satisfy every internal local rule, and which contain exactly \(k\) nonzero entries.

If a new symbol \(u\in\{0,1,2\}\) is appended, the transition is legal precisely when

$t\neq 0 \Rightarrow u=0,$

$s=2 \Rightarrow u\neq 1.$

When \(u\neq 0\), the counter \(k\) increases by \(1\). This is why the implementations only need a tiny state space for the last two symbols and a second dimension for the number of nonzero markers.

Step 3: Enforce Cyclic Closure

A path counted by the DP is not yet a valid cycle. When the current last two symbols are \((x,y)\) and the fixed initial pair is \((a,b)\), the wrap-around conditions are

$y\neq 0 \Rightarrow a=0,$

$x=2 \Rightarrow a\neq 1,$

$y=2 \Rightarrow b\neq 1.$

These are exactly the same local restrictions, but applied across the end of the cycle. Summing all DP states that satisfy these three boundary checks gives \(C_{L,k}\).

Step 4: Convert a Legal Pattern into a Contribution to \(M(n)\)

Once a valid cyclic marker pattern of length \(2n\) with \(k\) nonzero positions is fixed, the formula used by the implementation factors into four independent pieces.

First, the pattern itself contributes \(C_{2n,k}\).

Second, the \(k\) chosen local structures must be matched injectively with \(k\) distinct labeled objects among \(n\), which gives the falling factorial

$ (n)_k=\frac{n!}{(n-k)!}. $

Third, each chosen position has \(4\) concrete realizations, so there is a factor \(4^k\).

Fourth, after those \(k\) forced structures are removed, there remain \(2n-2k\) free items in each of two independent orders, contributing

$((2n-2k)!)^2.$

Inclusion-exclusion supplies the sign \((-1)^k\), and a final global factor \(2\) remains. Therefore

$M(n)=2\sum_{k=0}^{n}(-1)^k C_{2n,k}(n)_k 4^k ((2n-2k)!)^2 \pmod{10^9+7}.$

Step 5: Sum All \(M(n)\)

After \(M(n)\) has been evaluated for every \(2\le n\le N\), the required result is simply

$S(N)=\sum_{n=2}^{N} M(n)\pmod{10^9+7}.$

The implementations therefore precompute the pattern counts once, precompute the needed factorial data once, and then sweep through \(n=2,3,\dots,N\).

Worked Example: \(n=2\)

For \(n=2\) we need length \(4\) cyclic words. The legal counts are easy to derive directly.

For \(k=0\), only \(0000\) is possible, so \(C_{4,0}=1\).

For \(k=1\), choose one of the \(4\) positions and choose symbol \(1\) or \(2\), so \(C_{4,1}=8\).

For \(k=2\), the two nonzero symbols must occupy alternating positions, either \(\{1,3\}\) or \(\{2,4\}\). On each alternating pair, the distance-two rule forbids \((2,1)\) in either direction, so only \((1,1)\) and \((2,2)\) survive. Hence \(C_{4,2}=4\).

Substituting into the formula gives

$M(2)=2\left(1\cdot 1\cdot 1\cdot (4!)^2 - 8\cdot 2\cdot 4\cdot (2!)^2 + 4\cdot 2\cdot 16\cdot (0!)^2\right).$

That is

$M(2)=2(576-256+128)=896,$

which matches the checkpoint used by the implementation.

How the Code Works

The C++, Python, and Java implementations follow the same pipeline. They first build the full table \(C_{L,k}\) for every \(L\le 2N\) and \(k\le N\) by running the last-two-symbol DP for each admissible starting pair. They then precompute factorials, inverse factorials, and powers of \(4\) modulo \(10^9+7\).

For each \(n\), the implementation reads the already computed row \(C_{2n,k}\), evaluates the alternating sum for \(M(n)\), multiplies by the outer factor \(2\), and adds the result into the running total for \(S(N)\). The checkpoints embedded in the implementation include

$M(2)=896,\qquad M(3)=890880,\qquad M(10)=170717180,$

and

$S(10)=399291975.$

Complexity Analysis

Let the final limit be \(N\). The pattern-count DP considers \(O(N)\) lengths, a constant number of last-two-symbol states, and up to \(O(N)\) values of \(k\), so building all \(C_{L,k}\) costs \(O(N^2)\) time. The factorial, inverse-factorial, and power tables cost \(O(N)\) time and memory. Evaluating all alternating sums for \(M(2),\dots,M(N)\) is another \(O(N^2)\) pass. Therefore the overall complexity is

$O(N^2)\text{ time and }O(N^2)\text{ memory}.$

Footnotes and References

1. Problem page: https://projecteuler.net/problem=746
2. Inclusion-exclusion principle: Wikipedia - Inclusion-exclusion principle
3. Dynamic programming: Wikipedia - Dynamic programming
4. Finite-state machine: Wikipedia - Finite-state machine
5. Factorial: Wikipedia - Factorial