Paint Fence Problem

You are tasked with painting a fence with a given number of posts and a limited number of colors. The goal is to find the total number of ways to paint the fence such that no more than two adjacent posts have the same color. This problem is a classic example of dynamic programming, often used to illustrate combinatorial counting problems.

Problem Description

You have a fence with n posts and k colors available. You need to paint each post with one of the k colors. The constraint is that no more than two adjacent posts can have the same color. This means you cannot have three or more consecutive posts painted with the same color.

What needs to be achieved: Calculate the total number of distinct ways to paint the fence according to the given constraint.

Key requirements:

Each post must be painted.
Only k colors are available.
No more than two adjacent posts can share the same color.

Expected behavior: The function should return an integer representing the total number of valid ways to paint the fence.

Important edge cases to consider:

What happens if n is 0 or 1?
What happens if k is 1?

Examples

Example 1:

Input: n = 3, k = 2
Output: 6
Explanation:
Let the colors be R (Red) and B (Blue).
Valid ways:
1. RBR
2. RRG
3. GRR
4. GRB
5. BRR
6. BRB
(Note: The example above uses G, but it should be R or B. Let's correct it assuming R and B are the only colors)

Corrected Valid ways for n=3, k=2 (Colors R, B):
1. RBR
2. RRG -> Should be RRB (assuming R and G were a typo and meant R and B)
3. GRR -> Should be BRR
4. GRB -> Should be BRB
5. BRR
6. BRB

Let's re-list with R and B only:
1. RBR
2. RRG - Invalid (assumed typo, should be RRB)
3. GRR - Invalid (assumed typo, should be BRR)
4. GRB - Invalid (assumed typo, should be BRB)

Valid ways using R and B for n=3, k=2:
1. RBR
2. RBB
3. BRB
4. BRR
5. RRB
6. BBR

Let's trace the logic for n=3, k=2:
Post 1: Can be R or B (2 options)
Post 2: Can be R or B (2 options)
Post 3:
  - If Post 1 and Post 2 are different (e.g., RB): Post 3 can be R or B (2 options)
  - If Post 1 and Post 2 are the same (e.g., RR): Post 3 must be different from Post 2 (1 option - B)
  - If Post 1 and Post 2 are the same (e.g., BB): Post 3 must be different from Post 2 (1 option - R)

Let's use a more structured approach:

n=1: R, B (2 ways)
n=2: RR, RB, BR, BB (4 ways)
n=3:
  - If post 2 is different from post 1: (e.g., RB)
    - Post 3 can be R or B.
    - For RB: RBR, RBB
  - If post 2 is the same as post 1: (e.g., RR)
    - Post 3 must be different from post 2.
    - For RR: RRB

Let's consider the last two posts:
Let same[i] be the number of ways to paint the first i posts such that the i-th and (i-1)-th posts have the SAME color.
Let diff[i] be the number of ways to paint the first i posts such that the i-th and (i-1)-th posts have DIFFERENT colors.

For n=1:
same[1] = 0 (cannot have two same colors with only one post)
diff[1] = k (any color is valid for the first post, and it's trivially different from a non-existent previous post)

For n=2:
same[2]: The first post can be any color (k options). The second post must be the same as the first (1 option). So, same[2] = k * 1 = k.
diff[2]: The first post can be any color (k options). The second post must be different from the first (k-1 options). So, diff[2] = k * (k-1).
Total for n=2 = same[2] + diff[2] = k + k*(k-1) = k + k^2 - k = k^2. (This is correct for k=2: 2*2 = 4 ways)

For n=3:
same[3]: To have the 3rd and 2nd posts the same, the 2nd and 1st posts must have been DIFFERENT. The number of ways to have the first two posts different is diff[2]. For each of those ways, the 3rd post has only 1 choice (to be the same as the 2nd). So, same[3] = diff[2] * 1.
diff[3]: To have the 3rd and 2nd posts different, the 2nd and 1st posts could have been SAME or DIFFERENT.
  - If the first two were SAME (same[2] ways), the 3rd post can be any of the (k-1) colors different from the 2nd.
  - If the first two were DIFFERENT (diff[2] ways), the 3rd post can be any of the (k-1) colors different from the 2nd.
So, diff[3] = (same[2] + diff[2]) * (k-1).

Let's apply this to n=3, k=2:
k = 2

n=1:
same[1] = 0
diff[1] = 2

n=2:
same[2] = diff[1] * 1 = 2 * 1 = 2 (RR, BB)
diff[2] = (same[1] + diff[1]) * (k-1) = (0 + 2) * (2-1) = 2 * 1 = 2 (RB, BR)
Total for n=2 = same[2] + diff[2] = 2 + 2 = 4.

n=3:
same[3] = diff[2] * 1 = 2 * 1 = 2 (RBB, BRR)
diff[3] = (same[2] + diff[2]) * (k-1) = (2 + 2) * (2-1) = 4 * 1 = 4 (RBR, RBB-oops, RBR is already counted in diff[3] calculation. Let's rethink diff[3])

Correct logic for diff[3]:
To have the 3rd post different from the 2nd:
Consider the ways to paint first `i-1` posts. The `i`-th post can be any color different from the `i-1`-th post.
If we have `i-1` posts painted, and the `i-1`-th post is color X.
  - If the `i-2`-th post was also color X (total `same[i-1]` ways ending in XX): the `i`-th post can be any of the `k-1` colors other than X.
  - If the `i-2`-th post was NOT color X (total `diff[i-1]` ways ending in YX, where Y != X): the `i`-th post can be any of the `k-1` colors other than X.

Let's adjust the definitions:
Let `same_last_two[i]` be the number of ways to paint the first `i` posts such that post `i` and post `i-1` have the SAME color.
Let `diff_last_two[i]` be the number of ways to paint the first `i` posts such that post `i` and post `i-1` have DIFFERENT colors.

Base case: n = 1
`same_last_two[1] = 0` (cannot have two same colors with only one post)
`diff_last_two[1] = k` (The first post can be any of the k colors)
Total ways for n=1 = k

For `i > 1`:
To calculate `same_last_two[i]`:
The `i`-th post must be the same color as the `i-1`-th post.
This implies that the `i-1`-th post must NOT have been the same color as the `i-2`-th post (to avoid three consecutive same colors).
So, the number of ways to paint the first `i-1` posts such that the `i-1`-th and `i-2`-th are different is `diff_last_two[i-1]`.
For each of these ways, the `i`-th post has only 1 choice (to match the `i-1`-th post).
Thus, `same_last_two[i] = diff_last_two[i-1] * 1`.

To calculate `diff_last_two[i]`:
The `i`-th post must be a different color from the `i-1`-th post.
The number of ways to paint the first `i-1` posts can end with either the same color or different colors.
Total ways to paint the first `i-1` posts = `same_last_two[i-1] + diff_last_two[i-1]`.
For each of these ways, the `i`-th post can be any of the `k-1` colors different from the `i-1`-th post.
Thus, `diff_last_two[i] = (same_last_two[i-1] + diff_last_two[i-1]) * (k-1)`.

Total ways for `n` posts = `same_last_two[n] + diff_last_two[n]`.

Let's re-apply for n=3, k=2:
k = 2

n=1:
`same_last_two[1] = 0`
`diff_last_two[1] = 2`
Total = 2

n=2:
`same_last_two[2] = diff_last_two[1] * 1 = 2 * 1 = 2` (RR, BB)
`diff_last_two[2] = (same_last_two[1] + diff_last_two[1]) * (k-1) = (0 + 2) * (2-1) = 2 * 1 = 2` (RB, BR)
Total = 2 + 2 = 4.

n=3:
`same_last_two[3] = diff_last_two[2] * 1 = 2 * 1 = 2` (RBB, BRR)
`diff_last_two[3] = (same_last_two[2] + diff_last_two[2]) * (k-1) = (2 + 2) * (2-1) = 4 * 1 = 4` (RBR, RBR - wait, double check)
  - From RR: RRB (1 way)
  - From BB: BBR (1 way)
  - From RB: RBR, RBB (2 ways)
  - From BR: BRB, BRR (2 ways)

Let's trace `diff_last_two[3]`:
Ways to paint first 2 posts: RR, BB, RB, BR. Total 4.
For RR, post 3 must be B. (RRB) - ends in different.
For BB, post 3 must be R. (BBR) - ends in different.
For RB, post 3 can be R or B. (RBR, RBB) - ends in different or same.

This is where the previous definition was slightly off. The `diff_last_two[i]` should cover all ways where post `i` and `i-1` are different, regardless of the relationship between `i-1` and `i-2`.

Let's use a simpler DP state:
Let `total_ways[i]` be the total number of ways to paint `i` posts.

Consider painting post `i`.
Case 1: Post `i` has a DIFFERENT color than post `i-1`.
   - The number of ways to paint the first `i-1` posts is `total_ways[i-1]`.
   - For each of these ways, post `i` can be any of the `k-1` colors different from post `i-1`.
   - So, contributions from this case are `total_ways[i-1] * (k-1)`.

Case 2: Post `i` has the SAME color as post `i-1`.
   - This is only allowed if post `i-1` has a DIFFERENT color than post `i-2` (to avoid three consecutive).
   - So, we need to count the number of ways to paint the first `i-1` posts such that post `i-1` and `i-2` are different.
   - How many ways are there for the first `i-1` posts where the last two are different?
   - This is `total_ways[i-2] * (k-1)`? No.

Let's go back to `same` and `diff`.
Let `same_ending[i]` be the number of ways to paint `i` posts such that the last two posts have the SAME color.
Let `diff_ending[i]` be the number of ways to paint `i` posts such that the last two posts have DIFFERENT colors.

Base case: n=1
`same_ending[1] = 0`
`diff_ending[1] = k` (any of the k colors is valid, and there's no previous post to be different from)

For `i > 1`:
`same_ending[i]`:
  To have post `i` and `i-1` be the same, post `i-1` and `i-2` must have been different.
  The number of ways to paint `i-1` posts ending with different colors is `diff_ending[i-1]`.
  For each such way, post `i` has 1 choice (to match `i-1`).
  `same_ending[i] = diff_ending[i-1] * 1`

`diff_ending[i]`:
  To have post `i` and `i-1` be different:
  The first `i-1` posts could have ended with same colors OR different colors.
  Total ways to paint `i-1` posts = `same_ending[i-1] + diff_ending[i-1]`.
  For each of these ways, post `i` can be any of the `k-1` colors different from post `i-1`.
  `diff_ending[i] = (same_ending[i-1] + diff_ending[i-1]) * (k-1)`

Total ways for `n` posts = `same_ending[n] + diff_ending[n]`

Let's re-apply for n=3, k=2:
k = 2

n=1:
`same_ending[1] = 0`
`diff_ending[1] = 2`
Total = 2

n=2:
`same_ending[2] = diff_ending[1] * 1 = 2 * 1 = 2` (RR, BB)
`diff_ending[2] = (same_ending[1] + diff_ending[1]) * (k-1) = (0 + 2) * (2-1) = 2 * 1 = 2` (RB, BR)
Total = 2 + 2 = 4.

n=3:
`same_ending[3] = diff_ending[2] * 1 = 2 * 1 = 2` (RBB, BRR)
`diff_ending[3] = (same_ending[2] + diff_ending[2]) * (k-1) = (2 + 2) * (2-1) = 4 * 1 = 4` (RBR, RBB-oops, RBB ends in same. BRB, BRR-oops, BRR ends in same.)

Let's trace the `diff_ending[3]` calculation for n=3, k=2.
Ways to paint first 2 posts:
- RR (same_ending[2]=2 ways: RR, BB)
- RB (diff_ending[2]=2 ways: RB, BR)

Consider the 4 ways for n=2:
1. RR: Post 3 must be different from R, so B. -> RRB. (Ends in different)
2. BB: Post 3 must be different from B, so R. -> BBR. (Ends in different)
3. RB: Post 3 can be R or B.
   - RBR (Ends in different)
   - RBB (Ends in same)
4. BR: Post 3 can be B or R.
   - BRB (Ends in different)
   - BRR (Ends in same)

Wait, `diff_ending[i]` means post `i` and `i-1` are different.
Let's re-trace n=3, k=2 again.
Total ways for n=3: RBR, RBB, BRB, BRR, RRB, BBR. That's 6 ways.

Let's redo the DP with the current definitions:
`same_ending[i]`: ways to paint `i` posts ending with `XX`.
`diff_ending[i]`: ways to paint `i` posts ending with `YX` where `Y != X`.

Base case: n=1
`same_ending[1] = 0`
`diff_ending[1] = k`

For `i > 1`:
`same_ending[i]`:
  To end with `XX` at post `i`: the `i-1` post must be `X` and `i-2` must NOT be `X`.
  This means the first `i-1` posts must have ended with different colors (`Y` then `X`).
  Number of ways for first `i-1` posts ending with different colors = `diff_ending[i-1]`.
  For each such way, the `i`-th post is fixed to be the same as the `i-1`-th.
  `same_ending[i] = diff_ending[i-1] * 1`

`diff_ending[i]`:
  To end with `YX` where `Y != X` at post `i`:
  The first `i-1` posts could have ended with `YY` (i.e., `same_ending[i-1]` ways) or `ZY` where `Z != Y` (i.e., `diff_ending[i-1]` ways).
  In total, there are `same_ending[i-1] + diff_ending[i-1]` ways to paint the first `i-1` posts.
  For each of these `i-1` post colorings, the `i`-th post can be any of the `k-1` colors that is different from the `i-1`-th post's color.
  `diff_ending[i] = (same_ending[i-1] + diff_ending[i-1]) * (k-1)`

Total ways = `same_ending[n] + diff_ending[n]`.

Let's re-apply for n=3, k=2:
k = 2

n=1:
`same_ending[1] = 0`
`diff_ending[1] = 2`

n=2:
`same_ending[2] = diff_ending[1] * 1 = 2 * 1 = 2` (RR, BB)
`diff_ending[2] = (same_ending[1] + diff_ending[1]) * (k-1) = (0 + 2) * (2-1) = 2 * 1 = 2` (RB, BR)
Total = 2 + 2 = 4.

n=3:
`same_ending[3] = diff_ending[2] * 1 = 2 * 1 = 2` (RBB, BRR)
`diff_ending[3] = (same_ending[2] + diff_ending[2]) * (k-1) = (2 + 2) * (2-1) = 4 * 1 = 4`
  The 4 ways for `diff_ending[3]` are:
  From `same_ending[2]` (RR, BB):
    - RR: post 3 must be different from R -> RRB. (Ends in different)
    - BB: post 3 must be different from B -> BBR. (Ends in different)
  From `diff_ending[2]` (RB, BR):
    - RB: post 3 can be R or B.
      - RBR (Ends in different)
      - RBB (Ends in same) -> This shouldn't be counted in `diff_ending[3]`. Ah, it's the color of post 3 vs post 2.
      - RB -> R (post 3 color is R): RBR (post 3 is diff from post 2)
      - RB -> B (post 3 color is B): RBB (post 3 is same as post 2) - This one *should not* be counted in `diff_ending[3]`
    - BR: post 3 can be B or R.
      - BRB (post 3 is diff from post 2)
      - BRR (post 3 is same as post 2) - This one *should not* be counted in `diff_ending[3]`

Okay, the definitions are correct, but the tracing of the examples needs to be precise.
For n=3, k=2:
Valid ways: RBR, RBB, BRB, BRR, RRB, BBR. Total 6.

Let's trace `diff_ending[3]` again.
`diff_ending[3]` requires post 3 and post 2 to be different.
We start with ways to paint first 2 posts:
Total ways for n=2 is 4: RR, RB, BR, BB.

Consider each of these 4 ways:
1. RR (ends in same): Post 3 can be B (different from R). -> RRB. (This contributes to `diff_ending[3]`)
2. RB (ends in different): Post 3 can be R or B.
   - RBR (Post 3 is R, different from B). -> Contributes to `diff_ending[3]`.
   - RBB (Post 3 is B, same as B). -> Does NOT contribute to `diff_ending[3]`.
3. BR (ends in different): Post 3 can be B or R.
   - BRB (Post 3 is B, different from R). -> Contributes to `diff_ending[3]`.
   - BRR (Post 3 is R, same as R). -> Does NOT contribute to `diff_ending[3]`.
4. BB (ends in same): Post 3 can be R (different from B). -> BBR. (This contributes to `diff_ending[3]`)

So, ways ending in different colors for n=3 are: RRB, RBR, BRB, BBR. That's 4 ways. This matches `diff_ending[3] = 4`.

Now, `same_ending[3]`: requires post 3 and post 2 to be the same.
Ways to paint first 2 posts ending in different colors: RB, BR. (This is `diff_ending[2]=2`).
1. RB: Post 3 must be B (same as post 2). -> RBB. (This contributes to `same_ending[3]`)
2. BR: Post 3 must be R (same as post 2). -> BRR. (This contributes to `same_ending[3]`)

So, ways ending in same colors for n=3 are: RBB, BRR. That's 2 ways. This matches `same_ending[3] = 2`.

Total ways for n=3 = `same_ending[3] + diff_ending[3]` = 2 + 4 = 6. This is correct for Example 1.

**Example 2:**

Input: n = 1, k = 3 Output: 3 Explanation: With one post and three colors (R, G, B), there are three ways to paint it: R, G, or B.


**Example 3:**

Input: n = 2, k = 2 Output: 4 Explanation: For two posts and two colors (R, B), the valid ways are RR, RB, BR, BB.


## Constraints

- `1 <= n <= 10^5`
- `1 <= k <= 10^5`
- The result can be very large, so it might need to be modulo some large prime number if specified by the problem setter (for this challenge, assume standard integer types can handle the result or it is implied by the context of typical competitive programming platforms. If not, a modulo operation would be required.)
- `n` and `k` are positive integers.

## Notes

- This problem can be solved efficiently using dynamic programming.
- Consider the base cases carefully for `n=0` and `n=1`.
- You can optimize space by noticing that the calculation for `i` only depends on `i-1` and `i-2`, allowing you to use only a few variables instead of full arrays.
- The problem statement implies that the order of posts matters (i.e., painting post 1 Red then post 2 Blue is different from post 1 Blue then post 2 Red).

Paint Fence Problem

Problem Description

What needs to be achieved: Calculate the total number of distinct ways to paint the fence according to the given constraint.

Key requirements:

Each post must be painted.

Only k colors are available.

No more than two adjacent posts can share the same color.

Expected behavior: The function should return an integer representing the total number of valid ways to paint the fence.

Important edge cases to consider:

What happens if n is 0 or 1?

What happens if k is 1?

Examples

Example 1:

Input: n = 3, k = 2 Output: 6 Explanation: Let the colors be R (Red) and B (Blue). Valid ways: 1. RBR 2. RRG 3. GRR 4. GRB 5. BRR 6. BRB (Note: The example above uses G, but it should be R or B. Let's correct it assuming R and B are the only colors) Corrected Valid ways for n=3, k=2 (Colors R, B): 1. RBR 2. RRG -> Should be RRB (assuming R and G were a typo and meant R and B) 3. GRR -> Should be BRR 4. GRB -> Should be BRB 5. BRR 6. BRB Let's re-list with R and B only: 1. RBR 2. RRG - Invalid (assumed typo, should be RRB) 3. GRR - Invalid (assumed typo, should be BRR) 4. GRB - Invalid (assumed typo, should be BRB) Valid ways using R and B for n=3, k=2: 1. RBR 2. RBB 3. BRB 4. BRR 5. RRB 6. BBR Let's trace the logic for n=3, k=2: Post 1: Can be R or B (2 options) Post 2: Can be R or B (2 options) Post 3: - If Post 1 and Post 2 are different (e.g., RB): Post 3 can be R or B (2 options) - If Post 1 and Post 2 are the same (e.g., RR): Post 3 must be different from Post 2 (1 option - B) - If Post 1 and Post 2 are the same (e.g., BB): Post 3 must be different from Post 2 (1 option - R) Let's use a more structured approach: n=1: R, B (2 ways) n=2: RR, RB, BR, BB (4 ways) n=3: - If post 2 is different from post 1: (e.g., RB) - Post 3 can be R or B. - For RB: RBR, RBB - If post 2 is the same as post 1: (e.g., RR) - Post 3 must be different from post 2. - For RR: RRB Let's consider the last two posts: Let same[i] be the number of ways to paint the first i posts such that the i-th and (i-1)-th posts have the SAME color. Let diff[i] be the number of ways to paint the first i posts such that the i-th and (i-1)-th posts have DIFFERENT colors. For n=1: same[1] = 0 (cannot have two same colors with only one post) diff[1] = k (any color is valid for the first post, and it's trivially different from a non-existent previous post) For n=2: same[2]: The first post can be any color (k options). The second post must be the same as the first (1 option). So, same[2] = k * 1 = k. diff[2]: The first post can be any color (k options). The second post must be different from the first (k-1 options). So, diff[2] = k * (k-1). Total for n=2 = same[2] + diff[2] = k + k*(k-1) = k + k^2 - k = k^2. (This is correct for k=2: 2*2 = 4 ways) For n=3: same[3]: To have the 3rd and 2nd posts the same, the 2nd and 1st posts must have been DIFFERENT. The number of ways to have the first two posts different is diff[2]. For each of those ways, the 3rd post has only 1 choice (to be the same as the 2nd). So, same[3] = diff[2] * 1. diff[3]: To have the 3rd and 2nd posts different, the 2nd and 1st posts could have been SAME or DIFFERENT. - If the first two were SAME (same[2] ways), the 3rd post can be any of the (k-1) colors different from the 2nd. - If the first two were DIFFERENT (diff[2] ways), the 3rd post can be any of the (k-1) colors different from the 2nd. So, diff[3] = (same[2] + diff[2]) * (k-1). Let's apply this to n=3, k=2: k = 2 n=1: same[1] = 0 diff[1] = 2 n=2: same[2] = diff[1] * 1 = 2 * 1 = 2 (RR, BB) diff[2] = (same[1] + diff[1]) * (k-1) = (0 + 2) * (2-1) = 2 * 1 = 2 (RB, BR) Total for n=2 = same[2] + diff[2] = 2 + 2 = 4. n=3: same[3] = diff[2] * 1 = 2 * 1 = 2 (RBB, BRR) diff[3] = (same[2] + diff[2]) * (k-1) = (2 + 2) * (2-1) = 4 * 1 = 4 (RBR, RBB-oops, RBR is already counted in diff[3] calculation. Let's rethink diff[3]) Correct logic for diff[3]: To have the 3rd post different from the 2nd: Consider the ways to paint first `i-1` posts. The `i`-th post can be any color different from the `i-1`-th post. If we have `i-1` posts painted, and the `i-1`-th post is color X. - If the `i-2`-th post was also color X (total `same[i-1]` ways ending in XX): the `i`-th post can be any of the `k-1` colors other than X. - If the `i-2`-th post was NOT color X (total `diff[i-1]` ways ending in YX, where Y != X): the `i`-th post can be any of the `k-1` colors other than X. Let's adjust the definitions: Let `same_last_two[i]` be the number of ways to paint the first `i` posts such that post `i` and post `i-1` have the SAME color. Let `diff_last_two[i]` be the number of ways to paint the first `i` posts such that post `i` and post `i-1` have DIFFERENT colors. Base case: n = 1 `same_last_two[1] = 0` (cannot have two same colors with only one post) `diff_last_two[1] = k` (The first post can be any of the k colors) Total ways for n=1 = k For `i > 1`: To calculate `same_last_two[i]`: The `i`-th post must be the same color as the `i-1`-th post. This implies that the `i-1`-th post must NOT have been the same color as the `i-2`-th post (to avoid three consecutive same colors). So, the number of ways to paint the first `i-1` posts such that the `i-1`-th and `i-2`-th are different is `diff_last_two[i-1]`. For each of these ways, the `i`-th post has only 1 choice (to match the `i-1`-th post). Thus, `same_last_two[i] = diff_last_two[i-1] * 1`. To calculate `diff_last_two[i]`: The `i`-th post must be a different color from the `i-1`-th post. The number of ways to paint the first `i-1` posts can end with either the same color or different colors. Total ways to paint the first `i-1` posts = `same_last_two[i-1] + diff_last_two[i-1]`. For each of these ways, the `i`-th post can be any of the `k-1` colors different from the `i-1`-th post. Thus, `diff_last_two[i] = (same_last_two[i-1] + diff_last_two[i-1]) * (k-1)`. Total ways for `n` posts = `same_last_two[n] + diff_last_two[n]`. Let's re-apply for n=3, k=2: k = 2 n=1: `same_last_two[1] = 0` `diff_last_two[1] = 2` Total = 2 n=2: `same_last_two[2] = diff_last_two[1] * 1 = 2 * 1 = 2` (RR, BB) `diff_last_two[2] = (same_last_two[1] + diff_last_two[1]) * (k-1) = (0 + 2) * (2-1) = 2 * 1 = 2` (RB, BR) Total = 2 + 2 = 4. n=3: `same_last_two[3] = diff_last_two[2] * 1 = 2 * 1 = 2` (RBB, BRR) `diff_last_two[3] = (same_last_two[2] + diff_last_two[2]) * (k-1) = (2 + 2) * (2-1) = 4 * 1 = 4` (RBR, RBR - wait, double check) - From RR: RRB (1 way) - From BB: BBR (1 way) - From RB: RBR, RBB (2 ways) - From BR: BRB, BRR (2 ways) Let's trace `diff_last_two[3]`: Ways to paint first 2 posts: RR, BB, RB, BR. Total 4. For RR, post 3 must be B. (RRB) - ends in different. For BB, post 3 must be R. (BBR) - ends in different. For RB, post 3 can be R or B. (RBR, RBB) - ends in different or same. This is where the previous definition was slightly off. The `diff_last_two[i]` should cover all ways where post `i` and `i-1` are different, regardless of the relationship between `i-1` and `i-2`. Let's use a simpler DP state: Let `total_ways[i]` be the total number of ways to paint `i` posts. Consider painting post `i`. Case 1: Post `i` has a DIFFERENT color than post `i-1`. - The number of ways to paint the first `i-1` posts is `total_ways[i-1]`. - For each of these ways, post `i` can be any of the `k-1` colors different from post `i-1`. - So, contributions from this case are `total_ways[i-1] * (k-1)`. Case 2: Post `i` has the SAME color as post `i-1`. - This is only allowed if post `i-1` has a DIFFERENT color than post `i-2` (to avoid three consecutive). - So, we need to count the number of ways to paint the first `i-1` posts such that post `i-1` and `i-2` are different. - How many ways are there for the first `i-1` posts where the last two are different? - This is `total_ways[i-2] * (k-1)`? No. Let's go back to `same` and `diff`. Let `same_ending[i]` be the number of ways to paint `i` posts such that the last two posts have the SAME color. Let `diff_ending[i]` be the number of ways to paint `i` posts such that the last two posts have DIFFERENT colors. Base case: n=1 `same_ending[1] = 0` `diff_ending[1] = k` (any of the k colors is valid, and there's no previous post to be different from) For `i > 1`: `same_ending[i]`: To have post `i` and `i-1` be the same, post `i-1` and `i-2` must have been different. The number of ways to paint `i-1` posts ending with different colors is `diff_ending[i-1]`. For each such way, post `i` has 1 choice (to match `i-1`). `same_ending[i] = diff_ending[i-1] * 1` `diff_ending[i]`: To have post `i` and `i-1` be different: The first `i-1` posts could have ended with same colors OR different colors. Total ways to paint `i-1` posts = `same_ending[i-1] + diff_ending[i-1]`. For each of these ways, post `i` can be any of the `k-1` colors different from post `i-1`. `diff_ending[i] = (same_ending[i-1] + diff_ending[i-1]) * (k-1)` Total ways for `n` posts = `same_ending[n] + diff_ending[n]` Let's re-apply for n=3, k=2: k = 2 n=1: `same_ending[1] = 0` `diff_ending[1] = 2` Total = 2 n=2: `same_ending[2] = diff_ending[1] * 1 = 2 * 1 = 2` (RR, BB) `diff_ending[2] = (same_ending[1] + diff_ending[1]) * (k-1) = (0 + 2) * (2-1) = 2 * 1 = 2` (RB, BR) Total = 2 + 2 = 4. n=3: `same_ending[3] = diff_ending[2] * 1 = 2 * 1 = 2` (RBB, BRR) `diff_ending[3] = (same_ending[2] + diff_ending[2]) * (k-1) = (2 + 2) * (2-1) = 4 * 1 = 4` (RBR, RBB-oops, RBB ends in same. BRB, BRR-oops, BRR ends in same.) Let's trace the `diff_ending[3]` calculation for n=3, k=2. Ways to paint first 2 posts: - RR (same_ending[2]=2 ways: RR, BB) - RB (diff_ending[2]=2 ways: RB, BR) Consider the 4 ways for n=2: 1. RR: Post 3 must be different from R, so B. -> RRB. (Ends in different) 2. BB: Post 3 must be different from B, so R. -> BBR. (Ends in different) 3. RB: Post 3 can be R or B. - RBR (Ends in different) - RBB (Ends in same) 4. BR: Post 3 can be B or R. - BRB (Ends in different) - BRR (Ends in same) Wait, `diff_ending[i]` means post `i` and `i-1` are different. Let's re-trace n=3, k=2 again. Total ways for n=3: RBR, RBB, BRB, BRR, RRB, BBR. That's 6 ways. Let's redo the DP with the current definitions: `same_ending[i]`: ways to paint `i` posts ending with `XX`. `diff_ending[i]`: ways to paint `i` posts ending with `YX` where `Y != X`. Base case: n=1 `same_ending[1] = 0` `diff_ending[1] = k` For `i > 1`: `same_ending[i]`: To end with `XX` at post `i`: the `i-1` post must be `X` and `i-2` must NOT be `X`. This means the first `i-1` posts must have ended with different colors (`Y` then `X`). Number of ways for first `i-1` posts ending with different colors = `diff_ending[i-1]`. For each such way, the `i`-th post is fixed to be the same as the `i-1`-th. `same_ending[i] = diff_ending[i-1] * 1` `diff_ending[i]`: To end with `YX` where `Y != X` at post `i`: The first `i-1` posts could have ended with `YY` (i.e., `same_ending[i-1]` ways) or `ZY` where `Z != Y` (i.e., `diff_ending[i-1]` ways). In total, there are `same_ending[i-1] + diff_ending[i-1]` ways to paint the first `i-1` posts. For each of these `i-1` post colorings, the `i`-th post can be any of the `k-1` colors that is different from the `i-1`-th post's color. `diff_ending[i] = (same_ending[i-1] + diff_ending[i-1]) * (k-1)` Total ways = `same_ending[n] + diff_ending[n]`. Let's re-apply for n=3, k=2: k = 2 n=1: `same_ending[1] = 0` `diff_ending[1] = 2` n=2: `same_ending[2] = diff_ending[1] * 1 = 2 * 1 = 2` (RR, BB) `diff_ending[2] = (same_ending[1] + diff_ending[1]) * (k-1) = (0 + 2) * (2-1) = 2 * 1 = 2` (RB, BR) Total = 2 + 2 = 4. n=3: `same_ending[3] = diff_ending[2] * 1 = 2 * 1 = 2` (RBB, BRR) `diff_ending[3] = (same_ending[2] + diff_ending[2]) * (k-1) = (2 + 2) * (2-1) = 4 * 1 = 4` The 4 ways for `diff_ending[3]` are: From `same_ending[2]` (RR, BB): - RR: post 3 must be different from R -> RRB. (Ends in different) - BB: post 3 must be different from B -> BBR. (Ends in different) From `diff_ending[2]` (RB, BR): - RB: post 3 can be R or B. - RBR (Ends in different) - RBB (Ends in same) -> This shouldn't be counted in `diff_ending[3]`. Ah, it's the color of post 3 vs post 2. - RB -> R (post 3 color is R): RBR (post 3 is diff from post 2) - RB -> B (post 3 color is B): RBB (post 3 is same as post 2) - This one *should not* be counted in `diff_ending[3]` - BR: post 3 can be B or R. - BRB (post 3 is diff from post 2) - BRR (post 3 is same as post 2) - This one *should not* be counted in `diff_ending[3]` Okay, the definitions are correct, but the tracing of the examples needs to be precise. For n=3, k=2: Valid ways: RBR, RBB, BRB, BRR, RRB, BBR. Total 6. Let's trace `diff_ending[3]` again. `diff_ending[3]` requires post 3 and post 2 to be different. We start with ways to paint first 2 posts: Total ways for n=2 is 4: RR, RB, BR, BB. Consider each of these 4 ways: 1. RR (ends in same): Post 3 can be B (different from R). -> RRB. (This contributes to `diff_ending[3]`) 2. RB (ends in different): Post 3 can be R or B. - RBR (Post 3 is R, different from B). -> Contributes to `diff_ending[3]`. - RBB (Post 3 is B, same as B). -> Does NOT contribute to `diff_ending[3]`. 3. BR (ends in different): Post 3 can be B or R. - BRB (Post 3 is B, different from R). -> Contributes to `diff_ending[3]`. - BRR (Post 3 is R, same as R). -> Does NOT contribute to `diff_ending[3]`. 4. BB (ends in same): Post 3 can be R (different from B). -> BBR. (This contributes to `diff_ending[3]`) So, ways ending in different colors for n=3 are: RRB, RBR, BRB, BBR. That's 4 ways. This matches `diff_ending[3] = 4`. Now, `same_ending[3]`: requires post 3 and post 2 to be the same. Ways to paint first 2 posts ending in different colors: RB, BR. (This is `diff_ending[2]=2`). 1. RB: Post 3 must be B (same as post 2). -> RBB. (This contributes to `same_ending[3]`) 2. BR: Post 3 must be R (same as post 2). -> BRR. (This contributes to `same_ending[3]`) So, ways ending in same colors for n=3 are: RBB, BRR. That's 2 ways. This matches `same_ending[3] = 2`. Total ways for n=3 = `same_ending[3] + diff_ending[3]` = 2 + 4 = 6. This is correct for Example 1. **Example 2:**

Input: n = 1, k = 3 Output: 3 Explanation: With one post and three colors (R, G, B), there are three ways to paint it: R, G, or B.

**Example 3:**

Input: n = 2, k = 2 Output: 4 Explanation: For two posts and two colors (R, B), the valid ways are RR, RB, BR, BB.

## Constraints - `1 <= n <= 10^5` - `1 <= k <= 10^5` - The result can be very large, so it might need to be modulo some large prime number if specified by the problem setter (for this challenge, assume standard integer types can handle the result or it is implied by the context of typical competitive programming platforms. If not, a modulo operation would be required.) - `n` and `k` are positive integers. ## Notes - This problem can be solved efficiently using dynamic programming. - Consider the base cases carefully for `n=0` and `n=1`. - You can optimize space by noticing that the calculation for `i` only depends on `i-1` and `i-2`, allowing you to use only a few variables instead of full arrays. - The problem statement implies that the order of posts matters (i.e., painting post 1 Red then post 2 Blue is different from post 1 Blue then post 2 Red).