This should be fast. It's already consuming 0ms so I have no motive to further optimize it. As a statistician, I solved this problem by counting the possible ways of painting.

The answer is $\sum{d=0}^{\lfloor n/2 \rfloor} f(n,d)(k \cdot (k-1)^{n-d-1})$. (Oh! I wish TeX is supported here...) And f(n,d) is defined to be the possible ways to have d adjacent same-color posts.

```
long factorial(int x) {
long res = 1;
if (0 == x)
return 1;
for (int i = 1; i != x+1; ++i) {
res *= i;
}
return res;
}
int ipow(int x, int y) {
long res = x;
if (0 == y)
return 1;
for (int i = 1; i != y; ++i)
res *= x;
return res;
}
int f(int n, int d) {
long res = 1;
for (int i = n - d; i != n - 2*d; --i) {
if (i == d) {
res = res / factorial(n-2*d);
return res;
}
res *= i;
}
res = res / factorial(d);
return res;
}
int numWays(int n, int k) {
int sum = 0;
int halfn = n/2;
if (n == 0) return 0;
// d is the number of adjacent same color posts
for (int d = 0; d != halfn+1; ++d) {
sum += k * ipow(k-1, n-d-1) * f(n,d);
}
return sum;
}
```