rt

给你两个数 $n$,$k$

$n$ 为序列的长度，$k$ 表示序列中每个数的值域在 $1$ ~ $k$ 之间

求有多少种可能使得这个序列相邻两数异或不为 $0$

感觉可以dp

除dp外，有没有复杂度更优的解法