```
int numWays(int n, int k) {
// special cases
if(k == 0 || n == 0) return 0;
if(k == 1) return n <= 2;
if(n == 1) return k;
// f1 : for current number of posts, number of ways ended by 2 diff colors
// f2 : for current number of posts, number of ways ended by 2 same colors
// start from 2 posts
int f1 = k * ( k - 1 ), f2 = k, f = k * k, cnt = 2;
while(cnt++ < n){
f2 = f1;
f1 = f * ( k - 1 );
f = f1 + f2;
}
return f;
}
```