abc381_g 题解

· · 题解

题目简述

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

Solution

Task1

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

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

Task2

我们假设 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 上的时候，你看了看榜，只有三个人通过了此题，你又不慌了。

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

\prod^{B}_{i=1}(c_ix + d_iy) = \prod^{B}_{i=1}(c_i + d_i\frac{y}{x})x^B

你发现系数仍然未变，而 \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 一样。