Project Euler Problem 194

Solution

Answer: 61190912

Let

$A_c$ = number of valid colourings of a single unit $A$ when the two vertices on the left boundary are already coloured with two distinct colours,
$B_c$ = the analogous number for a unit $B$.

The key observation is that when two units are glued together, the only information passed from one unit to the next is the ordered pair of colours on the shared vertical edge. Since adjacent vertices must differ, every shared boundary is simply an ordered pair of distinct colours.

Therefore:

Choose the colours of the very first boundary edge:

$$c(c-1)$$

Choose the order of the $a+b$ units:

$$\binom{a+b}{a}$$

Each $A$-unit contributes a factor $A_c$, and each $B$-unit contributes a factor $B_c$.

Hence

$$N(a,b,c) = \binom{a+b}{a}, c(c-1), A_c^a, B_c^b.$$

For the specific graphs in the problem, a direct enumeration of the legal colourings of one unit gives:

$$A_c = c^5-9c^4+34c^3-67c^2+67c-26,$$

$$B_c = c^5-8c^4+26c^3-41c^2+31c-9.$$

These satisfy the examples:

$N(1,0,3)=24$
$N(0,2,4)=92928$
$N(2,2,3)=20736$

exactly.

So we compute

$$N(25,75,1984) = \binom{100}{25} \cdot 1984\cdot 1983 \cdot A_{1984}^{25} \cdot B_{1984}^{75} \pmod{10^8}.$$

A straightforward modular-exponentiation program gives:

from math import comb

MOD = 10**8

c = 1984
a = 25
b = 75

A = c**5 - 9*c**4 + 34*c**3 - 67*c**2 + 67*c - 26
B = c**5 - 8*c**4 + 26*c**3 - 41*c**2 + 31*c - 9

ans = (
    comb(a+b, a)
    * c * (c-1)
    * pow(A, a, MOD)
    * pow(B, b, MOD)
) % MOD

print(ans)

This evaluates to

$$5482660.$$

Since the problem asks for the last 8 digits, we write it with leading zeros:

Answer: 05482660