112. 線形隣接３項間漸化式

【問題概要】
初項a1と公差dが与えられたとき、
以下の線形隣接３項間漸化式で定義される数列の第n項を求めるプログラムを作成せよ。
a_n = a_{n-1} + a_{n-2} + a_{n-3} (n ≥ 4)
(a_1 = a1, a_2 = a1 + d, a_3 = a1 + 2d)

【解説】
この問題は線形隣接３項間漸化式の実装問題である。nが小さい場合は単純な再帰関数で実装できるが、nが大きい場合には再帰関数では時間がかかってしまう。そこで、メモ化再帰を用いて実装することで、計算量を抑えることができる。

具体的には、配列に計算済みの値を保存しておき、再帰呼び出しの際には配列を参照して計算済みであればその値を返すようにする。これにより、同じ計算を何度も行うことを避けることができる。

【例題】
AtcoderのタイトルとURL: ABC006D https://atcoder.jp/contests/abc006/tasks/abc006_4
レーティング難易度(★): 1100
ACした回答者に絞った場合のレーティング帯の範囲(数値): 0~1882
レーティング難易度(%): 14.79%
レーティング(数値): 1433
AC率(%): 14.79%
ACしたスコアの高い回答者: unbalanced_man
解説ブログ: https://www.creativ.xyz/abc-006

【問題概要】
与えられた数列の第n項を求めるアルゴリズムがあります。
数列の最初の3項 a[0], a[1], a[2] は与えられており、n >= 3 であるとします。
この数列は、すべての k (3 <= k <= n) について、a[k] = A * a[k-1] + B * a[k-2] + C * a[k-3] で定義されます。
ただし、A, B, C は定数であり、与えられます。

このアルゴリズムを実装し、数列の第n項を求めるプログラムを作成してください。

【解説】
この問題は、線形隣接3項間漸化式を解く問題です。
このような問題では、行列の累乗を使うことで高速に解くことができます。
具体的には、与えられた漸化式を行列の形式に変換し、n-3乗した行列と初期値の積を求めることで、数列の第n項を求めることができます。

【関連する問題】
AtCoderの「ABC129 E - Sum Equals Xor」が関連する問題です。(https://atcoder.jp/contests/abc129/tasks/abc129_e
この問題では、ある条件を満たす整数列を数え上げる問題となっていますが、条件の一部に線形隣接3項間漸化式を用いることができます。