hyper fibonacci sequence

問題文に書かれた通りに実装を行うと、いくつかの問題が発生します。

$A_n$ が大きすぎる

例えば $a = 1, \, b = 1, \, c = 1000000000 \, (= 10^9)$ が与えられたとき、数列の項は

$1, \, 1, \, 1^{1000000000} + 1^{1000000000} (= 2), \, 1^{1000000000} + 2^{1000000000}, \dots$

というように増加します。

$64$ bit の符号無し整数の最大値が $2^{64} - 1$ であることを考えると、数列の値が(多倍長整数を用いたとしてもこの問題には $1024$ MB のメモリ制限があるため)扱えないような大きさになってしまうことが分かります。

しかし、剰余環の性質から数列の各項を計算して最後に $M$ で割った余りを計算せずとも数列の各項を $M$ で割った余りのみを計算していくことで同じ答えを得ることができます。

各項を $M$ で割った余りは $0$ 以上 $M$ 未満の整数であり、これは制約 $M \leq 500$ より扱うことが容易な小さい値といえます。

$k$ が大きすぎる

数列を第 $k$ 項まで順番に計算していく方針では、例えば $k = 10^9$ が与えられたときに $10^9$ 回程度のループ処理を行わなければなりませんが、これでは $2$ 秒間の実行時間制限に間に合いません。

しかし数列の一部のある連続する $2$ 項が与えられたとき、それが数列のどこに現れる $2$ 項か分からなかったとしても漸化式よりそれ以降の項を全て計算することができるというこの数列の性質から、数列の中で同じ連続する $2$ 項の並びが現れた場合にそこから先は数列が循環します。

今は数列の各項を $M$ で割った余りを考えているため、各項としてあり得る値は $0$ から $M - 1$ までの $M$ 通りしかありません。よって連続する $2$ 項の並びとして考えられる組み合わせは $M^2$ 通りしかありません。

そこで、数列の各項を $M$ で割った余りを計算しつつ $M \times M$ の大きさの $2$ 次元配列を用意して配列の各要素に対応する連続する $2$ 項が今までどこかに現れたかを記録しておくことで同じ $2$ 項の並びが現れた時にそこで計算を終了し、それ以降の項は周期を計算することで求めることができるようになります。

第 $M^2 + 2$ 項まで計算を行うと連続する $2$ 項の並びは $M^2 + 1$ 個現れ、これらが $M^2$ 個の要素をもつ $2$ 次元配列の要素のどれかと対応するため鳩の巣原理より必ず周期を検出することができます。

$c$ が大きすぎる

整数の $c$ 乗を計算するために $c$ 回程度のループ処理を行うと、例えば $c = 10^9$ が与えられたときに累乗の計算が $2$ 秒間の実行時間制限に間に合いません。これは、二分累乗法を用いることで解決できます。

---

整数の入力や四則演算やコピー等に掛かる時間が全て定数時間であることを仮定すると、各項の計算に二分累乗法による累乗の計算で $\Theta(\log c)$ 時間が掛かり、その計算を第 $M^2$ 項程度まで行う必要があります。周期が検出された後は定数時間で第 $k$ 項を $M$ で割った余りを求められることから全体の時間計算量は $\Theta(M^2 \, \log c)$ です。

制約上の最大値である $M = 500, \, c = 10^{9}$ を代入し、対数の底を $2$ として単純な見積もりを行うと

$\begin{array}{ll} &M^2 \, \log_2{c} \\[0.5ex] =& 500^2 \cdot \log_2 \left(10^9\right) \\[0.5ex] =& 500^2 \cdot 9 \, \log_2{10} \\[0.5ex] <& 500^2 \cdot 9 \, \log_2{16} \\[0.5ex] =& 500^2 \cdot 9 \cdot 4 \\[0.5ex] =& 9 \times 10^6\end{array}$

より、$2$ 秒間の実行時間制限に間に合いそうであることが分かります(最近の一般的なコンピューターは $1$ 秒間に $10^8$ 回程度の計算ができると言われています)。

※実際に間に合うことはプログラムを実装して実行してみることで初めて確認されます。

解答例 (C++)