問題のリンク
解法
まず、$a_k=a\alpha^k+b\beta^k$という形で書くことができる。$d_{n,m}$の値は$a_k=\alpha^k,\beta^k$の結果がわかればそれの線形結合で書けるので、$a_k=r^k$といった等比数列でこの問題が解ければOK。
$a_k=r^k$のときの答えを、$n$を固定して$n$ごとに考えてみよう。
$n=1$のときは答えは$r^m $
$n=2$のときは
$$\sum_{k=1}^{m}r^k=r\cdot\dfrac{r^m - 1}{r-1}$$
$n=3$のときは
$$\sum_{k=1}^{m}r\cdot\dfrac{r^k - 1}{r-1}=\dfrac{r}{(r-1)^2}\left((m+1)r^{m+1}-(m+2)r^m-r+2\right)$$
$n=4$のときは
$$\sum_{k=1}^{m}[(n=3)]=\dfrac{r}{2(r-1)^3}\left((m+1)(m+2)r^{m+2}-2(m+1)(m+3)r^{m+1}+(m+2)(m+3)r^m-2r^2+6r-6\right)$$
$n=5$のときは
$$\sum_{k=1}^{m}[(n=4)]=\dfrac{r}{6(r-1)^4}\left((m+1)(m+2)(m+3)r^{m+3}-3(m+1)(m+2)(m+4)r^{m+2}+3(m+1)(m+3)(m+4)r^{m+1}-(m+2)(m+3)(m+4)r^m-6r^3+24r^2-36r+24\right)$$
OK！パターン見えてきたよ！！！
つまり、
$$d_{n,m}=\dfrac{r}{(n-2)!(r-1)^{n-1}}\left[\left(\prod_{i=1}^{n-1}(m+i)\right)\cdot \left(\sum_{i=0}^{n-2}(-1)^{n-2-i}\dfrac{r^{m+i}}{m+i}\binom{n-2}{i}\right)-(n-2)!(r-1)^{n-2}+(n-2)!\right]$$
だな！！！
これなら、$r^m $の累乗パートは二分累乗法を使えば$O(\log{m})$で計算できて、他の部分もΣやΠの項数は$O(n)$だから、これで十分間に合う！
この式の証明はしてないけど、$n=6$のときにも合ってそうだから、まあ大丈夫だろう！！（競技プログラミング特有のガバガバ証明）
…と、ここまでは良いとして、ある問題が立ちふさがる。
「$r$の値は具体的にいくつにすればいいんだ？」
この問題はフィボナッチ数列の和を求める問題なので、$r=\dfrac{1\pm\sqrt{5}}{2}$の場合を計算できればOKである。よって、これは$\mod 998244353$において5の平方根を求めればいいことになる。
ここで、平方剰余の計算方法は、コンピュータを使う場合は、オイラーの基準を使うのが最良である。つまり、$5^{\frac{998244353-1}{2}}\mod 998244353$を計算して、1ならば平方剰余、998244352なら平方非剰余となる。
もし5が平方剰余ならば$c^2\equiv 5\pmod{998244353}$なる整数$c$が存在するため、
$r=(1\pm c)\cdot 2^{-1}$とすればmodint998244353での計算に帰着することができる。
しかし残念ながら$\mod 998244353$において5は平方剰余ではないのである。
するとこの解法は諦めるべきなのだろうか？と思ってしまうがここでこの記事の本題が登場する。
それは、拡大体modintである
つまり、$\mathbb{F}_p[\sqrt{5}]$で計算すればいいことになる。ここで、代数学の知識を駆使すると$\mathbb{F}_p[\sqrt{5}]\simeq \mathbb{F}_{p^2}$であって、これは$\mathbb{F}_p$の二次拡大体となってることが分かる。
結局どうすればいいのかというと、modintのpairを持つのである。
ここで、$(a,b)\in\mathbb{F}_p\times \mathbb{F}_p$に対して$a+b\sqrt{5}$を対応させて、それに対して四則演算を定義させる。
あとは上記の計算を拡大体modint上で行うと無事に問題を解くことができるのである。
提出リンク
余談
位数素数の有限体の場合、二次拡大の場合は単拡大で書くことができる。適当な$d$を取ってきて$\sqrt{d}$を添加すればよいので。あとは$d$以外の数のルートの値が欲しいならば、素数mod上の平方根アルゴリズムなどを使って頑張ることになりそうである。
ところで、自分が原案を書いたKUPC2021-Hの裏テーマは「三次拡大体上modint」だった。しかし、一般の三次方程式の最小分解体の場合だと一次拡大、二次拡大、三次拡大のどれもとる可能性があるため場合分けが面倒くさい。さらに最低でも三次方程式を解かなければいけないが、やるとしたらカルダノの公式を使うといったところになる。結局の所、行列累乗でやるといったような解法のほうがシンプルなので表に出ることはなかった。
関連リンク
modで平方剰余だった場合のifルートが見れる
