自动搬运

查看原文

来自洛谷，原作者为

	ftiasch 这个学院最强大的女孩子的朋友

搬运于2025-08-24 22:07:31，当前版本为作者最后更新于2022-12-30 13:15:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是一篇关于常数的题解，截止 2022 年 12 月 30 日我是最优解。

算法的常数

为了方便分析，假设 $n=2^k - 1$，也就是 $k = O(\log n)$.

如果使用矩阵乘法，两个 $2 \times 2$ 的矩阵相乘需要 $8$ 次乘法（如果考虑 Strassen algorithm 则是 7 次），所以计算 $M^n$ 需要 $16k$ 次乘法（$8k$ 次平方，$8k$ 次乘法）。

一个更好的方法是设 $A(n) = a^n$，$B(n) = b^n$，$S(n) = \sum_{i = 0} a^i b^{n - i}$。我们有递归关系：

• 当 $n$ 是偶数的时候，$A(n) = (A(n/2))^2$，$B(n) = (B(n/2))^2$, $S(n) = S(n/2)\,(A(n/2) + B(n/2)) - A(n/2)\,B(n/2)$，这需要 $4$ 次乘法。
• 当 $n$ 是奇数的时候，$A(n) = a\,A(n-1)$, $B(n) = b\,B(n-1)$，$S(n) = a\,S(n - 1) + B(n)$，这需要 $3$ 次乘法。

所以计算 $S(n)$ 需要 $7k=4k+3k$ 次乘法。

当然，当 $n$ 是奇数的时候，我们可以先计算 $A' = a\,A(n/2)$ 和 $B' = b\,B(n/2)$，然后 $S(n) = S(n/2)\,(A' + B')$, $A(n) = A'\,A(n/2)$, $B(n)=B'B(n/2)$，这需要 5 次乘法。总共计算 $S(n)$ 需要 $5k$ 次乘法。

实现的常数

根据我的 benchmark，在 64 位模数下，Barrett Multiplication 比直接调用 % 快 4 倍。

-------------------------------------------------------------------------------
mod_64 - BarrettMod64T<>

benchmark name                            samples    iterations          mean
bench                                          100             3     4.5259 us 

-------------------------------------------------------------------------------
mod_64 - NonConstMod64T<>

benchmark name                            samples    iterations          mean
bench                                          100             1    19.6215 us 
===============================================================================

所以你应该使用 Barrett Multiplication。

最后加上快速读入。