公式解説(2) (https://atcoder.jp/contests/arc154/editorial/5565) の dp を考えるところまでは同じです。公式解説にある通り、この dp は \(A_{i, j} = \text{dp}[1][j][i]\) と定義すれば \(\text{dp}[k][j][i] = (A ^ k) _ {i, j}\) であるという性質を持ちます。\(N\) 次元ベクトル \(u, v\) を \(u_i = i, ~ v _ i = P_i\) と定義すると、\(u^{\top} A^M v\) を求めることが目標となります。

\(P^{-1} A P= D\) と対角化可能と仮定すると、\(A ^ M v = P D^M P^{-1} v\) です。更に \(P\) や \(P^{-1}\) が規則的な形になるならば、\(v\) に対する乗算も高速に行える可能性があります。そこで小さな \(N\) について実際に \(A\) を計算し Wolfram Alpha を用いて固有ベクトルを計算すると、以下の予想が立ちます。

\(A\) の固有ベクトルは全ての成分が \(1\) から成るものと、\(0 \leq k < \left\lceil \frac{N}{2} \right\rceil - 1\) によって

\[v _ i = \begin{cases} N - 2k - 2 \quad &(i = k) \\ -1 \quad &(k < i < N-1-k) \\ 0 \quad &(\text{otherwise}) \end{cases}\]

と表されるもの、及びそれを左右反転したもの、\(N\) が偶数の場合に限りこれに加えて

\[v _ i = \begin{cases} 1 \quad &(i = \frac{N}{2} - 1) \\ -1 \quad &(i = \frac{N}{2}) \\ 0 \quad &(\text{otherwise}) \end{cases}\]

である。

\(v\) に \(P^{-1}\) を乗じる操作は \(v\) を固有ベクトルの線形結合で表現する際の係数を求める操作であり、\(P\) を乗じる操作はその逆に係数に従い固有ベクトルを足し合わせる操作です。固有ベクトルの形から、前述の予想における \(k\) の値が小さい順にその係数を定めていくアルゴリズムは \(O(N)\) の時間計算量で動作します。\(D\) は固有値を対角成分に持つ行列であり、固有値も予想するか、あるいは固有ベクトルから手で計算することで高速に求まります。以上より \(A ^ M v = P D^M P^{-1} v\) の計算は \(O(N \log(M))\) で実行でき、AC を得ることができます。