P5137 polynomial

ftiasch · 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。

最后加上快速读入。