\((0,0)\) から始めて \((k,k)\) に至るパスであって，対角線を踏み超えず，また始点と終点以外で対角線に触れないような操作の重みの総和を \(g_k\) と置きます． また，\(G(x)=\sum_{1 \leq k} g_k x^k\) と置きます． \(G\) が求まれば元の問題もすぐに解けます．

\(F(x,y)=\sum_{0 \leq i,j \leq 3} W_{i,j}x^iy^j\) と置きます．

ジャンプ \((i,j)\) に長さ \(i+j\) の棒を対応させることにします． \((0,0)\) から \((n,n)\) へ至るパス (対角線制約は考えない) は，長さ \(2n\) の棒になります． そしてこの棒を cyclic shift することを考えます． ここで，シフトによって操作の途中が先頭になってもよいものとします．

こうして得られる列（重複を除く）の重みの総和 \(v_n\) について考えてみましょう． まず，\(F\) を使って表します． 重複を数えないためには，先頭の操作が \((i,j)\) だった場合 \((i+j)\) 通りのシフトが存在すると考えればよく，

\[\displaystyle v_n=[x^ny^n]\left(\sum_{0 \leq i,j \leq 3} (i+j) \times W_{i,j}x^iy^j \right)\frac{1}{1-F(x,y)} \]

となります． 他方で，\(G\) を用いた表示も存在します． \(F\) と同様の議論により，

\[\displaystyle v_n=[x^n]\left(\sum_{1 \leq k} 2k \times g_kx^k \right)\frac{1}{1-G(x)} \]

とわかります． ところで，

\[\displaystyle [x^n] (- \log(1-G(X))) = \frac{1}{n} [x^n]\left(\sum_{1 \leq k} k \times g_kx^k \right)\frac{1}{1-G(x)} \]

と表せます． よって，\(v_i\) (\(0 \leq i \leq N\)) がわかれば， \((- \log(1-G(X)))\) の最初の \(N+1\) 項もわかり，そこから元問題の答えも計算できることになります．

あとは \(v_n\) を計算するだけです． \(v_n\) の \(F\) による表示に注目すると，これは P-recursive であることがわかります． また分母，分子の多項式の次数が定数なので，漸化式の項数/次数も定数です． よって，実際に \(v_n\) の最初の項 (writer 解は \(500\) 項生成しました) を適当な DP によって求めたあと，残りを漸化式に沿って求めていけばよいです．

計算量は形式的べき級数関連の操作がボトルネックになり，全体で \(O(N \log N)\) になります．

解答例

ところで，\(v_i\) が P-recursive であることと，その項数/次数が定数であることは理論的に示せますが，実際にいくつになるかは実験しないとわかりません． 実験したところ \(500\) 項使って計算すれば大丈夫そうということがわかっているだけで，理論的な保証は一切ありません． また，漸化式を使った計算の途中で \(0\) 除算 (mod 素数) が発生しないかどうかも未知数です． P-recursive のよくある実装として，多項式の次数を適当に指定するというものがありますが，ここで指定した値によって得られる漸化式が変わり，その値によって \(0\) 除算が起きるかどうかが変わることもあります． 以上の理由から，writer 解は限りなく正しそうではあるものの，正しい答えを出力できる確率について何の証明もありません． 一応，愚直解を走らせることで用意した出力が正しいことは確認していますが．果たして，このような問題はどのように出題すればよいのでしょう？