Problem 194: Coloured Configurations

Mathematical Development

Theorem 1. (Chromatic Polynomial of $K_m$.) The number of proper $n$-colourings of the complete graph $K_m$ is the falling factorial

Proof. In a proper colouring of $K_m$, every pair of vertices must receive distinct colours. Assign colours greedily: the first vertex has $n$ choices, the second $n-1$, …, the $m$-th vertex has $n-m+1$ choices. Since $K_m$ has all edges, every greedy assignment is valid and every valid colouring arises exactly once. $\square$

Theorem 2. (Clique Separator Theorem.) If $G = G_1 \cup G_2$ where $G_1 \cap G_2$ is a clique $K_s$, then

Proof. Let $S = V(G_1) \cap V(G_2)$ with $|S| = s$, and $S$ induces a clique $K_s$ in both $G_1$ and $G_2$. For any proper colouring $c$ of $G$, the restriction $c|_S$ is a proper colouring of $K_s$. Conversely, for a fixed proper colouring $c_S$ of $K_s$:

• The number of extensions of $c_S$ to all of $G_1$ is $P(G_1, n) / P(K_s, n)$, since every colouring of $G_1$ restricts to some colouring of $S$, and by symmetry (all colourings of $K_s$ are equivalent under colour permutation in terms of extension count), each colouring of $S$ has exactly $P(G_1, n) / P(K_s, n)$ extensions.

• Similarly, the number of extensions of $c_S$ to $G_2$ is $P(G_2, n) / P(K_s, n)$.

Since $V(G_1) \setminus S$ and $V(G_2) \setminus S$ are disjoint and share no edges, the extensions are independent. Summing over all $P(K_s, n)$ colourings of $S$:

$\square$

Lemma 1. (Application.) For $G = K_a \cup K_b$ with $K_a \cap K_b = K_2$ (a shared edge):

Proof. By Theorems 1 and 2 with $s = 2$:

Since $n^{\underline{a}} = n(n-1) \cdot (n-2)^{\underline{a-2}}$, the factor $n(n-1)$ cancels exactly. $\square$

Editorial

Fix the colours on the leftmost vertical edge first. There are c(c-1) ordered ways to do that, and once those two boundary colours are fixed, the number of valid colourings of a single unit depends only on whether the unit is of type A or type B. Enumerating the five remaining vertices of one unit gives two polynomials:

Every time another unit is glued onto the chain, the new left boundary is again just an ordered pair of distinct colours, so the same single-unit count applies again. That means a configuration with a copies of A and b copies of B contributes

for any fixed order of the units. The only remaining combinatorics is choosing which a of the a+b positions contain unit A, giving the binomial factor \binom{a+b}{a}. The final computation is therefore one binomial coefficient and two modular exponentiations.

Pseudocode

Set c = 1984, a = 25, b = 75, and MOD = 10^8.
Evaluate the single-unit colouring polynomials A(c) and B(c).
Compute the binomial factor C(a + b, a).

Start with the c(c-1) choices for the colours on the first vertical edge.
Multiply by A(c)^a and B(c)^b.
Multiply by C(a + b, a) to account for the placements of the A-units.
Take the result modulo MOD and return it.

Complexity Analysis

• Time: $O(a + b)$ modular multiplications. For $(a, b) = (25, 75)$, this is 98 multiplications.
• Space: $O(1)$.

Answer

#include <cassert>
#include <iostream>
#include <vector>

using namespace std;

unsigned long long unit_a_count(unsigned long long c) {
    return c * c * c * c * c - 9 * c * c * c * c + 34 * c * c * c - 69 * c * c + 77 * c - 38;
}

unsigned long long unit_b_count(unsigned long long c) {
    return c * c * c * c * c - 8 * c * c * c * c + 27 * c * c * c - 50 * c * c + 52 * c - 24;
}

unsigned long long exact_binomial_small(int n, int k) {
    if (k > n - k) {
        k = n - k;
    }
    unsigned long long result = 1;
    for (int i = 1; i <= k; ++i) {
        result = result * static_cast<unsigned long long>(n - k + i) / static_cast<unsigned long long>(i);
    }
    return result;
}

unsigned long long pow_ull(unsigned long long base, int exp) {
    unsigned long long result = 1;
    while (exp > 0) {
        if (exp & 1) {
            result *= base;
        }
        base *= base;
        exp >>= 1;
    }
    return result;
}

unsigned long long configuration_count_small(int a_units, int b_units, unsigned long long colors) {
    return colors * (colors - 1) * exact_binomial_small(a_units + b_units, a_units)
        * pow_ull(unit_a_count(colors), a_units) * pow_ull(unit_b_count(colors), b_units);
}

unsigned long long mod_pow(unsigned long long base, int exp, unsigned long long mod) {
    unsigned long long result = 1 % mod;
    unsigned long long value = base % mod;
    while (exp > 0) {
        if (exp & 1) {
            result = (result * value) % mod;
        }
        value = (value * value) % mod;
        exp >>= 1;
    }
    return result;
}

int prime_exponent_in_factorial(int n, int p) {
    int exponent = 0;
    while (n > 0) {
        n /= p;
        exponent += n;
    }
    return exponent;
}

unsigned long long binomial_mod_100_25(unsigned long long mod) {
    const int n = 100;
    const int k = 25;
    const int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
        53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

    unsigned long long result = 1;
    for (int p : primes) {
        int exponent = prime_exponent_in_factorial(n, p)
            - prime_exponent_in_factorial(k, p)
            - prime_exponent_in_factorial(n - k, p);
        if (exponent > 0) {
            result = result * mod_pow(static_cast<unsigned long long>(p), exponent, mod) % mod;
        }
    }
    return result;
}

int main() {
    const unsigned long long mod = 100000000ULL;
    const unsigned long long colors = 1984;

    assert(configuration_count_small(1, 0, 3) == 24ULL);
    assert(configuration_count_small(0, 2, 4) == 92928ULL);
    assert(configuration_count_small(2, 2, 3) == 20736ULL);

    unsigned long long answer = colors % mod;
    answer = answer * ((colors - 1) % mod) % mod;
    answer = answer * binomial_mod_100_25(mod) % mod;
    answer = answer * mod_pow(unit_a_count(colors) % mod, 25, mod) % mod;
    answer = answer * mod_pow(unit_b_count(colors) % mod, 75, mod) % mod;

    assert(answer == 61190912ULL);
    cout << answer << '\n';
    return 0;
}

"""
Project Euler Problem 194: Coloured Configurations

Count colourings of chains made from 25 A-units and 75 B-units, modulo 10^8.
"""

from math import comb


def unit_a_count(colors):
    c = colors
    return c**5 - 9 * c**4 + 34 * c**3 - 69 * c**2 + 77 * c - 38


def unit_b_count(colors):
    c = colors
    return c**5 - 8 * c**4 + 27 * c**3 - 50 * c**2 + 52 * c - 24


def configuration_count(a_units, b_units, colors):
    return (
        colors
        * (colors - 1)
        * comb(a_units + b_units, a_units)
        * unit_a_count(colors) ** a_units
        * unit_b_count(colors) ** b_units
    )


def solve():
    mod = 10**8
    return configuration_count(25, 75, 1984) % mod


if __name__ == "__main__":
    assert configuration_count(1, 0, 3) == 24
    assert configuration_count(0, 2, 4) == 92928
    assert configuration_count(2, 2, 3) == 20736
    answer = solve()
    assert answer == 61190912
    print(answer)