解説

右隣と同じならば、どの数字を選んでも点数に差がでないです。

以下、右隣と違うものを考えます。

右隣と違うものが $cnt$ 個あるとしましょう。

となります。よってここで、 $cnt$ 個のうち、左右のどちらかを選ぶ個数 $i$ を固定しましょう。

このとき、 $cnt - k$ は左右のどちらでもない数字を選ぶので、 $(k - 2) ^ {cnt - i}$ 通りあります。

左右のどちらかを選ぶときは、基本的に $2^{i - 1}$ 通りあります(左右どちらかが多いのは対称なので)

ただし、 $i$ が偶数の場合は左右が同じ数になるのを引いてから考えておきましょう。( ${} _ {i} C _ {i/2}$ 通りあります)

提出コード

実装では左右に選ばない数を $i$ としています