公式解説の記号を用います:

• \(M=49=7^2\)．
• 公式解説で定義された \(M\) 次正方行列 \(G\)，およびその転置 \(A=G^{\top}\)
• 行列の行・列へのindexは0-origin で，配列の角括弧記法 \(G[i][j]\) を準用する

解法

この問題は，公式解説でも指摘されている通り，\(G\) の \(N\)乗 \(G^N\) の \((0,M-1)\)-成分，つまり \((G^N)[0][M-1]\) を求める問題でした．言い換えれば， \(A^N\) の \((M-1, 0)\)-成分 \((A^N)[M-1][0]\) です．

しかし，行列積をそのままナイーブに実装すると \(\Theta(M^3)\) かかるため，ダブリングを用いてもケースごとに時間計算量が \(\Theta(M^3 \log N)\) かかってしまい，全体での最悪時間計算量は \(\Theta(TM^3 \log(N_{\max}))\)，数値的に \(1.8 \times 10^{10}\) ほどとなり，間に合いません．

これを言い換えたいです．\(M\) 次縦ベクトル \(v\) を次のように定義します：

\[ v = \begin{pmatrix} 1 \\ 0 \\ 0 \\ \vdots\\ 0\\ 0 \end{pmatrix}, \]

つまり \(v[0] = 1\), \(v[i]=0\) for \(0 < i < M\) です．このとき，行列 \(A^N\) の成分 \((A^N)[M-1][0]\) は，縦ベクトル \(A^N v\) の第 \(M-1\) 成分 \((A^N v)[M-1]\) と等しいです．

そこで，\(M\) 次正方行列と \(M\) 次縦ベクトルの積が時間計算量 \(O(M^2)\) で計算できることを使うことを考えます．とはいえ， \(A^N v\) を

\[ A(A(\cdots(Av)\cdots)) \]

のように計算してしまっては，\(\Theta(M^2 N)\) かかるので元も子もありません．ダブリングと組み合わせることを考えましょう．

いま，次のような表示を考えます．

\[ N = 2^{a_1} + 2^{a_2} + \cdots +2^{a_k}, \quad a_1 > a_2 > \cdots > a_k \]

このとき，次が成り立ちます．

\[ A^N = A^{2^{a_1}}A^{2^{a_2}} \dotsb A^{2^{a_k}} \]

したがって，もちろん次も成り立ちます：

\[ A^N v= A^{2^{a_1}} (A^{2^{a_2}}( \dotsb (A^{2^{a_k}}v)\dotsb)) \]

この式を使って計算することを考えます．そのためには，次の全てを前計算しておき，各ケースについては行列とベクトルの積を繰り返して計算すれば良いです：

\[ A^{2^0}, A^{2^1}, \dotsc, A^{2^{\lfloor \log N_{\max}\rfloor}} \]

この列は \(A^{2^{k+1}} = (A^{2^k})^2\) によって，逐次的に時間計算量 \(O(M^3 \log N_{\max})\) で計算できます．各ケースの計算時間は， \(k \le \log N\) に注意すれば \(O(M^2 \log N)\) であることがわかり，結局，合わせての計算時間は，\(O((M^3 + M^2T)\log N_{\max})\) となります．これはざっくり \(3.6\times 10^8\) 程度で，おそらく十分間に合います．

3倍高速化

なお，私は DP の状態数を減らすことによって \(M=28\) として提出しました． 公式解説のDP配列 \(\mathrm{DP}\) を用いて，\(\mathrm{DP}_2\) を次のように定義します:

\[ \operatorname{DP}_2[i][j][k] \coloneqq \begin{cases} \operatorname{DP}[i][j][k] + \operatorname{DP}[i][k][j] & j > k,\\ \operatorname{DP}[i][j][k] & j = k. \end{cases} \]

ここで，配列 \(\mathrm{DP}_2\) の成分としては\(j \ge k\) なる成分だけを考えることにし，\(j < k\) は無いものとして扱います．この配列を用いても漸化式を作れて，正しく問題を解くことができます．すると，各 \(i\) ごとに \(28\) 要素しか無くなるので，これだけでも大体2倍弱の高速化が望めます．また，これに対応する行列も同様に考えることができ，この解説の解法では3倍強の高速化を見込むことができます．

解答例(Haskell): 提出 #54785935