まずは愚直な \(DP\) を考えましょう． \(dp[i][j]=(x_i,\cdots,x_j)\) に対する答えとします． \(dp\) の遷移は以下の通りです．

• \(x_i=x_j\): \(dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]\)
• \(x_i \neq x_j\): \(dp[i][j]=dp[i-1][j]+dp[i][j-1]\)

この DP の値を高速に計算しましょう． まず，\(dp[i][j]\) の値は \(i \pmod N\) と \(j-i\) だけで決定されるとわかります． そこで，\(dp2[i \pmod N][j-i]=dp[i][j]\) として，\(dp2\) に注目します．

\(dp2[i][*]\) は \(dp2[i-1][*]\) と \(dp2[i-2][*]\) の値から決まります． そこで，\((dp[i-2][*],dp[i-1][*]) \to (dp[i-1][*],dp[i][*])\) という変換を考えると，これは行列の形で書けます． この行列は \(i \pmod N\) にのみ依存します． この行列を \(M_0,M_1,\cdots,M_{N-1}\) とおきます．

すると最終的に求めたいのは \((M_{N-1} \times \cdots \times M_0)^K(dp[-1][*],dp[0][*])\) の値 (の \(1\) つの成分) です．

この式の形を見れば，各 \(k=0,1,\cdots,K\) の答えが線型漸化的になっていることがわかります． そこで，\(dp2[Nk][0]\) の値を \(O(N)\) 個 (具体的には \(k=0,1,\cdots,4N\) に対して) 求めて，Berlekamp Massey と Bostan-Mori Algorithm を用いれば \(dp2[NK][0]\) の値を求められます．

計算量は \(O(N^3+N^2 \log K)\) です．

回答例(C++)