Detailed mathematical approach

Problem Summary

On each square of an \(n\times n\) board, one centaur is placed at one of the four corners of that square. A centaur attacks as a king or a knight, so a placement is valid only when no two chosen corners are separated by a king move or a knight move. If \(C(n)\) denotes the number of valid boards of size \(n\), the required quantity is

$$\sum_{k=2}^{90} C(F_k) \pmod{100000007},$$

where \(F_1=F_2=1\) and \(F_k=F_{k-1}+F_{k-2}\).

Mathematical Approach

The implementations use a two-level strategy. First, they model the board exactly by row states and a transfer matrix, which gives rigorous small-board checkpoints. Then they use the closed congruence that makes the huge Fibonacci boards feasible.

Step 1: Encode Each Square by a Corner State

Scale the board by a factor of \(2\) in both directions. Then the four corners of one square can be written as

$$L_0=(0,0),\qquad L_1=(0,1),\qquad R_0=(1,0),\qquad R_1=(1,1).$$

If the square in column \(c\) and row \(r\) uses the corner \((\xi,\eta)\in\{0,1\}^2\), its centaur sits at

$$\bigl(2c+\xi,\ 2r+\eta\bigr).$$

Two centaurs attack if the coordinate difference is a king move,

$$\max(|\Delta x|,|\Delta y|)=1,$$

or a knight move,

$$\{|\Delta x|,|\Delta y|\}=\{1,2\}.$$

This is exactly the geometric test used by the implementation.

Step 2: Derive the Shape of a Valid Row

Now inspect two neighboring squares in the same row. Checking the \(16\) ordered pairs of corner choices shows that a legal row can only stay on one fixed left-corner type and then, at most once, switch to one fixed right-corner type. Therefore every valid row has the form

$$\bigl(\underbrace{L_\alpha,\dots,L_\alpha}_{k\text{ entries}},\underbrace{R_\beta,\dots,R_\beta}_{n-k\text{ entries}}\bigr),\qquad \alpha,\beta\in\{0,1\},\ 0\le k\le n.$$

When \(k=0\), the whole row is \(R_\beta\); when \(k=n\), the whole row is \(L_\alpha\). Hence the number of admissible row states is

$$2+4(n-1)+2=4n.$$

This explains why the exact state space is small enough for direct transfer counting on small boards.

Step 3: Build the Transfer Matrix Between Adjacent Rows

Two row states are compatible if no pair of centaurs attacks across consecutive rows. Because the move range is at most a knight move, it is enough to check

$$\text{same-column pairs}\qquad\text{and}\qquad\text{diagonal pairs one column apart}.$$

Let \(T_n\) be the \(4n\times 4n\) matrix whose entry is \(1\) when two row states are compatible and \(0\) otherwise. If \(\mathbf{1}\) is the all-ones vector, then the exact count of legal boards is

$$C(n)=\mathbf{1}^{\mathsf T} T_n^{\,n-1}\mathbf{1}.$$

This is an exact formula for every \(n\). It yields the checkpoint values

$$C(1)=4,\qquad C(2)=25,\qquad C(3)=120,\qquad C(10)=1477721.$$

Step 4: Use the Closed Congruence for Large Boards

The Fibonacci boards are far too large for transfer-matrix exponentiation, so the implementations use the closed congruence

$$C(n)\equiv 8\binom{2n}{n}-(3n^2+2n+7)\pmod{p},\qquad p=100000007.$$

Thus the row-transfer combinatorics compresses modulo \(p\) to a central binomial term plus a quadratic correction. Once this congruence is available, the whole problem reduces to evaluating \(\binom{2n}{n}\bmod p\) for very large \(n\).

Step 5: Evaluate the Central Binomial Coefficient with Lucas' Theorem

Because \(p\) is prime, Lucas' theorem applies. Write

$$N=\sum_{t\ge 0} N_t p^t,\qquad K=\sum_{t\ge 0} K_t p^t$$

in base \(p\). Then

$$\binom{N}{K}\equiv \prod_{t\ge 0}\binom{N_t}{K_t}\pmod{p}.$$

For this problem we set

$$N=2n,\qquad K=n.$$

Each digit-level binomial is computed by

$$\binom{a}{b}\equiv a!\,(b!)^{-1}\,((a-b)!)^{-1}\pmod{p},\qquad 0\le b\le a \lt p,$$

and the inverse is obtained from Fermat's little theorem:

$$x^{-1}\equiv x^{p-2}\pmod{p}.$$

Step 6: Sum Over Fibonacci Board Sizes

The Fibonacci sequence is generated up to \(F_{90}\). For each \(k=2,3,\dots,90\), the implementation evaluates \(C(F_k)\bmod p\) and accumulates the result modulo \(p\):

$$\sum_{k=2}^{90} C(F_k)\pmod{p}.$$

The terms are independent, which is why the C++ implementation can evaluate them in parallel while the Python and Java implementations perform the same arithmetic sequentially.

Worked Example: \(n=10\)

Since \(2n=20 \lt p\), Lucas' theorem has only one base-\(p\) digit here, so the central binomial coefficient is the ordinary one:

$$\binom{20}{10}=184756.$$

The correction term is

$$3n^2+2n+7=3\cdot 10^2+2\cdot 10+7=327.$$

Therefore

$$C(10)\equiv 8\cdot 184756-327=1477721\pmod{100000007},$$

which matches the checked sample value.

How the Code Works

The C++, Python, and Java implementations first prepare modular arithmetic for the prime \(p=100000007\). They precompute factorial values at block boundaries, so a later query for \(n!\bmod p\) starts from the nearest stored block product and multiplies only the short tail inside that block. This keeps repeated small-binomial evaluations efficient.

For large board sizes, the implementation applies Lucas' theorem to \(\binom{2n}{n}\), computes the correction term \(3n^2+2n+7\) modulo \(p\), combines them as \(8\binom{2n}{n}-(3n^2+2n+7)\), and then sums these values over \(F_2,F_3,\dots,F_{90}\).

The C++ implementation also performs self-checks before the final sum: exact transfer-matrix counts for small boards, consistency checks for small binomial coefficients against Pascal's triangle, and the sample values \(C(1)=4\), \(C(2)=25\), and \(C(10)=1477721\). Those checks ensure that the exact model and the modular formula agree on all calibrated cases.

Complexity Analysis

For a board of size \(m\), the exact validation model has \(4m\) row states. Building all row-to-row compatibilities requires \(O(m)\) work per state pair, so the transition construction is \(O(m^3)\), and the dynamic program over \(m\) rows is of the same order. This part is used only for small checkpoints, so its cost is negligible.

The main computation has a one-time preprocessing cost of \(O(p)\) to build factorial products at block boundaries, with memory \(O(p/B)\) when the block size is \(B\). After that, one Lucas digit costs a few tail multiplications of length at most \(B\) plus one modular inverse in \(O(\log p)\). Therefore one evaluation of \(C(n)\) costs

$$O\bigl(\log_p n\cdot (B+\log p)\bigr),$$

and the final Fibonacci sum uses this only \(89\) times.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=554
2. Lucas' theorem: Wikipedia - Lucas' theorem
3. Transfer-matrix method: Wikipedia - Transfer-matrix method
4. Central binomial coefficient: Wikipedia - Central binomial coefficient
5. Fibonacci number: Wikipedia - Fibonacci number