「HDU 5848」Easy Homework

题目传送门

题目大意是给定一个广义 Fibonacci 数列 ,其中 ,求有多少 范围内,满足

首先 的范围很大,考虑模意义下的广义 Fibonacci 数列的循环节长度大概是 的, 是模数,因此我们先把循环节求出来。

求广义 Fibonacci 数列循环节在这篇文章给出了详细证明过程,在本题的结论是:

  • 是模 的二次剩余,则最小循环节长度是 的一个因子;
  • 不是模 的二次剩余,则最小循环节长度是 的一个因子;
  • ,则最小循环节长度为

最后一条结论不会证明,但是跑了 以内的满足条件的数应该都是满足的。

所以套用 Pollard Rho 即可进行快速的因数枚举,之后使用矩阵快速幂判断是否是循环节即可,复杂度是 指的是 的因数个数。

现在我们把整个序列的范围缩小到了一个 长度的循环节内,下面考虑一个循环节内模 的位置怎么求。考虑一个经典题是给两个数,问在广义 Fibonacci 数列出现的位置,这个是用这两个数构造矩阵,用 BSGS 求即可。这里只出现了一个数,没办法构造矩阵的。

考虑 Cassini's identity,有 。这里按照行列式证明的方式,易知本题中这个性质仍然满足。因此设 ,则方程

成立。

因为我们要求出 才能根据 求出 ,但所有满足条件的解一定满足方程,所以我们先讨论奇偶,然后发现这个是一个模意义下解二次方程。利用求根公式求,如果根号下的数在模 意义下不存在二次剩余,则忽略它,因为要求的是实根,否则找个二次剩余板子把解求出来,然后套用上面提到的 BSGS 把位置求出来。

根据方程性质,可以知道在一个循环节内最多有 个解,然后就套用 BSGS 求位置,根据循环节长度算算即可。

然后就会收到一个大大的 TLE。

仔细分析,因为我们求解的是一个矩阵 ,其中:

是我们构造的矩阵。按照正常的矩阵求解,是拆成 而非 的形式以避免矩阵求逆,但是拆成 的话第一步小步的值需要求四次,而拆成 的话小步的结果就可以保留下来,大步中还能复用。所幸 是可逆的,因此根据这个性质,就从原来的最大 的 BSGS 过程变成了 ,就能卡过去了。

时间复杂度:,空间复杂度:

代码在这里