公式解説での解法 2 における

組の個数は \(6y_1+4y_3+y_6=S\) を満たす正整数の組 \((y_1,y_3,y_6)\) の個数に等しくなります。

という問題について、別のアプローチで計算をすることを考えます。

スコアを番号だけ増加させる操作 \(1, 2, 3, 4, 5, 6\) について、操作列が広義単調増加になるように操作することを考えます。使った操作が \(1, 4, 6\) のみの場合、スコアを \(S\) 得るような操作列の個数と上述の解説で取り上げられている問題の個数は等しくなることが分かります。

ここで、

dp[i][b] := 今のスコアが i で、使った操作が b の通り数

という dp を考えます。これには六項間漸化式が立つので、適切な遷移行列を累乗することによって求めることができます。

この行列は、ありうる 64 通りの集合に番号を割り振りったものを六項分持つことになります。そのため、サイズは \(2^6 \cdot 6=384\) となり、行列累乗を行った際の演算回数の概算は \(384^3 \cdot \log_2 10^{18} \approx 3.4 \cdot 10^9\) 回程度となります。

行列行列積の高速化や扱う行列が疎であるために可能な高速化などを行い、C++ にて実行時間が 1300ms の実装を行うことができました。

実装: https://atcoder.jp/contests/abc198/submissions/21723046