暴力计算即可。
DP，正难则反。
也就是求不超过连续两个题目选择同一个答案的方案数。
状态 f[i][x][y] 第 i 位，前一位是 x，本位是 y 的上述的方案数。
f[2][x][y] = 1, 1 \leq x \leq K,1 \leq y \leq K。
f[i][x][y] = \sum\limits_{j=1}^{K} f[i-1][j][x], x \neq y
f[i][x][y] = \sum\limits_{1 \leq l \leq K , x \neq j} f[i-1][j][x], x = y
答案为
$$N^K-\sum\limits{x=1}^{K} \sum\limits{y=1}^{K} f[N][x][y]$$
正难则反（含义见上文）。
不妨将一道题或是两道连续的、选择相同答案的题视作一个“块”。
如果有 0 个块选连续两道相同的题：总共有 N 个块，第一个块有 K 种选法，以后的每个块由于不和上一个相同，有 (K-1) 种选法。
如果有 1 个块选连续两道相同的题：总共有 (N-1) 个块，第一个块有 K 种选法，以后的每个块由于不和上一个相同，有 (K-1) 种选法。由于这 (N-1) 个块中恰好有 1 个块选连续两道相同的题，所以方案数要乘上 \binom{n-1}{1}。
如果有 2 个块选连续两道相同的题：总共有 (N-2) 个块，第一个块有 K 种选法，以后的每个块由于不和上一个相同，有 (K-1) 种选法。由于这 (N-2) 个块中恰好有 2 个块选连续两道相同的题，所以方案数要乘上 \binom{n-2}{2}。
依此类推，总方案数为：
\sum\limits_{i=0}^{\left \lfloor \frac{n}{2} \right \rfloor} K (K-1) ^ {n-i-1} \binom{n-i}{i}
使用递推处理组合数（时间复杂度 O(n^2)），或是预处理阶乘与阶乘逆元（时间复杂度 O(n \log n)）都可以。