abc381_g 题解

给定广义斐波那契数列的前两项 $x,y$。求该斐波那契数列的前 $N$ 项之积。

如果你熟悉斐波那契数列的性质，你就会知道斐波那契数列在取模 $m$ 时循环。周期为 $O(m)$ 级别的。

广义斐波那契数列的周期是可以求的。因为模数为 $99824353$ 且为质数，我们利用矩阵快速幂可以求得该数列的周期 $T$。时间复杂度为 $O(\log N)$。

我们假设 $f(x) = \prod^{x}_{i=1}a_i$，若我们求出来了周期 $T$，那么答案即为 $f(N \mod T) + f(T)^{\lfloor \frac{N}{T} \rfloor}$。

接下来考虑将题目范围缩小到 $998244353$ 级别怎么做。如果你做过快速阶乘，那么会想到类似的分块思想。现在将 $T$ 内的数字分为若干个块，块长为 $B$。如果要知道这个块的信息，必须要先知道前两个数的值，以方便斐波那契数列的递推。这部分可以使用矩阵快速幂，时间复杂度 $O(\frac{T}{B} \log T)$。

你把块剥离出来，假设某个块前两个数为 $x,y$，根据斐波那契数列的递推式，第三个数为 $x+y$，第 $B$ 个数为 $c_n x + d_n y$。那么这一段的积即为 $\prod^{B}_{i=1}(c_ix + d_iy)$。

不同的块只有 $x,y$ 不相同，系数是不变的，我们不妨预处理展开每一项的系数。这是 $B$ 个二项式相乘，时间复杂度 $O(B^2)$。

这是一个 $B$ 次的多项式，单次计算时间 $O(B)$。如果暴力对所有块计算，时间复杂度来到 $O(n)$，弗如暴力。

你知道有“多项式多点求值”这个东西，它可以实现 $O(\log n)$ 求出多项式的值。可是你搜索的所有“多项式多点求值”都是一元求值，并无二元求值。

本来以为成功的你大为失望，你愤恨，怒骂，质疑出题人为什么要放这么难的题在 G 上的时候，你看了看榜，只有三个人通过了此题，你又不慌了。

不知道过了多久，你准备关闭网页的时候，想到：为什么我要二元？你把上面的柿子转化成：

你发现系数仍然未变，而 $\frac{y}{x}$ 是一元的。而你每个块是知道 $x,y$ 的，你想到了好做法：

将 $\frac{y}{x}$ 设为一个点，利用多项式单点求值求出这个固定的已知系数的多项式的值。$x^B$ 用个快速幂就可以求。你发觉：这个时间复杂度是 $O(\log B)$。

你算了算，总的时间复杂度是 $O(\frac{T}{B} \log B + B \log B + B^2)$。这个均值不等式你是会计算的。在取 $B = T^{\frac{1}{3}}$ 时或许可以做到最优，那么时间复杂度就变为了 $O(T^\frac{2}{3} \log T^\frac{1}{3})$。这个速度和你跑 $q = 10^6$ 的线段树差不多，然而常数比较大，不过时限是 4s（标解的时间复杂度是 $O(\sqrt T\log T)$）。

你直接就开始写。大概离比赛还有 5min 的时候，你看着还有大半没写完的代码陷入了沉思，然后大哭一场。

如果你不在那 20min 里去看 B 站，或许你还有机会把这题做出来。

就像 NOIP 一样。