import typing


def _de_bruijn(k: int, n: int) -> typing.List[int]:
    """Generate a De Bruijn sequence.

    This is a piece of mathematical heavy machinery needed for O(1) ctz on
    integers of bounded size. The algorithm is adapted from chapter 7 of
    Frank Ruskey's "Combinatorial Generation".

    Args:
        k: The number of symbols in the alphabet. Must be > 1.
        n: The length of subsequences. Should be >= 0.

    Returns:
        The De Bruijn sequence, as a list of integer indices.

    >>> _de_bruijn(2, 3)
    [0, 0, 0, 1, 0, 1, 1, 1]
    >>> _de_bruijn(4, 2)
    [0, 0, 1, 0, 2, 0, 3, 1, 1, 2, 1, 3, 2, 2, 3, 3]
    >>> _de_bruijn(2, 5)
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1]
    """
    a: typing.List[int] = [0] * k * n
    sequence: typing.List[int] = []

    def gen(t: int, p: int):
        if t > n:
            if n % p == 0:
                sequence.extend(a[1:p + 1])
        else:
            a[t] = a[t - p]
            gen(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                gen(t + 1, t)

    gen(1, 1)
    return sequence