594. 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).
Constraints - `1 ≤ n ≤ 10^18` - `1 ≤ k ≤ 1000000`
Input
One line containing two integers n and k, the number of houses and colours.
Output
Print one integer, the number of valid paintings, modulo 1000000007.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.