部分点解法を説明します。

\(i=4,5,\dots,11\) の操作に対応するベクトルは \(i=0,1,2,3\) の操作に対応するベクトルの整数係数の線形結合で表せることが確認できます。
よって 4 次元 DP による \(\mathrm{O}(N^5)\) 解法が従って、これを利用すれば \(N \leq 60\) 程度までは計算することが出来ます。

母関数を用いると、求めたい答えはある定数次の多項式 \(f(x,y,z,w)\) を用いて

\[[x^N y^N z^N w^N u^N] \frac{1}{1-u f}\]

と表せます。ところで、\(m\) 変数 \(x_1, \dots, x_m\) および有理式 \(g(x_1,x_2,\dots,x_m)\) に対して

\[a_n = [x_1^n x_2^n \dots x_m^n] g(x_1,x_2,\dots,x_m)\]

としたとき、数列 \((a_n)\) は p-recursive であることが知られています。(p-recursive については ABC222-Ex 解説 などを参照してください。) よって \(N \leq 60\) における結果をもとに p-recursive の漸化式の係数を復元することで \(\mathrm{O}(N)\) や \(\mathrm{O}(\sqrt{N} \log N)\) で問題を解くことが出来ます。

ただし、この方針は以下の理由により厳密な正当性を与えていない解法であることに留意してください。制約下において想定解が正しい解を返すことは満点解法によって示されています。

• 今回の問題において p-recursive の次数に対応する概念(ABC222-Ex 解説の \(d, r\)) が \(\mathrm{O}(1)\) で抑えられることは証明可能ですが、\(d, r\) の値の上限がどの程度であるかを証明することは難しいと考えています。その上、minimal な p-recursive の漸化式の表現は一意でないため \((d, r)\) も一意ではありません。よって \(N \leq 60\) の \(60\) という数値の妥当性(\(60\) で本当に足りるのかどうか) に関する証明は困難です。
• p-recursive の漸化式の係数の復元において、”運が悪い時” は十分大きい \(N\) について計算可能な漸化式を得られないことがあります。(条件の説明が困難なのであえてボカした表現を使っています) よって、今回の方針が実装によらず常に正しい答えを返すことの証明もまた困難です。