下準備：\(\sqrt{5}\) の添加

既知の事実として、\(a_n\) の一般項はある定数 \(c_1, c_2\) を用いて次式で表すことができます。

\[a_n = c_1 \left(\frac{1 + \sqrt{5}}{2}\right)^n + c_2 \left(\frac{1 - \sqrt{5}}{2}\right)^n\]

この式は \(a_n\) の一般項としてキレイな表現なのでこの式を用いて問題を解くことを考えたいですが、\(\text{mod }998244353\) 上で \(\sqrt{5}\) をどのように扱うのかという問題が発生します。\(\text{mod }998244353\) 上に \(\sqrt{5}\) が存在すれば、すなわち整数 \(n\) であって \(n^2 = 5 \pmod{998244353}\) を満たす数が存在すれば \(\sqrt{5}\) を \(n\) に置き換えることが出来ますが、残念ながらそのような \(n\) は存在しません。

困ったようですが、この問題は 添加 と呼ばれる数学的概念を用いると解決できます。ラフに説明すると、値を「(modint998244353) + (modint998244353) \(\times \sqrt{5}\) 」という形で管理することにすると、これは通常の modint998244353 と同様に扱って問題ないことが示せます。このような代数的構造を「\(\sqrt{5}\) を添加した体」のように呼びます。

• 少しだけ形式的に説明すると、\(F = \lbrace a + b \sqrt{5} \vert a, b \in F_{998244353} \rbrace\) として \(F\) 上での四則演算を適切に定義すると \(F\) は体となることが証明できるため、 体に対するアルゴリズムを \(F\) に対しても適用できます。

添加は高度な問題の解法にまれに登場するので (特に \(1\) の \(k\) 乗根の添加が典型的です) 知っておいて損はないでしょう。

解法

以降では値を適宜 \(F = \lbrace a + b \sqrt{5} \vert a, b \in F_{998244353} \rbrace\) の元として考えます。

\(a_n\) はある定数 \(A, B, c_1, c_2\) を用いて

\[a_n = c_1 A^n + c_2 B^n\]

と表すことが出来ます。(\(c_1,c_2\) は \(n=1, 2\) の場合の等式を利用すれば計算できます)

\(\mathrm{mod} = 998244353\) とします。ここで非自明な事実として、

\[A^{2(\mathrm{mod} + 1)} = B^{2(\mathrm{mod} + 1)} = 1\]

が成り立つことが確認できるので、数列 \(a_n\) の周期は \(2(\mathrm{mod} + 1)\) の約数です。よって \(N = q \times 2 (\mathrm{mod} + 1) + r\) とおくと、\(N \gt 2(\mathrm{mod} + 1)\) の場合は \(N = 2 (\mathrm{mod} + 1)\) の場合の答えを \(q\) 乗した答えに \(N = r\) の場合の答えを乗じたものになります。よって \(N \leq 2 (\mathrm{mod} + 1)\) の場合が解ければ問題を解くことが出来ます。以降では \(N \leq 2 (\mathrm{mod} + 1)\) とします。

さて、 \(D = \frac{A}{B}\) と置くと

\[\frac{a_n}{B^n} = c_1 D^n + c_2\]

となるので \(\prod_{n=1}^N (c_1 D^n + c_2)\) が計算できれば求めたい答えを計算できるのでこの式を計算することにします。

\(M = \lfloor \sqrt{N} \rfloor\) とします。\(N = M^2\) である場合が解ければ \(\mathrm{O}(\sqrt{N})\) 個追加で \(a_n\) を計算すれば答えを求められるので、以降では \(N = M^2\) の場合を解くことを考えます。

\[ \begin{aligned} &\prod_{n=1}^{M^2} (c_1 D^n + c_2) \\ &= \prod_{i=0}^{M-1} \prod_{j=1}^{M} (c_1 D^{iM + j} + c_2) \\ &= \prod_{i=0}^{M-1} \left\vert \prod_{j=1}^M (c_1 D^j X + c_2) \right \vert_{X=D^{iM}} \end{aligned} \]

です。(\(\vert f(X) \vert_{X=n}\) は \(f(X)\) に \(X=n\) を代入する意。)よって \(F(X) = \prod_{j=1}^M (c_1 D^j X + c_2)\) とすると、

1. \(F(X)\) を計算する
2. \(F(X)\) に \(X = D^0, D^M, D^{2M}, \dots, D^{M(M-1)}\) を代入した値を計算する

という 2 つのステップを経れば求めたい値を計算できます。それぞれのステップに分けて考えます。

1 番目のステップはダブリングの要領で \(\mathrm{O}(M \log M)\) で計算できます。

\(F_n(X) = \prod_{j=1}^n (c_1 D^j X + c_2)\) とします。求めたいものは \(F_M(X)\) です。
\(M\) が偶数の場合、

\[ \begin{aligned} F_M(X) &= \prod_{j=1}^M (c_1 D^j X + c_2) \\ &= \prod_{j=1}^{M/2} (c_1 D^j X + c_2) \prod_{j=M/2+1}^M (c_1 D^j X + c_2) \\ &= F_{M/2}(X) F_{M/2} (D^{M/2} X) \end{aligned} \]

という式により \(F_{M/2}(X)\) から \(F_M(X)\) を \(\mathrm{O}(M \log M)\) で計算できます。\(M\) が奇数の場合も \(F_M(X) = F_{M-1}(X) (c_1 D^M X + c_2)\) という式を利用すればよいです。以上の内容を実装すれば \(F_M(X)\) を \(\mathrm{O}(M \log M)\) で計算できます。

2 番目のステップについて考えます。このステップは言い換えると「多項式を等比数列上において多点評価せよ」という問題です。通常の多点評価は評価点数および多項式の次数を \(n\) として \(\mathrm{O}(n \log^2 n)\) かかりますが、等比数列上での多点評価は chirp z-transform と呼ばれるアルゴリズムで \(\mathrm{O}(M \log M)\) で計算できます。詳細な説明は以下の記事に譲ります。Kyopro Encyclopedia of Algorithms の記事, CodeForces の記事

以上の内容を適切に実装すればこの問題を \(\mathrm{O}(\sqrt{\mathrm{mod}} \log \mathrm{mod})\) 程度で解くことが出来て、これは十分高速です。