Colouring a Row Without a Table
A row of n houses is to be painted, each in one of k colours, so that no two ADJACENT
houses share a colour. Count the ways, modulo 1000000007.
3 houses, 3 colours -> 12
5 houses, 1 colour -> 0 the second house has nothing left to use
1 house, 5 colours -> 5
## Start with the table, then read it
The obvious state is dp[i][c], the number of ways to paint the first i houses with house
i in colour c. That is a real dynamic program, and it is the one used in problems 411 and
445, where the colours carry costs or a longer constraint.
Here it collapses. Every colour is interchangeable, so dp[i][c] does not depend on c at
all, and
dp[i] = (k - 1) * dp[i-1]
for every house after the first. A recurrence that multiplies by a constant is a geometric sequence, so
answer = k * (k-1)^(n-1)
## Reading it directly
The first house takes any of k colours. Every later house takes any colour EXCEPT its left
neighbour's, which is k - 1 choices, and that count does not depend on which colour the
neighbour actually used.
Both routes are worth doing. The first shows how to notice a collapse from the recurrence; the second shows that the answer was available without writing one.
## Why a table is impossible here
n goes up to 10^18. There is no loop over houses at any speed. The closed form has to be
evaluated with repeated squaring, in about 60 multiplications.
## Where the edges are
k = 1: the answer is 1 when n = 1, and 0 for every larger n, since 0^(n-1) is 0. The
formula handles it, provided 0^0 is treated as 1, which is what every standard modular power
routine does.
n = 1: the answer is k, with no exponent involved.
These two are the whole difficulty of the problem, and both are in the tests.
## Overflow
Reduce k before multiplying, and use a multiplication that stays exact: two values below
10^9 reach nearly 10^18, which is fine in signed 64 bits and not exact in a double.
n itself reaches 10^18 and must be read into a 64 bit integer. In JavaScript an ordinary
number loses precision above 2^53, so read it as a big integer.
## Cost
Time O(log n). Space O(1).